Pascal's Triangle - Formule, patronen en voorbeelden
Sara Chen
Wat is de driehoek van Pascal?
De driehoek van Pascal is een driehoekige reeks getallen gevolgd door een bepaald patroon en verbinding met de rij ervoor. Het werd uitgevonden door Blaise Pascal. Deze driehoek begint met één element in de eerste rij. Daarna begint en eindigt elke rij met "1".
Pascal's driehoeksgeschiedenis
Het Chinese boek “The Nine Chapters on the Mathematical Art” bevat een van de eerste voorbeelden van de Driehoek van Pascal. Bovendien bevat het enkele van dezelfde patronen en kwaliteiten die tegenwoordig in driehoeken voorkomen.
Pascal was een van de vele mensen in Europa die de driehoek bestudeerden. Andere wiskundigen hadden soortgelijke driehoekige arrays van getallen vóór hem onderzocht.
Constructie van de driehoek van Pascal
Het construeren van de driehoek van Pascal is eenvoudig. Het enige dat u moet onthouden is dat de rij begint en eindigt met 1. De regel voor de rest van de getallen is als volgt:
Voor elke rij r en kolom c is het getal de som van de kolommen c-1 en c uit rij r-1.
Hier
- r=3,4,5….
- n en c = 2,3,4,…r-1.
Hier zijn stappen om de driehoek van Pascal te bouwen:
Stap 1) Laten we beginnen met het invullen van twee rijen.
Stap 2) Het tweede element voor de derde regel is de som van het eerste en tweede getal in de tweede rij.
Stap 3) De vierde rij begint met “1.”. Het tweede getal is 3, wat de som is van 1 en 2 (blauw gemarkeerd).
De onderstaande afbeelding laat zien hoe u de vierde rij vult:
Stap 4) De vijfde rij zal bestaan uit vijf getallen. We kennen het patroon voor het vullen van de rijen al uit de eerdere stappen.
Pascal's driehoeksformule - Binominale coëfficiënt
Een binomiale coëfficiënt is een getal dat verschillende methoden uitdrukt om een subset van k elementen te selecteren uit een verzameling van n elementen. Vaak wordt het geschreven als “C(n,k)” of “n kies k.”
De binomiale coëfficiënt wordt gedefinieerd als
De "!" duidt de ‘faculteit’ aan.
N! = n.(n-1). (n-2)…3.2.1
Bijvoorbeeld
5! = 5.4.3.2.1
= 120
Dus laten we zeggen C(5,3) of 5, kies 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Methode 1: Bouw de driehoek van Pascal op basis van de vorige rij
De stappen in deze procedure zijn dezelfde als die in de driehoek van Pascal. Laten we zeggen dat we de driehoek van Pascal tot zeven rijen willen maken.
De stappen om dit te bereiken zijn als volgt:
Stap 1) Begin de bovenste rij met “1”.
Stap 2) Voor de rij “r” zal “c” het product zijn van “c-1” en “c” het nummer van de “r-1” rij.
Stap 3) Het eerste en laatste getal in een rij zijn altijd "1".
We moeten deze drie eenvoudige stappen volgen om de driehoek van Pascal te creëren.
C++ Code van de driehoek van Pascal door de vorige rij
#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 van Pascal-driehoekformule door de vorige rij
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)
Pascal's driehoek Voorbeelduitvoer:
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
Complexiteitsanalyse
A tweedimensionale array werd gebruikt bij de uitvoering. Gegeven dat N het aantal rijen in de driehoek van Pascal is. Hiervoor is N nodig2 eenheidsruimten. Daarom zal O de ruimtecomplexiteit zijn (N2).
We hebben twee lussen in de functie, en elke lus loopt voor "N" keer. Dus de tijdcomplexiteit is ook AAN2) of kwadratische tijdcomplexiteit.
Methode 2: De driehoek van Pascal bouwen door de binomiale coëfficiënt te berekenen
We kunnen de getallen van Pascal's driehoek eenvoudig afleiden met behulp van de binominale coëfficiënt. Hier is het diagram:
Hier zijn de stappen om de driehoek van Pascal te bouwen door de binominale waarde te berekenen:
Stap 1) De bovenste rij is C(0,0). Gebruik de bovenstaande formule voor de binomiale coëfficiënt: C(0,0) = 1. Omdat 0! = 1.
Stap 2) Voor rij “i” zijn er totale “i”-elementen. Elk item wordt berekend als C(n,r), waarbij n gelijk is aan i-1.
Stap 3) Herhaal stap 2 voor het aantal rijen dat je wilt voor de driehoek van Pascal.
C++ Codeer de driehoek van Pascal met binomiale coëfficiënt
#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 Codeer de driehoek van Pascal met binomiale coëfficiënt
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)
Pascal's driehoek Voorbeelduitvoer:
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
Complexiteitsanalyse
Er zijn drie lussen gebruikt in de implementatie. Eén lus is voor het berekenen van de binominale coëfficiënt en de andere twee zijn voor het maken van getallen voor alle rijen. Wat betreft het aantal rijen, hebben we drie lussen die "n" keer worden uitgevoerd. Bijgevolg zal de algehele tijdcomplexiteit 0(n3).
De ruimtecomplexiteit is nu constant omdat we geen gegevens in opslag bewaren. Het programma berekent het element en het wordt in een rij afgedrukt. De ruimtecomplexiteit neemt vervolgens af tot 0(1).
Methode 3: De driehoek van Pascal bouwen door gemodificeerde binomiale coëfficiënt
In de vorige techniek hebben we al gezien hoe we een binominale coëfficiënt kunnen gebruiken om elk element van de driehoek van Pascal te berekenen. Deze benadering zal C(n,r) bepalen uit C. (n, r-1). Het zal de zaken met één bestelling vereenvoudigen.
Hier zijn de stappen om de driehoek van Pascal te bouwen met behulp van de gemodificeerde binomiale coëfficiënt:
Stap 1) Begin de eerste rij met “1”
Stap 2) Bereken C(n,r), waarbij “n” het rijnummer is en “r” de kolom of het element is. Wijs de waarde toe aan een variabele C.
Stap 3) Voor het berekenen van C(n,k) zal dit C*(nk)/k zijn. Wijs deze waarde nu toe aan C.
Stap 4) Ga door met stap 3 totdat “k” het einde van de rij bereikt. Na elke iteratie verhoogt u de waarde van K met één.
C++ Codeer voor de driehoek van Pascal met gewijzigde binomiale coëfficiënt
#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 voor de driehoek van Pascal door gewijzigde binomiale coëfficiënt
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)
Uitvoer van Pascal's driehoekspatronen:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Complexiteitsanalyse
De implementatie heeft twee lussen. Elke lus loopt maximaal "n" keer, waarbij "n" het aantal rijen in de pascaldriehoek betekent. De tijdcomplexiteit is dus Aan2), kwadratische tijd.
Wat betreft de ruimtecomplexiteit, we hadden geen array nodig om op te slaan. We gebruikten gewoon één variabele om de vorige binominale coëfficiënt te behouden. Dus we hadden gewoon één extra ruimte nodig. De ruimtecomplexiteit werd O (1).
Toepassing van de driehoek van Pascal
Hier zijn enkele toepassingen van de driehoek van Pascal:
Binominale uitbreidingen: We kunnen de coëfficiënt van de binomiale uitbreidingen bepalen op basis van de driehoek van Pascal. Hier is een voorbeeld:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2en + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3en + 6x2y2 + 4xy3 + 1y4 |
Combinaties berekenen: We hebben gezien dat elementen van de driehoek van Pascal gelijkwaardig zijn aan binomiale coëfficiënten. Als je bijvoorbeeld 6 ballen hebt en er wordt je gevraagd om 3 ballen te kiezen, dan is dat zo 6C3. Of je kunt het nummer vinden in het 3e element van de 6e rij uit de driehoek van Pascal.
Interessante feiten over de driehoek van Pascal
Hier zijn enkele feiten die u interessant zult vinden over de driehoek van Pascal:
- De som van alle elementen op een rij is altijd de macht van 2.
- De diagonale som van de elementen van de rijen genereert de Fibonacci-reeks.
Samenvatting
- De driehoek van Pascal geeft de coëfficiënten voor de binominale uitbreidingen.
- Elke rij van de driehoek van Pascal begint en eindigt met “1”. De tussenliggende waarden zijn de som van twee elementen uit de vorige rij.
- Door alle elementen in de driehoek van Pascal diagonaal op te tellen, krijgt u de Fibonacci-reeks.
- De driehoek van Pascal kan ook worden gegenereerd met binominale coëfficiënten.
