Pascals trekant – formel, mønstre og eksempler
Sarah Chen
Hvad er Pascals trekant?
Pascals trekant er en trekantet række af tal efterfulgt af et bestemt mønster og forbindelse til rækken før den. Det blev opfundet af Blaise Pascal. Denne trekant starter med et element i den første række. Derefter starter og slutter hver række med "1".
Pascals trekanthistorie
Den kinesiske bog "De ni kapitler om matematisk kunst" indeholder et af de første eksempler på Pascals trekant. Derudover indeholder den nogle af de samme mønstre og kvaliteter, som findes i trekanter i dag.
Pascal var en af flere mennesker i Europa, der studerede trekanten. Andre matematikere havde undersøgt lignende trekantede rækker af tal før ham.
Konstruktion af Pascals trekant
Det er enkelt at konstruere Pascals trekant. Det eneste du skal huske er, at rækken starter og slutter med 1. Reglen for resten af tallene er som følger:
For enhver række r og kolonne c vil tallet være summen af kolonne c-1 og c fra række r-1.
Her,
- r = 3,4,5….
- n og c = 2,3,4,…r-1.
Her er trin til at bygge Pascals trekant:
Trin 1) Lad os begynde med at fylde to rækker ud.
Trin 2) Det andet element for den tredje linje er summen af det første og andet tal i den anden række.
Trin 3) Den fjerde række begynder med "1". Det andet tal er 3, som er summen af 1 og 2 (markeret med blåt).
Billedet nedenfor viser, hvordan du udfylder den fjerde række:
Trin 4) Den femte række vil bestå af fem numre. Vi kender allerede mønsteret for at udfylde rækkerne fra de tidligere trin.
Pascals trekantformel – binomial koefficient
En binomial koefficient er et tal, der udtrykker forskellige metoder til at vælge en delmængde af k elementer fra en samling af n elementer. Ofte skrives det som "C(n,k)" eller "n vælg k."
Den binomiale koefficient er defineret som
Det "!" betegner det "faktorielle".
n! = n.(n-1). (n-2)...3.2.1
For eksempel:
5! = 5.4.3.2.1
= 120
Så lad os sige C(5,3) eller 5, vælg 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metode 1: Byg Pascals trekant efter den forrige række
Trinene i denne procedure er de samme som dem i Pascals trekant. Lad os sige, at vi vil skabe Pascals trekant op til syv rækker.
Trinene til at opnå det er som følger:
Trin 1) Start den øverste række med "1".
Trin 2) For rækken "r", vil "c"-elementet være produktet af "c-1" og "c" nummeret på "r-1"-rækken.
Trin 3) Det første og sidste tal i en række vil altid være "1".
Vi skal overholde disse tre nemme trin for at skabe Pascals trekant.
C++ Kode for Pascals trekant af 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 Kode for Pascal-trekantformel af 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 blev brugt i implementeringen. Givet at N er antallet af rækker i Pascals trekant. Dette vil kræve N2 enhedspladser. Derfor vil O være rummets kompleksitet (N2).
Vi har to loops i funktionen, og hver loop kører "N" gange. Så det er tidskompleksiteten også PÅ2) eller kvadreret tidskompleksitet.
Metode 2: Byg Pascals trekant ved at beregne binomial koefficient
Vi kan simpelthen udlede antallet af pascals trekant ved hjælp af den binomiale koefficient. Her er diagrammet:
Her er trinene til at bygge Pascals trekant ved at beregne binomialet:
Trin 1) Den øverste række vil være C(0,0). Ved at bruge formlen ovenfor for den binomiale koefficient, C(0,0) = 1. Fordi 0! = 1.
Trin 2) For række "i" vil der være samlede "i"-elementer. Hvert element vil blive beregnet C(n,r), hvor n vil være i-1.
Trin 3) Gentag trin 2 for det antal rækker, du ønsker til pascals trekant.
C++ Kod Pascals trekant ved binomial koefficient
#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 Kod Pascals trekant ved binomial koefficient
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 sløjfer blev brugt i implementeringen. Den ene løkke er til at beregne binomialkoefficienten, og de to andre er til at skabe tal for alle rækker. Med hensyn til antallet af rækker har vi tre sløjfer, der udfører "n" gange. Som følge heraf vil den samlede tidskompleksitet være 0(n3).
Rumkompleksiteten er nu konstant, fordi vi ikke opbevarer nogen data. Programmet beregner elementet, og det udskrives i en række. Rumkompleksiteten falder derefter til 0(1).
Metode 3: Opbygning af Pascals trekant ved modificeret binomial koefficient
I den foregående teknik har vi allerede set, hvordan man bruger en binomial koefficient til at beregne hvert element i Pascals trekant. Denne tilgang vil bestemme C(n,r) fra C. (n, r-1). Det vil forenkle tingene med én ordre.
Her er trinene til at bygge Pascals trekant ved modificeret binomial 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 kolonnen eller elementet. Tildel værdien i en variabel C.
Trin 3) Til beregning af C(n,k) vil det være C*(nk)/k. Tildel nu denne værdi til C.
Trin 4) Fortsæt trin 3, indtil "k" når slutningen af rækken. Efter hver iteration øges værdien af K med én.
C++ Kode for Pascals trekant af modificeret binomial koefficient
#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 kode for Pascals trekant ved modificeret binomial koefficient
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 har to sløjfer. Hver sløjfe løber maksimalt "n" tid, hvor "n" betyder antallet af rækker i pascaltrekanten. Så tidskompleksiteten er På2), kvadreret tid.
Med hensyn til pladsens kompleksitet behøvede vi ikke noget array at opbevare. Vi brugte bare en variabel til at beholde den tidligere binomiale koefficient. Så vi havde bare brug for en ekstra plads. Rumkompleksiteten blev O (1).
Anvendelse af Pascals trekant
Her er nogle anvendelser af Pascals trekant:
Binomiale udvidelser: Vi kan bestemme koefficienten for de binomiale udvidelser ud 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: Vi har set elementer i Pascals trekant svarer til binomiale koefficienter. Hvis du for eksempel har 6 bolde og er blevet bedt om at vælge 3 bolde, bliver det det 6C3. Eller du kan finde tallet i det 3. element i 6. række fra pascals trekant.
Interessante fakta om Pascals trekant
Her er nogle fakta, du vil finde interessante om Pascals trekant:
- Summen af alle elementer i en række er altid potensen af 2.
- Diagonalt genererer summen af elementerne i rækkerne Fibonacci-sekvensen.
Resumé
- Pascals trekant giver koefficienterne for de binomiale udvidelser.
- Hver række af pascals trekant starter og slutter med "1". De mellemliggende værdier er summen af to elementer i den foregående række.
- Diagonal tilføjelse af alle elementerne i pascals trekant vil give dig Fibonacci sekvens.
- Pascals trekant kan også genereres med binomiale koefficienter.
