Pascalsche Dreiecksformel mit Beispielen

Was ist Pascals Dreieck?

Das Pascalsche Dreieck ist eine dreieckige Anordnung von Zahlen, die einem einfachen Muster folgt, das sich aus der darüberliegenden Zeile ergibt. Es wurde im 17. Jahrhundert vom französischen Mathematiker Blaise Pascal bekannt gemacht. Das Dreieck beginnt mit einer einzelnen „1“ an der Spitze, und jede nachfolgende Zeile beginnt und endet ebenfalls mit einer „1“.

Über seine elegante Form hinaus birgt das Pascalsche Dreieck tiefgreifende mathematische Zusammenhänge. Es ist eng mit dem Binomialsatz, der Kombinatorik und der Wahrscheinlichkeitsrechnung verbunden, weshalb es weltweit in Algebra-, Statistik- und Informatikvorlesungen Verwendung findet.

Geschichte des Pascalschen Dreiecks

Obwohl das Dreieck nach Blaise Pascal benannt wurde, existierte es bereits Jahrhunderte vor ihm. Der chinesische mathematische Text „Die neun Kapitel über die mathematische Kunst“ enthält eines der frühesten bekannten Beispiele, das viele der Muster zeigt, die wir heute verwenden.

Der persische Mathematiker Al-Karaji und der indische Gelehrte PingAuch Ala untersuchte ähnliche Anordnungen. Pascal formalisierte die Eigenschaften des Dreiecks in seiner 1654 erschienenen Abhandlung „Traité du triangle arithmétique“, die der Struktur in der westlichen Mathematik ihren modernen Namen gab.

Konstruktion des Pascalschen Dreiecks

Das Konstruieren des Pascalschen Dreiecks ist einfach. Die einzige Regel, die man sich merken muss, ist, dass jede Zeile mit 1 beginnt und endet und jede weitere Zahl aus der Zeile darüber gebildet wird.

Für jede Zeile r und Spalte c ist der Wert gleich der Summe der Zahlen in den Spalten c-1 und c der Zeile r-1.

Dabei steht:

• r = 3, 4, 5, …
• n und c = 2, 3, 4, …, r-1.

Hier sind die Schritte zum Aufbau des Pascalschen Dreiecks:

Schritt 1) Beginnen Sie damit, die ersten beiden Zeilen auszufüllen.

Schritt 2) Das zweite Element der dritten Zeile ist die Summe der ersten und zweiten Zahl in der zweiten Zeile.

Schritt 3) Die vierte Zeile beginnt mit „1“. Die zweite Zahl ist 3, die Summe von 1 und 2 (blau hervorgehoben).

Die Abbildung unten zeigt, wie die vierte Zeile ausgefüllt wird:

Schritt 4) Die fünfte Zeile besteht aus fünf Zahlen. Das Muster zum Füllen der Zeilen kennen wir bereits aus den vorherigen Schritten.

Pascals Dreiecksformel – Binomialkoeffizient

Der Binomialkoeffizient gibt die Anzahl der Möglichkeiten an, eine Teilmenge von k Elementen aus einer Menge von n Elementen auszuwählen. Er wird üblicherweise als „C(n, k)“ oder „n über k“ geschrieben.

Der Binomialkoeffizient ist wie folgt definiert:

Das Symbol „!“ kennzeichnet die Fakultät einer Zahl.

n! = n.(n-1).(n-2)…3.2.1

Zum Beispiel,

5! = 5.4.3.2.1

= 120

Also, C(5, 3) oder „5 über 3“ = 5! / 3!(5-3)!

= 120 / 12

= 10

Methode 1: Aufbau des Pascalschen Dreiecks anhand der vorherigen Zeile

Das hier beschriebene Verfahren entspricht dem manuellen Zeichnen des Dreiecks. Angenommen, wir möchten ein Pascalsches Dreieck mit bis zu sieben Zeilen erzeugen.

Die einzelnen Schritte hierfür sind wie folgt:

Schritt 1) Die oberste Zeile beginnt mit „1“.

Schritt 2) Für die Zeile „r“ ist das Element „c“ die Summe der Spalte „c-1“ und der Spalte „c“ der Zeile „r-1“.

Schritt 3) Die erste und die letzte Zahl in jeder Zeile sind immer „1“.

Wenn wir diese drei einfachen Schritte befolgen, können wir das gesamte Dreieck systematisch konstruieren.

C++ Code des Pascalschen Dreiecks in der vorherigen Zeile

