Pascals trekantformel med eksempler
Sarah Chen
⚡ Smart opsummering
Pascals trekant er en trekantet opstilling af tal, hvor hver værdi er lig med summen af de to tal direkte over den, hvilket afslører dybe mønstre inden for kombinatorik, binomiale udvidelser og sandsynlighed, der har fascineret matematikere i århundreder.
Hvad er Pascals trekant?
Pascals trekant er en trekantet række af tal, der følger et simpelt mønster baseret på rækken ovenover. Den blev populariseret af den franske matematiker Blaise Pascal i det 17. århundrede. Trekanten begynder med et enkelt "1" øverst, og hver efterfølgende række starter og slutter også med "1".
Ud over sin elegante form koder Pascals trekant for dybe matematiske sammenhænge. Den er tæt knyttet til binomialsætningen, kombinatorisk tælling og sandsynlighedsteori, hvilket er grunden til, at den optræder i algebra-, statistik- og datalogiklasser verden over.
Pascals trekanthistorie
Selvom trekanten er opkaldt efter Blaise Pascal, er den århundreder ældre end ham. Den kinesiske matematiske tekst "De ni kapitler om matematisk kunst" indeholder et af de tidligste kendte eksempler, der viser mange af de samme mønstre, som vi bruger i dag.
Den persiske matematiker Al-Karaji og indiske lærde Pingala udforskede også lignende arrays. Pascal formaliserede trekantens egenskaber i sin afhandling fra 1654 "Traité du triangle arithmétique", som gav strukturen dens moderne navn i vestlig matematik.
Konstruktion af Pascals trekant
Det er ligetil at konstruere Pascals trekant. Den eneste regel, man skal huske, er, at hver række starter og slutter med 1, og alle andre tal bygges ud fra rækken ovenfor.
For enhver række r og kolonne c er værdien lig med summen af tallene i kolonne c-1 og c i række r-1.
Her,
- r = 3, 4, 5, …
- n og c = 2, 3, 4, …, r⁻¹.
Her er trinene til at bygge Pascals trekant:
Trin 1) Start med at udfylde de første to rækker.
Trin 2) Det andet element i tredje række er summen af det første og andet tal i anden række.
Trin 3) Den fjerde række begynder med "1". Det andet tal er 3, som er summen af 1 og 2 (fremhævet med blåt).
Billedet nedenfor viser, hvordan man udfylder den fjerde række:
Trin 4) Den femte række består af fem tal. Vi kender allerede mønsteret for udfyldning af rækker fra de tidligere trin.
Pascals trekantformel – binomial koefficient
En binomial koefficient tæller antallet af måder at vælge en delmængde af k elementer fra en samling af n elementer. Den skrives almindeligvis som "C(n, k)" eller "n vælger k".
Den binomiale koefficient er defineret som:
Symbolet "!" angiver fakulteten af et tal.
n! = n.(n-1).(n-2)…3.2.1
For eksempel:
5! = 5.4.3.2.1
= 120
Så, C(5, 3) eller “5 vælg 3” = 5! / 3!(5-3)!
= 120 / 12
= 10
Metode 1: Opbygning af Pascals trekant ved hjælp af den forrige række
Fremgangsmåden her afspejler, hvordan vi tegnede trekanten manuelt. Antag, at vi vil generere Pascals trekant med op til syv rækker.
Trinene til at gøre det er som følger:
Trin 1) Start den øverste række med "1".
Trin 2) For række "r" vil elementet "c" være summen af kolonne "c-1" og kolonne "c" i række "r-1".
Trin 3) Det første og sidste tal i hver række vil altid være "1".
Ved at følge disse tre enkle trin kan vi systematisk konstruere hele trekanten.
C++ Code af Pascals trekant ved den forrige række
#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); }
Output:
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 af Pascal-trekantformlen ved den forrige række
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)
Pascals trekanteksempel output:
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
Kompleksitetsanalyse
A todimensionelt array bruges i denne implementering. Da N er antallet af rækker i Pascals trekant, kræver dette N2 enhedsrum. Derfor er rumkompleksiteten O(N2).
Funktionen bruger to indbyggede løkker, der hver kører op til "N" gange. Så tidskompleksiteten er også PÅ2)eller kvadreret tidskompleksitet.
Metode 2: Opbygning af Pascals trekant ved at beregne binomialkoefficienten
Vi kan udlede tallene i Pascals trekant direkte ved hjælp af binomiale koefficienter. Diagrammet nedenfor illustrerer forholdet:
Her er trinnene til at opbygge Pascals trekant ved at beregne binomialkoefficienten:
Trin 1) Den øverste række er C(0, 0). Ved at bruge ovenstående formel er C(0, 0) = 1, fordi 0! = 1.
Trin 2) For række "i" vil der være i alt "i"-elementer. Hvert element beregnes som C(n, r), hvor n er i-1.
Trin 3) Gentag trin 2 for så mange rækker af Pascals trekant, som du ønsker at generere.
C++ Code Pascals trekant ved binomialkoefficient
#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); }
Output:
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 Pascals trekant ved binomialkoefficient
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)
Pascals trekanteksempel output:
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
Kompleksitetsanalyse
Tre løkker bruges i denne implementering: en til at beregne binomialkoefficienten og to mere til at iterere gennem hver række og kolonne. Med hensyn til antallet af rækker kører alle tre løkker op til "n" gange. Følgelig er den samlede tidskompleksitet O(n3).
Rumkompleksiteten er konstant, fordi vi ikke gemmer nogen mellemresultater. Programmet beregner hvert element undervejs og udskriver det i en række, så rumkompleksiteten reduceres til O (1).
Metode 3: Opbygning af Pascals trekant ved modificeret binomial koefficient
I den tidligere teknik brugte vi binomialkoefficientformlen til at beregne hvert element. Den modificerede tilgang udleder C(n, r) direkte fra C(n, r-1), hvilket reducerer arbejdet med én størrelsesorden.
Her er trinnene til at opbygge Pascals trekant ved hjælp af den modificerede binomiale koefficient:
Trin 1) Start den første række med "1".
Trin 2) Beregn C(n, r), hvor "n" er rækkenummeret og "r" er kolonneindekset. Tildel denne værdi til en variabel C.
Trin 3) For at beregne den næste koefficient skal du bruge C * (n – k) / k. Tildel denne nye værdi tilbage til C.
Trin 4) Fortsæt trin 3, indtil "k" når slutningen af rækken. Øg k med én efter hver iteration.
C++ Code for Pascals trekant ved hjælp af modificeret binomialkoefficient
#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); }
Output:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code for Pascals trekant ved hjælp af modificeret binomialkoefficient
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)
Pascals trekantmønstre output:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Kompleksitetsanalyse
Implementeringen bruger to løkker, der hver kører maksimalt "n" gange, hvor "n" er antallet af rækker i trekanten. Så tidskompleksiteten er På2), kvadreret tid.
Med hensyn til rumkompleksitet behøver vi ikke noget array til lagring. Vi bruger kun én variabel til at beholde den tidligere binomiale koefficient, så vi behøver kun ét ekstra rum. Rumkompleksiteten er derfor O (1).
Anvendelse af Pascals trekant
Her er nogle praktiske anvendelser af Pascals trekant:
Binomiale udvidelser: Koefficienterne for enhver binomial udvidelse kan aflæses direkte fra Pascals trekant. Her er et eksempel:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2og + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3og + 6x2y2 + 4xy3 + 1y4 |
Beregning af kombinationer: Elementerne i Pascals trekant svarer direkte til binomiale koefficienter. Hvis du for eksempel har 6 kugler og vil vælge 3, er svaret 6C3Du kan finde den værdi i det 3. element i den 6. række af Pascals trekant.
Sandsynlighed: Pascals trekant bruges i vid udstrækning til at beregne sandsynligheder i møntkast, terningproblemer og andre kombinatoriske begivenheder, hvor hvert udfald svarer til en binomialfordeling.
Interessante fakta om Pascals trekant
Her er nogle fakta, du vil finde interessante om Pascals trekant:
- Summen af alle elementer i en given række er altid en potens af 2.
- De diagonale summer af rækkerne genererer Fibonacci-sekvensen.
- Hver række svarer til koefficienterne i udvidelsen af (a+b)n.
- Hvis du kun skygger de ulige tal, danner den resulterende figur Sierpinski-trekantfraktalen.
