Pascalsches Dreieck

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Das Pascalsche Dreieck enthält die Binomialkoeffizienten. Sie sind im Dreieck derart angeordnet, dass ein Eintrag die Summe der zwei darüberstehenden Einträge ist. Der Name geht auf Blaise Pascal zurück, obgleich das Pascalsche Dreieck bereits 1303 im Manuskript des Chinesen Chu Shih-chieh abgebildet wurde.

[Bearbeiten] Anwendung

Das Pascalsche Dreieck gibt eine Handhabe, schnell beliebige Potenzen von Binomen auszumultiplizieren. So finden sich in der dritten Zeile die Koeffizienten der ersten beiden Binomischen Formeln:

$(a \pm b)^2 = a^2 \pm 2\cdot a\cdot b + b^2$ .

In der nächsten Zeile finden sich die Koeffizienten für $(a \pm b)^3$ :

$(a \pm b)^3 = a^3\pm 3\cdot a^2\cdot b^1 + 3\cdot a^1 \cdot b^2 \pm b^3$ .

Diese Auflistung kann beliebig fortgesetzt werden, wobei zu beachten ist, dass für das Binom $(a - b)$ stets das Minuszeichen aus „ $\pm$ “ zu nehmen ist, und dass, während der Exponent von $a$ in jeder Formel stets um 1 abnimmt, der Exponent von $b$ um 1 zunimmt. Eine Verallgemeinerung liefert der Binomische Lehrsatz.

Eine Erweiterung in die dritte Dimension ist die Pascalsche Pyramide.

[Bearbeiten] Folgen im Pascalschen Dreieck

Im Pascalschen Dreieck finden sich viele bekannte Zahlenfolgen wieder.

[Bearbeiten] Die natürlichen Zahlen und Summenfolgen

In jeder Diagonale steht die Folge der Partialsummen zu der Folge, die in der Diagonale darüber steht. So steht in der zweiten Diagonale

$1=1,\quad 2=1+1,\quad 3=1+1+1,\quad 4=1+1+1+1,\quad\ldots,$

in der dritten die Folge der Dreieckszahlen

$1=1,\quad 3=1+2,\quad 6=1+2+3,\quad 10=1+2+3+4,\quad\ldots,$

in der vierten die Folge der Tetraederzahlen

$1=1,\quad 4=1+3,\quad 10=1+3+6,\quad 20=1+3+6+10,\quad\ldots$

und so weiter. Umgekehrt ist jede Diagonalenfolge die Differenzenfolge zu der in der Diagonale unterhalb stehenden Folge.

Die ersten vier Zeilen unter der 1 an der Spitze beschreiben 11er Potenzen.

[Bearbeiten] Die Fibonacci-Zahlen

Die Summen der hier grau bzw. weiß markierten flachen „Diagonalen“ ergeben jeweils eine Fibonacci-Zahl (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...). In diesem Beispiel ist die Summe der weißen Diagonale gleich 21, die Summe der grauen Diagonale gleich 34. Dass sich die „Diagonale“ manchmal nicht von einem zum anderen Ende „durchziehen“ lässt, wie im Fall der weißen Diagonale, ist unerheblich.

[Bearbeiten] Die Zweierpotenzen

Die Summe der Glieder der $n$ -ten Zeile ist $2 n - 1$ (1, 2, 4, 8, 16, 32, 64, 128, 256, ...). Oder anders ausgedrückt: die Summe der Binomialkoeffizienten in der binomischen Formel $n$ -ten Grades beträgt $2 n$ .

1 = $20$

1+1 = 2 = $21$

1+2+1 = 4 = $22$

1+3+3+1 = 8 = $23$

...

[Bearbeiten] Potenzen mit beliebiger Basis

Für Potenzen mit beliebiger Basis existiert ein Zahlendreieck anderer Art:

$\begin{matrix} &j &{n \choose 1}&{n \choose 2}&{n \choose 3}&{n \choose 4}&{n\choose 5}\\ i&&&&&&\\ n^1&&1&&&&&\\ n^2&&1&2&&&\\ n^3&&1&6&6&&\\ n^4&&1&14&36&24&\\ n^5&&1&30&150&240&120 \end{matrix}$

