Pascals Dreieck – Formel, Muster und Beispiele
Sarah Chen
Was ist Pascals Dreieck?
Das Pascalsche Dreieck ist eine dreieckige Zahlenreihe, gefolgt von einem bestimmten Muster und einer Verbindung zur vorhergehenden Reihe. Es wurde von Blaise Pascal erfunden. Dieses Dreieck beginnt mit einem Element in der ersten Reihe. Danach beginnt und endet jede Reihe mit „1“.
Geschichte des Pascalschen Dreiecks
Das chinesische Buch „The Nine Chapters on the Mathematical Art“ enthält eines der ersten Beispiele für das Pascalsche Dreieck. Darüber hinaus enthält es einige der gleichen Muster und Eigenschaften, die heute in Dreiecken zu finden sind.
Pascal war einer von mehreren Menschen in Europa, die das Dreieck studierten. Andere Mathematiker hatten vor ihm ähnliche dreieckige Zahlenanordnungen untersucht.
Konstruktion des Pascalschen Dreiecks
Die Konstruktion des Pascalschen Dreiecks ist einfach. Sie müssen sich lediglich merken, dass die Reihe mit 1 beginnt und endet. Für die restlichen Zahlen gilt folgende Regel:
Für jede Zeile r und Spalte c ist die Zahl die Summe der Spalten c-1 und c aus Zeile r-1.
Hier
- r = 3,4,5….
- n und c = 2,3,4,…r-1.
Hier sind Schritte zum Aufbau des Pascalschen Dreiecks:
Schritt 1) Beginnen wir damit, zwei Zeilen aufzufüllen.
Schritt 2) Das zweite Element für die dritte Zeile ist die Summe der ersten und zweiten Zahl in der zweiten Reihe.
Schritt 3) Die vierte Zeile beginnt mit „1.“ Die zweite Zahl ist 3, also die Summe von 1 und 2 (blau hervorgehoben).
Das folgende Bild zeigt, wie die vierte Zeile gefüllt wird:
Schritt 4) Die fünfte Zeile besteht aus fünf Zahlen. Das Muster zum Auffüllen der Zeilen kennen wir bereits aus den vorherigen Schritten.
Pascals Dreiecksformel – Binomialkoeffizient
Ein Binomialkoeffizient ist eine Zahl, die verschiedene Methoden zum Auswählen einer Teilmenge von k Elementen aus einer Sammlung von n Elementen ausdrückt. Häufig wird es als „C(n,k)“ oder „n wähle k“ geschrieben.
Der Binomialkoeffizient ist definiert als
Der "!" bezeichnet die „Fakultät“.
N! = n.(n-1). (n-2)…3.2.1
Zum Beispiel,
5! = 5.4.3.2.1
= 120
Nehmen wir also an, C(5,3) oder 5 wählen 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Methode 1: Aufbau des Pascalschen Dreiecks anhand der vorherigen Zeile
Die Schritte in diesem Verfahren sind die gleichen wie im Pascalschen Dreieck. Nehmen wir an, wir möchten das Pascalsche Dreieck mit bis zu sieben Reihen erstellen.
Die Schritte, um dies zu erreichen, sind wie folgt:
Schritt 1) Beginnen Sie die oberste Zeile mit „1“.
Schritt 2) Für die Zeile „r“ ist das Element „c“ das Produkt aus „c-1“ und „c“ die Nummer der Zeile „r-1“.
Schritt 3) Die erste und die letzte Zahl in einer Reihe sind immer „1“.
Wir müssen diese drei einfachen Schritte befolgen, um das Pascalsche Dreieck zu erstellen.
C++ Code des Pascalschen Dreiecks durch die vorherige 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 Dreieckformel durch die vorherige 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 wurde bei der Umsetzung verwendet. Vorausgesetzt, N ist die Anzahl der Zeilen im Pascalschen Dreieck. Dies erfordert N2 Einheitsräume. Daher ist O die Raumkomplexität (N2).
Wir haben zwei Schleifen in der Funktion und jede Schleife wird „N“ Mal ausgeführt. Die zeitliche Komplexität ist also auch AUF2) oder quadrierte Zeitkomplexität.
Methode 2: Aufbau des Pascalschen Dreiecks durch Berechnung des Binomialkoeffizienten
Wir können die Zahlen des Pascalschen Dreiecks einfach mithilfe des Binomialkoeffizienten ableiten. Hier ist das Diagramm:
Hier sind die Schritte zum Aufbau des Pascalschen Dreiecks durch Berechnung des Binomials:
Schritt 1) Die oberste Zeile ist C(0,0). Unter Verwendung der obigen Formel für den Binomialkoeffizienten ist C(0,0) = 1. Weil 0! = 1.
Schritt 2) Für die Zeile „i“ gibt es insgesamt „i“-Elemente. Für jedes Element wird C(n,r) berechnet, wobei n i-1 ist.
Schritt 3) Wiederholen Sie Schritt 2 für die Anzahl der Zeilen, die Sie für das Pascal-Dreieck benötigen.
C++ Code des Pascalschen Dreiecks anhand 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 des Pascalschen Dreiecks anhand 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
Bei der Implementierung wurden drei Schleifen verwendet. Eine Schleife dient zur Berechnung des Binomialkoeffizienten und die anderen beiden zur Erstellung von Zahlen für alle Zeilen. Bezüglich der Anzahl der Zeilen haben wir drei Schleifen, die „n“ Mal ausgeführt werden. Folglich beträgt die Gesamtzeitkomplexität 0 (n3).
Die Speicherkomplexität ist jetzt konstant, da wir keine Daten im Speicher behalten. Das Programm berechnet das Element und gibt es in einer Zeile aus. Die Speicherkomplexität sinkt dann auf 0(1).
Methode 3: Aufbau des Pascalschen Dreiecks durch modifizierten Binomialkoeffizienten
In der vorherigen Technik haben wir bereits gesehen, wie man einen Binomialkoeffizienten verwendet, um jedes Element des Pascal-Dreiecks zu berechnen. Dieser Ansatz bestimmt C(n,r) aus C. (n, r-1). Es wird die Dinge um eine Reihenfolge vereinfachen.
Hier sind die Schritte zum Aufbau des Pascalschen Dreiecks anhand des modifizierten Binomialkoeffizienten:
Schritt 1) Beginnen Sie die erste Zeile mit „1“
Schritt 2) Berechnen Sie C(n,r), wobei „n“ die Zeilennummer und „r“ die Spalte oder das Element ist. Weisen Sie den Wert einer Variablen C zu.
Schritt 3) Zur Berechnung von C(n,k) beträgt es C*(nk)/k. Weisen Sie diesen Wert nun C zu.
Schritt 4) Fahren Sie mit Schritt 3 fort, bis „k“ das Ende der Reihe erreicht. Erhöhen Sie nach jeder Iteration den Wert von K um eins.
C++ Code für Pascals Dreieck durch modifizierten 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 Pascals Dreieck durch modifizierten 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 besteht aus zwei Schleifen. Jede Schleife wird maximal „n“ Mal ausgeführt, wobei „n“ die Anzahl der Zeilen im Pascal-Dreieck bezeichnet. Die zeitliche Komplexität beträgt also Auf2), quadrierte Zeit.
In Bezug auf die Speicherkomplexität brauchten wir kein Array zum Speichern. Wir verwendeten nur eine Variable, um den vorherigen Binomialkoeffizienten zu speichern. Wir brauchten also nur einen zusätzlichen Speicherplatz. Die Speicherkomplexität wurde O (1).
Anwendung des Pascalschen Dreiecks
Hier sind einige Anwendungen des Pascalschen Dreiecks:
Binomialentwicklungen: Wir können den Koeffizienten der Binomialentwicklungen aus dem Pascalschen Dreieck bestimmen. Hier ist ein Beispiel:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2und + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3und + 6x2y2 + 4xy3 + 1y4 |
Kombinationen berechnen: Wir haben gesehen, dass Elemente des Pascalschen Dreiecks Binomialkoeffizienten entsprechen. Wenn Sie beispielsweise 6 Bälle haben und aufgefordert werden, 3 Bälle auszuwählen, ist dies der Fall 6C3. Oder Sie finden die Zahl im 3. Element der 6. Reihe des Pascalschen Dreiecks.
Interessante Fakten über das Pascalsche Dreieck
Hier sind einige interessante Fakten zum Pascalschen Dreieck:
- Die Summe aller Elemente in einer Reihe ist immer die Potenz von 2.
- Die diagonale Summe der Elemente der Zeilen erzeugt die Fibonacci-Folge.
Zusammenfassung
- Das Pascalsche Dreieck gibt die Koeffizienten für die Binomialentwicklungen an.
- Jede Reihe des Pascal-Dreiecks beginnt und endet mit „1“. Die Zwischenwerte sind die Summe zweier Elemente der vorherigen Zeile.
- Die diagonale Addition aller Elemente im Pascal-Dreieck ergibt Folgendes: Fibonacci-Folge.
- Das Pascalsche Dreieck kann auch mit Binomialkoeffizienten erzeugt werden.
