Pascalsches Dreieck

Grundidee und Aufbau

Das Pascalsche Dreieck ist eine grafische Darstellung der Binomialkoeffizienten {n \choose k}. Ein Binomialkoeffizient gibt in diesem Zusammenhang den Eintrag in Zeile n und Spalte k an; die Zählung beginnt bei Null, also mit der ersten Zeile n=0 und der ersten Spalte k=0. An den Rändern stehen Einträge mit dem Wert 1. Jeder innere Eintrag entsteht als Summe der zwei darüberstehenden Einträge.

Dieser Zusammenhang wird durch die Formel {n+1 \choose k+1}={n \choose k}+{n \choose k+1} beschrieben. Aus den Randwerten und dieser Additionsregel ergeben sich genau die Binomialkoeffizienten. Die ersten Zeilen enthalten zum Beispiel die Werte 1, dann 1,1, dann 1,2,1, dann 1,3,3,1 und so weiter.

Der Name geht auf Blaise Pascal zurück. Das Dreieck war aber schon früher bekannt und trägt in verschiedenen Ländern andere Namen: In China heißt es Yang-Hui-Dreieck, in Italien Tartaglia-Dreieck und im Iran Chayyām-Dreieck.

Geschichte

Die früheste detaillierte Darstellung eines Dreiecks von Binomialkoeffizienten erschien im 10. Jahrhundert in Kommentaren zur Chandas Shastra, einem indischen Werk zur Prosodie des Sanskrit. Dieses Werk wurde von Pingala zwischen dem fünften und zweiten Jahrhundert vor Christus geschrieben. Der Kommentator Halayudha verwendete um 975 das Dreieck; außerdem war bereits bekannt, dass Summen flacher Diagonalen Fibonacci-Zahlen ergeben. Vom indischen Mathematiker Bhattotpala, etwa um 1070, sind die ersten 17 Zeilen des Dreiecks überliefert.

Im Nahen Osten behandelten al-Karadschi (953–1029), as-Samaw'al und Omar Chayyām das Dreieck. Dort waren verschiedene mathematische Sätze dazu bekannt, darunter der binomische Lehrsatz. Es gilt als ziemlich sicher, dass Chayyām ein Verfahren zur Berechnung der n-ten Wurzel verwendete, das auf der binomischen Erweiterung und damit auf Binomialkoeffizienten beruhte.

In China findet sich die früheste Darstellung eines identischen arithmetischen Dreiecks in Yang Huis Buch Xiangjie Jiuzhang Suanfa von 1261. Yang Hui schrieb, er habe das Dreieck von Jia Xian, um 1050, und dessen Methode zur Berechnung von Quadrat- und Kubikwurzeln übernommen.

In Europa veröffentlichte Peter Apian das Dreieck 1531/32 auf dem Titelbild eines Buchs über Handelsberechnungen; eine frühere Version von 1527 gilt als erster schriftlicher Nachweis des pascalschen Dreiecks in Europa. Blaise Pascal schrieb 1654 sein 1665 veröffentlichtes Buch Traité du triangle arithmétique, in dem er Ergebnisse zum Dreieck sammelte und für Probleme der Wahrscheinlichkeitstheorie verwendete. Später wurde das Dreieck von Pierre Rémond de Montmort (1708) und Abraham de Moivre (1730) nach Pascal benannt.

Binome und Rechnen mit Potenzen

Eine wichtige Anwendung des Pascalschen Dreiecks ist das Ausmultiplizieren von Potenzen von Binomen. Ein Binom ist ein Ausdruck aus zwei Termen, zum Beispiel a+b oder a-b. Die Zahlen einer Zeile liefern die Koeffizienten, also die Zahlenfaktoren, die vor den einzelnen Termen stehen.

In der Zeile n=2 stehen die Koeffizienten 1,2,1. Sie gehören zu den ersten beiden binomischen Formeln: (a\pm b)^2=a^2\pm 2\cdot ab+b^2. In der nächsten Zeile stehen 1,3,3,1, also die Koeffizienten für (a\pm b)^3: (a\pm b)^3=a^3\pm 3\cdot a^2b^1+3\cdot a^1b^2\pm b^3.

Allgemein nimmt in diesen Formeln der Exponent von a Schritt für Schritt um 1 ab, während der Exponent von b um 1 zunimmt. Für (a-b) wird jeweils das Minuszeichen aus \pm verwendet. Dabei wechseln die Vorzeichen bei beliebigem Exponenten zwischen Minus und Plus; ein Minus steht immer dann, wenn der Exponent von b ungerade ist. Zum Beispiel gilt (a-b)^4=a^4-4\cdot a^3b^1+6\cdot a^2b^2-4\cdot a^1b^3+b^4.

Die Verallgemeinerung dieser Regel ist der binomische Lehrsatz. Außerdem nennt der Artikel zwei Erweiterungen: Das Trinomial Triangle ist eine zweidimensionale Verallgemeinerung, in der jede Zahl die Summe von drei Einträgen ist. Eine Erweiterung in die dritte Dimension ist die Pascalsche Pyramide.

