Formule van de driehoek van Pascal met voorbeelden
Redactie
⚡ Slimme samenvatting
De driehoek van Pascal is een driehoekige getallenreeks waarbij elke waarde gelijk is aan de som van de twee getallen die er direct boven staan. Dit onthult diepgaande patronen in combinatoriek, binominale expansies en kansrekening die wiskundigen al eeuwenlang fascineren.
Wat is de driehoek van Pascal?
De driehoek van Pascal is een driehoekige reeks getallen die een eenvoudig patroon volgt op basis van de rij erboven. Hij werd in de 17e eeuw populair gemaakt door de Franse wiskundige Blaise Pascal. De driehoek begint met een enkele "1" bovenaan, en elke volgende rij begint en eindigt ook met een "1".
Naast zijn elegante vorm, bevat de driehoek van Pascal diepgaande wiskundige verbanden. Hij is nauw verbonden met de binomiaalstelling, combinatorisch tellen en kansrekening, en daarom komt hij wereldwijd voor in lessen algebra, statistiek en informatica.
Pascal's driehoeksgeschiedenis
Hoewel de driehoek naar Blaise Pascal is vernoemd, bestond hij al eeuwen vóór hem. De Chinese wiskundige tekst "De Negen Hoofdstukken over de Wiskundige Kunst" bevat een van de vroegst bekende voorbeelden, met veel van dezelfde patronen die we vandaag de dag nog steeds gebruiken.
De Perzische wiskundige Al-Karaji en de Indiase geleerde PingAla onderzocht ook soortgelijke structuren. Pascal formaliseerde de eigenschappen van de driehoek in zijn verhandeling "Traité du triangle arithmétique" uit 1654, die de structuur haar moderne naam in de westerse wiskunde gaf.
Constructie van de driehoek van Pascal
Het construeren van de driehoek van Pascal is eenvoudig. De enige regel die je moet onthouden is dat elke rij begint en eindigt met 1, en dat elk ander getal wordt opgebouwd uit de rij erboven.
Voor elke rij r en kolom c is de waarde gelijk aan de som van de getallen in de kolommen c-1 en c van rij r-1.
Hier
- r = 3, 4, 5, …
- n en c = 2, 3, 4, …, r-1.
Hieronder volgen de stappen om de driehoek van Pascal te construeren:
Stap 1) Begin met het invullen van de eerste twee rijen.
Stap 2) Het tweede element van de derde rij 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 afbeelding hieronder laat zien hoe je de vierde rij invult:
Stap 4) De vijfde rij bestaat uit vijf getallen. Het patroon voor het vullen van rijen kennen we al uit de voorgaande stappen.
Pascal's driehoeksformule - Binominale coëfficiënt
Een binomiaalcoëfficiënt telt het aantal manieren om een subset van k elementen te kiezen uit een verzameling van n elementen. Het wordt vaak geschreven als "C(n, k)" of "n kies k".
De binomiaalcoëfficiënt wordt als volgt gedefinieerd:
Het symbool “!” geeft de faculteit van een getal aan.
n! = n.(n-1).(n-2)…3.2.1
Bijvoorbeeld
5! = 5.4.3.2.1
= 120
Dus C(5, 3) of “5 kies 3” = 5! / 3!(5-3)!
= 120 / 12
= 10
Methode 1: De driehoek van Pascal opbouwen met behulp van de vorige rij.
De procedure hier is vergelijkbaar met hoe we de driehoek handmatig hebben getekend. Stel dat we de driehoek van Pascal tot zeven rijen willen genereren.
De stappen die je daarvoor moet volgen zijn als volgt:
Stap 1) Begin de bovenste rij met “1”.
Stap 2) Voor rij “r” is element “c” de som van kolom “c-1” en kolom “c” van rij “r-1”.
Stap 3) Het eerste en laatste getal in elke rij zullen altijd "1" zijn.
Door deze drie eenvoudige stappen te volgen, kunnen we de hele driehoek systematisch construeren.
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 de formule van de driehoek van Pascal 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 wordt in deze implementatie gebruikt. Aangezien N het aantal rijen in de driehoek van Pascal is, vereist dit N2 eenheidsruimtes. Daarom is de ruimtecomplexiteit O(N).2).
De functie maakt gebruik van twee geneste lussen, die elk tot "N" keer worden uitgevoerd. De tijdscomplexiteit is dus ook AAN2), oftewel de tijdcomplexiteit in het kwadraat.
Methode 2: De driehoek van Pascal construeren door de binominale coëfficiënt te berekenen
We kunnen de getallen van de driehoek van Pascal rechtstreeks afleiden met behulp van binominale coëfficiënten. Het onderstaande diagram illustreert de relatie:
Hieronder volgen de stappen om de driehoek van Pascal te construeren door de binomiaalcoëfficiënt te berekenen:
Stap 1) De bovenste rij is C(0, 0). Met behulp van de bovenstaande formule is C(0, 0) = 1, omdat 0! = 1.
Stap 2) Voor rij "i" zullen er in totaal "i" elementen zijn. Elk item wordt berekend als C(n, r), waarbij n gelijk is aan i-1.
Stap 3) Herhaal stap 2 voor zoveel rijen van de driehoek van Pascal als je wilt genereren.
C++ Code De driehoek van Pascal met behulp van de binomiaalcoë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 Code De driehoek van Pascal met behulp van de binomiaalcoë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
In deze implementatie worden drie lussen gebruikt: één om de binomiaalcoëfficiënt te berekenen en twee om door elke rij en kolom te itereren. Afhankelijk van het aantal rijen worden alle drie de lussen maximaal "n" keer uitgevoerd. Bijgevolg is de totale tijdscomplexiteit O(n).3).
De ruimtecomplexiteit is constant omdat we geen tussenresultaten opslaan. Het programma berekent elk element direct en print het binnen een regel, waardoor de ruimtecomplexiteit afneemt tot... O (1).
Methode 3: De driehoek van Pascal bouwen door gemodificeerde binomiale coëfficiënt
Bij de vorige techniek gebruikten we de binominale coëfficiëntformule om elk element te berekenen. De aangepaste aanpak leidt C(n, r) rechtstreeks af uit C(n, r-1), waardoor de hoeveelheid werk met een factor tien wordt verminderd.
Hieronder volgen de stappen om de driehoek van Pascal te construeren met behulp van de aangepaste binomiaalcoëfficiënt:
Stap 1) Begin de eerste rij met “1”.
Stap 2) Bereken C(n, r), waarbij "n" het rijnummer en "r" de kolomindex is. Wijs die waarde toe aan een variabele C.
Stap 3) Gebruik voor het berekenen van de volgende coëfficiënt C * (n – k) / k. Wijs deze nieuwe waarde weer toe aan C.
Stap 4) Ga door met stap 3 totdat "k" het einde van de rij bereikt. Verhoog k na elke iteratie met één.
C++ Code voor de driehoek van Pascal met behulp van de aangepaste binomiaalcoë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 met behulp van de aangepaste binomiaalcoë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 maakt gebruik van twee lussen, die elk maximaal "n" keer worden uitgevoerd, waarbij "n" het aantal rijen in de driehoek is. De tijdscomplexiteit is dus Aan2), kwadratische tijd.
Wat de ruimtecomplexiteit betreft, hebben we geen array nodig voor opslag. We gebruiken slechts één variabele om de vorige binominale coëfficiënt bij te houden, dus we hebben maar één extra ruimte nodig. De ruimtecomplexiteit is daarom O (1).
Toepassing van de driehoek van Pascal
Hieronder volgen enkele praktische toepassingen van de driehoek van Pascal:
Binominale uitbreidingen: De coëfficiënten van elke binominale expansie kunnen direct worden afgelezen uit 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: De elementen van de driehoek van Pascal corresponderen rechtstreeks met binominale coëfficiënten. Als je bijvoorbeeld 6 ballen hebt en er 3 wilt kiezen, is het antwoord: 6C3Die waarde vind je in het derde element van de zesde rij van de driehoek van Pascal.
Waarschijnlijkheid: De driehoek van Pascal wordt veel gebruikt om kansen te berekenen bij het opgooien van munten, dobbelproblemen en andere combinatorische gebeurtenissen waarbij elke uitkomst overeenkomt met een binomiale verdeling.
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 in een rij is altijd een macht van 2.
- De sommen van de diagonalen van de rijen vormen de Fibonacci-reeks.
- Elke rij komt overeen met de coëfficiënten in de expansie van (a+b).n.
- Als je alleen de oneven getallen inkleurt, vormt de resulterende figuur de Sierpinski-driehoekfractal.