#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
  int numbers[n][n];
  for (int row = 0; row < n; row++)
  {
    for (int col = 0; col <= row; col++)
    {
      if (col == 0 || col == row)
      {
        numbers[row][col] = 1;
      }
      else
      {
        numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
      }
      cout << numbers[row][col] << "\t";
    }
    cout << endl;
  }
}
int main()
{
  int n;
  cout << "How many rows: ";
  cin >> n;
  printRow(n);
}

Ausgang:

How many rows: 7
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1
1       5       10      10      5       1
1       6       15      20      15      6       1

Python Code der Pascalschen Dreiecksformel aus der vorherigen Zeile

def printRow(n):
    numbers = [[0 for row in range(n)]
               for col in range(n)
               ]
    for row in range(len(numbers)):
        for col in range(0, row+1):
            if row == col or col == 0:
                numbers[row][col] = 1
            else:
                numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]

            print(numbers[row][col],end="\t")
        print("\n")
n = int(input("How many rows: "))
printRow(n)

Beispielausgabe für das Pascalsche Dreieck:

How many rows: 7
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1
1       5       10      10      5       1
1       6       15      20      15      6       1

Komplexitätsanalyse

A zweidimensionales Array wird in dieser Implementierung verwendet. Da N die Anzahl der Zeilen im Pascalschen Dreieck ist, benötigt man dafür N² Einheitsräume. Daher beträgt die Speicherkomplexität O(N).²).

Die Funktion verwendet zwei verschachtelte Schleifen, die jeweils bis zu „N“ Mal durchlaufen werden. Die Zeitkomplexität beträgt daher ebenfalls AUF²)oder quadratische Zeitkomplexität.

Methode 2: Aufstellen des Pascalschen Dreiecks durch Berechnung des Binomialkoeffizienten

Die Zahlen des Pascalschen Dreiecks lassen sich direkt mithilfe der Binomialkoeffizienten ableiten. Das folgende Diagramm veranschaulicht den Zusammenhang:

Hier sind die Schritte zum Aufbau des Pascalschen Dreiecks durch Berechnung des Binomialkoeffizienten:

Schritt 1) Die oberste Zeile ist C(0, 0). Gemäß der obigen Formel gilt C(0, 0) = 1, da 0! = 1.

Schritt 2) In Zeile „i“ befinden sich insgesamt „i“ Elemente. Jedes Element wird als C(n, r) berechnet, wobei n = i-1 ist.

Schritt 3) Wiederholen Sie Schritt 2 so oft, wie Sie Zeilen des Pascalschen Dreiecks erzeugen möchten.

C++ Code Pascalsches Dreieck mithilfe des Binomialkoeffizienten

#include <iostream>
using namespace std;
int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}
int binomialCoefficient(int n, int r)
{
    int result = 1;
    if (r > n)
    {
        return -1;
    }
    result = factorial(n) / (factorial(r) * factorial(n - r));
    return result;
}
void printPascalTriangle(int row)
{
    for (int i = 0; i <= row; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            cout << binomialCoefficient(i, j) << "\t";
        }
        cout << endl;
    }
}
int main()
{
    int n;
    cout << "Enter row number: ";
    cin >> n;
    printPascalTriangle(n);
}

Ausgang:

Enter row number: 9
1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1
1	6	15	20	15	6	1
1	7	21	35	35	21	7	1
1	8	28	56	70	56	28	8	1
1	9	36	84	126	126	84	36	9	1

Python Code Pascalsches Dreieck mithilfe des Binomialkoeffizienten

def factorial(n):
    result = 1
    for i in range(1,n+1):
        result*=i
    return result
def binomialCoefficient(n,r):
    result =1
    if r>n:
        return None
    result = factorial(n) / (factorial(r) * factorial(n - r))
    return int(result)
def printPascalTriangle(row):
    for i in range(row+1):
        for j in range(i+1):
            print(binomialCoefficient(i, j), end="\t")
        print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)

Beispielausgabe für das Pascalsche Dreieck:

Enter row number: 8
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1
1       5       10      10      5       1
1       6       15      20      15      6       1
1       7       21      35      35      21      7       1
1       8       28      56      70      56      28      8       1

Komplexitätsanalyse

In dieser Implementierung werden drei Schleifen verwendet: eine zur Berechnung des Binomialkoeffizienten und zwei weitere zur Iteration über jede Zeile und Spalte. Bezüglich der Anzahl der Zeilen werden alle drei Schleifen bis zu „n“ Mal ausgeführt. Folglich beträgt die Gesamtzeitkomplexität O(n²).³).