Zahlenfolgen im Dreieck

Im Pascalschen Dreieck treten viele bekannte Zahlenfolgen auf. In den Diagonalen steht zuerst nur die Folge der Einsen. Die zweite Diagonale enthält die natürlichen Zahlen. In der dritten Diagonale stehen die Dreieckszahlen, in der vierten die Tetraederzahlen. Allgemein findet man in der r-ten Diagonale die regulären figurierten Zahlen der Ordnung r. Jede Diagonale enthält die Partialsummen der darüberliegenden Diagonale; umgekehrt ist jede Diagonalenfolge die Differenzenfolge der darunterliegenden Diagonale.

Für die Dreieckszahlen gilt \Delta(n)={n+1 \choose 2}. Für die Tetraederzahlen gilt T(n)=\sum_{k=1}^{n}\Delta(k)={n+2 \choose 3}. Für reguläre figurierte Zahlen der Ordnung r gilt R(r,n)=\sum_{k=1}^{n}R(r-1,k)={n+r-1 \choose r}.

Auch die Fibonacci-Zahlen entstehen im Pascalschen Dreieck. Addiert man bestimmte flache Diagonalen, erhält man die Folge 1,1,2,3,5,8,13,21,34,\dots. Im Artikel werden als Beispiele Diagonalensummen von 13, 21 und 34 genannt. Allgemein gilt für n\geq 1: F(n)=\sum_{k=0}^{\lfloor n/2\rfloor}{n-k-1 \choose k}=\sum_{k=0}^{\lfloor n/2\rfloor}{n-k-1 \choose n-2k-1}.

Auch die Zeilen besitzen wichtige Eigenschaften. Die Summe der Einträge einer Zeile heißt Zeilensumme. Von oben nach unten verdoppeln sich die Zeilensummen; da die erste Zeilensumme gleich 1 ist, ist die Zeilensumme der n-ten Zeile gleich 2^{n-1}. Für Binomialkoeffizienten gilt \sum_{k=0}^{n}{n \choose k}=2^n. Reiht man die Ziffern der ersten fünf Zeilen aneinander, erhält man 1,11,121,1331,14641, also die ersten Potenzen von 11. Die alternierende Summe jeder Zeile ist für n>0 gleich Null: \sum_{k=0}^{n}(-1)^k{n \choose k}=0. Diese Formeln folgen aus dem binomischen Lehrsatz (1+x)^n=\sum_{k=0}^{n}{n \choose k}x^k für x=1, x=10 und x=-1.

Die mittleren Binomialkoeffizienten beginnen mit 1,2,6,20,70,252,\dots.

Verbindungen zu anderen Strukturen

Das Pascalsche Dreieck ist mit dem Sierpinski-Dreieck verwandt, das 1915 nach Wacław Sierpiński benannt wurde. Beide verwenden eine einfache Iterationsvorschrift. Ein direkter Zusammenhang entsteht, wenn man das Pascalsche Dreieck modulo 2 betrachtet: Gerade Zahlen werden zum Beispiel weiß und ungerade Zahlen schwarz eingefärbt. Dann ergibt sich unmittelbar die Struktur des Sierpinski-Dreiecks.

Für Potenzen mit beliebiger Basis beschreibt der Artikel ein anderes Zahlendreieck. Es entsteht durch Inversion einer Matrix von Koeffizienten zu Kombinationen ohne Wiederholung der Form {n \choose k}. Ein Beispiel ist {n \choose 2}=\frac{n(n-1)}{2}=-0{,}5n+0{,}5n^2. Eine Lesart lautet: n^5=1{n \choose 1}+30{n \choose 2}+150{n \choose 3}+240{n \choose 4}+120{n \choose 5}. Für 6^5 ergibt das 1\cdot6+30\cdot15+150\cdot20+240\cdot15+120\cdot6=7\,776.

Das Bildungsgesetz der Koeffizienten in diesem Zahlendreieck lautet E(i,j)=[E(i-1,j-1)+E(i-1,j)]\cdot j. Außerdem gilt E(i,j)=j!S(i,j), wobei S(i,j) eine Stirling-Zahl ist. Das Dreieck gibt Einblicke in Teilbarkeit von Potenzen: Jede Primzahlpotenz n^p ist für p>3 kongruent n modulo 6p. Damit wird in diesem Zusammenhang der kleine Fermatsche Satz berührt und zusätzlich gezeigt, dass a^p-a für p>3 auch durch 6 teilbar ist.

John Wallis nutzte 1655 eine schachbrettartige Interpolation zwischen figurierten Zahlenfolgen zur ersten Berechnung einer Darstellung von 4/\pi als unendliches Produkt. Außerdem erwähnt der Artikel die Singmaster-Vermutung über die Häufigkeit, mit der eine Zahl im Pascalschen Dreieck vorkommt, sowie die Tatsache, dass die Summe der ersten vier Terme jeder Reihe die Kuchenzahlen ergibt.