Zu dieser Dreiecksmatrix gelangt man durch Inversion der Matrix der Koeffizienten der Terme, die die Kombinationen ohne Wiederholung der Form ( $n$ über $k$ ) für $k = 1,2,3 \dots$ usw. darstellen.

Beispiel: ( $n$ über 2) $= n (n - 1) / 2 = - 0,5 n + 0,5 n 2$ .

(Lesart: $n 5$ = 1*( $n$ über 1) + 30*( $n$ über 2) + 150*( $n$ über 3) + 240*( $n$ über 4) + 120*( $n$ über 5))

Beispiel: $65 = 1 * 6 + 30 * 15 + 150 * 20 + 240 * 15 + 120 * 6 = 7776$

Das Bildungsgesetz der Koeffizienten lautet für den Koeffizienten in Zeile $i$ und Spalte $j$ :

$E(i,j) = [E(i-1,j-1)+E(i-1,j)]\cdot j$

Mit Hilfe dieses Dreiecks gewinnt man unmittelbare Einblicke in die Teilbarkeit von Potenzen. So ist jede Primzahlpotenz $n p$ für $p > 3$ äquivalent $n$ modulo $6 p$ . Dies ist im wesentlichen der Inhalt des kleinen fermatschen Satzes; zusätzlich wird jedoch gezeigt, dass der Ausdruck $a p - a$ für alle $a$ nicht nur durch $p$ , sondern für $p > 3$ auch durch 6 teilbar ist. Der größte gemeinsame Teiler der Matrixkoeffizienten ab dem zweiten Koeffizienten der Primzahlexponenten für $n$ entspricht stets dem Nenner der jeweiligen Bernoullischen Zahl (Beispiel: $p = 3$ : Nenner = 6; $p = 5$ : Nenner = 30, usw.)

Mit diesem Zahlendreieck kann beispielsweise mühelos bewiesen werden, dass $n 5 - n 3$ für alle $n$ aus $\mathbb{N}$ durch 24 teilbar ist: $0\cdot a+ 24\cdot b + 144\cdot c + 240\cdot d + 120\cdot e$ (mit $a = n$ über 1, $b = n$ über 2 usf.) ist stets durch 24 teilbar, da wegen $n$ aus $\mathbb{N}$ auch $a, b, c, d, e$ stets aus $\mathbb{N}$ sind.

==Rekursive Implementierung==* rekursive Implementierung in C++

#include <iostream>
//Non-efficient design // for educational use only
//Questions: stefan (dot) steiger (at) bluewin (dot) ch

//Calculates binomial coefficient
long nCr(unsigned int n , unsigned int k)
{
        if (n < k) return 0;
        if (k == 0) return 1;
        return n * nCr (n -1 , k -1) / k;
}

//outputs one line of the Pascal Triangle
void PascalTriangleRow(unsigned int row, unsigned int column)
{
        if (column==0)
                std::cout << nCr(row,column);
        else
        {
                std::cout << nCr(row,column) << "\t\t";
                PascalTriangleRow(row,column-1);
        }
}

//Puts n tabs at the start of each lines
void PutTab(unsigned int n)
{
        if(n!=0)
        {
                std::cout << "\t";
                PutTab(n-1);
        }
}

//Iterates recursively to the n-th row of the pascal triangle
unsigned int& PascalTriangle(unsigned int n)
{
        static unsigned int i=0;

        if(i!=n)
        {
                PutTab(n-i-1);
                PascalTriangleRow(i,i);
                std::cout << std::endl;
                ++i;
                PascalTriangle(n);
        }
        return i;
}


//Outputs the triangle for column 1 to 5
int main()
{
        for(int i = 1;i<=5;++i)
        {
        unsigned int& v=PascalTriangle(i);
        v=0;
        std::cout << "\n\n\n";
        }
        return 0;
}