Die Speicherkomplexität ist konstant, da keine Zwischenergebnisse gespeichert werden. Das Programm berechnet jedes Element zur Laufzeit und gibt es zeilenweise aus, wodurch sich die Speicherkomplexität reduziert. O (1).

Methode 3: Aufbau des Pascalschen Dreiecks durch modifizierten Binomialkoeffizienten

Bei der bisherigen Methode wurde die Binomialkoeffizientenformel zur Berechnung jedes Elements verwendet. Der modifizierte Ansatz leitet C(n, r) direkt aus C(n, r-1) ab und reduziert so den Rechenaufwand um eine Größenordnung.

Hier sind die Schritte zum Aufbau des Pascalschen Dreiecks mithilfe des modifizierten Binomialkoeffizienten:

Schritt 1) Die erste Zeile beginnt mit „1“.

Schritt 2) Berechne C(n, r), wobei „n“ die Zeilennummer und „r“ der Spaltenindex ist. Weise diesen Wert einer Variablen C zu.

Schritt 3) Um den nächsten Koeffizienten zu berechnen, verwenden Sie C * (n – k) / k. Weisen Sie diesen neuen Wert wieder C zu.

Schritt 4) Fahren Sie mit Schritt 3 fort, bis „k“ das Ende der Zeile erreicht. Erhöhen Sie k nach jeder Iteration um eins.

C++ Code für das Pascalsche Dreieck mittels modifiziertem Binomialkoeffizienten

#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
  for (int row = 1; row <= n; row++)
  {
    int previous_coef = 1;
    for (int col = 1; col <= row; col++)
    {
      cout << previous_coef << "\t";
      previous_coef = previous_coef * (row - col) / col;
    }
    cout << endl;
  }
}

int main()
{
  int n;
  cout << "How many rows: ";
  cin >> n;
  printpascalTriangle(n);
}

Ausgang:

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

Python Code für das Pascalsche Dreieck mittels modifiziertem Binomialkoeffizienten

def printpascalTriangle(n):
    for row in range(1, n+1):
        previous_coef = 1
        for col in range(1, row+1):
            print(previous_coef, end="\t")
            previous_coef = int(previous_coef*(row-col)/col)
        print()
n = int(input("How many rows: "))
printpascalTriangle(n)

Ausgabe von Pascals Dreiecksmustern:

How many rows: 5
1
1       1
1       2       1
1       3       3       1
1       4       6       4       1

Komplexitätsanalyse

Die Implementierung verwendet zwei Schleifen, die jeweils maximal „n“ Mal durchlaufen werden, wobei „n“ die Anzahl der Zeilen im Dreieck ist. Die Zeitkomplexität beträgt somit O(n²). Auf²), quadrierte Zeit.

Bezüglich der Speicherkomplexität benötigen wir kein Array zur Speicherung. Wir verwenden lediglich eine Variable, um den vorherigen Binomialkoeffizienten zu speichern, benötigen also nur einen zusätzlichen Speicherplatz. Die Speicherkomplexität beträgt daher O (1).

Anwendung des Pascalschen Dreiecks

Hier einige praktische Anwendungen des Pascalschen Dreiecks:

Binomialentwicklungen: Die Koeffizienten einer beliebigen Binomialentwicklung lassen sich direkt aus dem Pascalschen Dreieck ablesen. Hier ist ein Beispiel:

Kombinationen berechnen: Die Elemente des Pascalschen Dreiecks entsprechen direkt den Binomialkoeffizienten. Wenn man beispielsweise 6 Kugeln hat und 3 davon auswählen möchte, lautet die Antwort: ⁶C₃Diesen Wert finden Sie im dritten Element der sechsten Zeile des Pascalschen Dreiecks.

Wahrscheinlichkeit: Das Pascalsche Dreieck wird häufig verwendet, um Wahrscheinlichkeiten bei Münzwürfen, Würfelproblemen und anderen kombinatorischen Ereignissen zu berechnen, bei denen jedes Ergebnis einer Binomialverteilung entspricht.

Interessante Fakten über das Pascalsche Dreieck

Hier sind einige interessante Fakten zum Pascalschen Dreieck:

• Die Summe aller Elemente in einer Zeile ist immer eine Zweierpotenz.

• Die Diagonalsummen der Zeilen ergeben die Fibonacci-Folge.

• Jede Zeile entspricht den Koeffizienten in der Entwicklung von (a+b)ⁿ.
• Schattiert man nur die ungeraden Zahlen, so ergibt sich die Sierpinski-Dreiecksfraktalfigur.

Häufig gestellte Fragen