Pascalův trojúhelníkový vzorec s příklady
Sarah Chen
⚡ Chytré shrnutí
Pascalův trojúhelník je trojúhelníkové uspořádání čísel, kde každá hodnota se rovná součtu dvou čísel přímo nad ní, což odhaluje hluboké vzorce v kombinatorice, binomických rozvojích a pravděpodobnosti, které fascinují matematiky po staletí.
Co je Pascalův trojúhelník?
Pascalův trojúhelník je trojúhelníkové pole čísel, které se řídí jednoduchým vzorem založeným na řádku nad ním. Zpopularizoval ho francouzský matematik Blaise Pascal v 17. století. Trojúhelník začíná jednou „jedničkou“ nahoře a každý následující řádek také začíná a končí „jedničkou“.
Pascalův trojúhelník kromě svého elegantního tvaru kóduje hluboké matematické vztahy. Je úzce spjat s binomickou větou, kombinatorickým počítáním a pravděpodobností, a proto se objevuje v učebnách algebry, statistiky a informatiky po celém světě.
Historie Pascalova trojúhelníku
Ačkoli byl trojúhelník pojmenován po Blaise Pascalovi, předchází ho o staletí. Čínský matematický text „Devět kapitol o matematickém umění“ obsahuje jeden z nejstarších známých příkladů, který zobrazuje mnoho stejných vzorů, jaké používáme dnes.
Perský matematik Al-Karaji a indický učenec PingAla také zkoumala podobná pole. Pascal formalizoval vlastnosti trojúhelníku ve svém pojednání z roku 1654 „Traité du triangle arithmétique“, které dalo této struktuře její moderní název v západní matematice.
Konstrukce Pascalova trojúhelníku
Sestrojení Pascalova trojúhelníku je jednoduché. Jediné pravidlo, které je třeba si pamatovat, je, že každý řádek začíná a končí jedničkou a každé další číslo se sestavuje z řádku výše.
Pro libovolný řádek r a sloupec c se hodnota rovná součtu čísel ve sloupcích c-1 a c řádku r-1.
Zde,
- r = 3, 4, 5, …
- n a c = 2, 3, 4, …, r-1.
Zde jsou kroky k sestavení Pascalova trojúhelníku:
Krok 1) Začněte vyplněním prvních dvou řádků.
Krok 2) Druhý prvek třetího řádku je součtem prvního a druhého čísla ve druhém řádku.
Krok 3) Čtvrtý řádek začíná číslem „1“. Druhé číslo je 3, což je součet čísel 1 a 2 (zvýrazněno modře).
Obrázek níže ukazuje, jak vyplnit čtvrtý řádek:
Krok 4) Pátý řádek se skládá z pěti čísel. Vzor pro vyplňování řádků již známe z předchozích kroků.
Pascalův trojúhelníkový vzorec – binomický koeficient
Binomický koeficient udává počet způsobů, jak vybrat podmnožinu k prvků z kolekce n prvků. Obvykle se zapisuje jako „C(n, k)“ nebo „n vybere k“.
Binomický koeficient je definován jako:
Symbol „!“ označuje faktoriál čísla.
n! = n.(n-1)(n-2)…3.2.1
Například,
5 = 5.4.3.2.1
= 120
Takže C(5, 3) neboli „5 vybere 3“ = 5! / 3!(5-3)!
= 120 / 12
= 10
Metoda 1: Sestavení Pascalova trojúhelníku podle předchozí řady
Postup zde odráží, jak jsme trojúhelník kreslili ručně. Předpokládejme, že chceme vygenerovat Pascalův trojúhelník až do sedmi řádků.
Postupujte takto:
Krok 1) Začněte nejvyšší řádek číslem „1“.
Krok 2) Pro řádek „r“ bude prvek „c“ součtem sloupce „c-1“ a sloupce „c“ řádku „r-1“.
Krok 3) První a poslední číslo v každém řádku bude vždy „1“.
Dodržení těchto tří jednoduchých kroků nám umožní systematicky sestrojit celý trojúhelník.
C++ Code Pascalova trojúhelníku podle předchozího řádku
#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); }
Výstup:
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 Vzorec Pascalova trojúhelníku podle předchozího řádku
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)
Výstup příkladu Pascalova trojúhelníku:
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
Analýza složitosti
A dvourozměrné pole je použit v této implementaci. Vzhledem k tomu, že N je počet řádků v Pascalově trojúhelníku, vyžaduje to N2 jednotkové prostory. Prostorová složitost je tedy O(N2).
Funkce používá dvě vnořené smyčky, každá běží až „N“krát. Časová složitost je tedy také NA2), neboli druhá mocnina časové složitosti.
Metoda 2: Sestavení Pascalova trojúhelníku výpočtem binomického koeficientu
Čísla Pascalova trojúhelníku můžeme odvodit přímo pomocí binomických koeficientů. Níže uvedený diagram ilustruje vztah:
Zde jsou kroky k sestavení Pascalova trojúhelníku výpočtem binomického koeficientu:
Krok 1) Horní řádek je C(0, 0). Podle výše uvedeného vzorce je C(0, 0) = 1, protože 0! = 1.
Krok 2) Pro řádek „i“ bude celkem „i“ prvků. Každá položka se vypočítá jako C(n, r), kde n je i-1.
Krok 3) Krok 2 opakujte pro tolik řádků Pascalova trojúhelníku, kolik chcete vygenerovat.
C++ Code Pascalův trojúhelník pomocí binomického koeficientu
#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); }
Výstup:
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 Pascalův trojúhelník pomocí binomického koeficientu
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)
Výstup příkladu Pascalova trojúhelníku:
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
Analýza složitosti
V této implementaci se používají tři smyčky: jedna pro výpočet binomického koeficientu a další dvě pro iteraci každým řádkem a sloupcem. Vzhledem k počtu řádků se všechny tři smyčky opakují až „n“krát. Celková časová složitost je tedy O(n3).
Prostorová složitost je konstantní, protože neukládáme žádné mezivýsledky. Program počítá každý prvek za chodu a vypisuje ho v rámci řádku, takže prostorová složitost se snižuje na O (1).
Metoda 3: Sestavení Pascalova trojúhelníku pomocí modifikovaného binomického koeficientu
V předchozí technice jsme k výpočtu každého prvku použili vzorec pro binomické koeficienty. Modifikovaný přístup odvozuje C(n, r) přímo z C(n, r-1), čímž se práce snižuje o řád.
Zde jsou kroky pro sestavení Pascalova trojúhelníku pomocí modifikovaného binomického koeficientu:
Krok 1) První řádek začněte číslicí „1“.
Krok 2) Vypočítejte C(n, r), kde „n“ je číslo řádku a „r“ je index sloupce. Přiřaďte tuto hodnotu proměnné C.
Krok 3) Pro výpočet dalšího koeficientu použijte C * (n – k) / k. Tuto novou hodnotu přiřaďte zpět k C.
Krok 4) Pokračujte v kroku 3, dokud „k“ nedosáhne konce řádku. Po každé iteraci zvyšte k o jedna.
C++ Code pro Pascalův trojúhelník pomocí modifikovaného binomického koeficientu
#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); }
Výstup:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code pro Pascalův trojúhelník pomocí modifikovaného binomického koeficientu
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)
Výstup vzorů Pascalova trojúhelníku:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Analýza složitosti
Implementace používá dvě smyčky, každá z nich běží maximálně „n“krát, kde „n“ je počet řádků v trojúhelníku. Časová složitost je tedy Na2), čas na druhou.
Co se týče prostorové složitosti, nepotřebujeme žádné pole pro ukládání. Používáme pouze jednu proměnnou pro zachování předchozího binomického koeficientu, takže potřebujeme jen jeden další prostor. Prostorová složitost je tedy O (1).
Aplikace Pascalova trojúhelníku
Zde je několik praktických aplikací Pascalova trojúhelníku:
Binomické rozšíření: Koeficienty libovolného binomického rozvoje lze odečíst přímo z Pascalova trojúhelníku. Zde je příklad:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2a + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3a + 6x2y2 + 4xy3 + 1y4 |
Výpočet kombinací: Prvky Pascalova trojúhelníku přímo odpovídají binomickým koeficientům. Například pokud máte 6 míčků a chcete si vybrat 3, odpověď je 6C3Tuto hodnotu najdete ve 3. prvku 6. řádku Pascalova trojúhelníku.
Pravděpodobnost: Pascalův trojúhelník se široce používá k výpočtu pravděpodobností v hodech mincí, úlohách s kostkami a dalších kombinatorických událostech, kde každý výsledek odpovídá binomickému rozdělení.
Zajímavá fakta o Pascalově trojúhelníku
Zde jsou některá zajímavá fakta o Pascalově trojúhelníku:
- Součet všech prvků v libovolném řádku je vždy mocninou čísla 2.
- Diagonální součty řádků generují Fibonacciho posloupnost.
- Každý řádek odpovídá koeficientům v rozvoji (a+b)n.
- Pokud vystínujete pouze lichá čísla, výsledný obrazec vytvoří fraktál Sierpinského trojúhelníku.
