Pascalův trojúhelník – vzorec, vzory a příklady
Co je Pascalův trojúhelník?
Pascalův trojúhelník je trojúhelníkové pole čísel následovaných určitým vzorem a spojením s řádkem před ním. Vynalezl jej Blaise Pascal. Tento trojúhelník začíná jedním prvkem v první řadě. Poté každý řádek začíná a končí „1“.
Historie Pascalova trojúhelníku
Čínská kniha „Devět kapitol o matematickém umění“ obsahuje jeden z prvních příkladů Pascalova trojúhelníku. Kromě toho obsahuje některé ze stejných vzorů a vlastností, jaké se dnes vyskytují v trojúhelníkech.
Pascal byl jedním z několika lidí v Evropě, kteří studovali trojúhelník. Jiní matematici zkoumali podobná trojúhelníková pole čísel před ním.
Konstrukce Pascalova trojúhelníku
Konstrukce Pascalova trojúhelníku je jednoduchá. Jediné, co si musíte zapamatovat, je, že řádek začíná a končí 1. Pro zbytek čísel platí následující pravidlo:
Pro libovolný řádek r a sloupec c bude číslo součtem sloupců c-1 a c z řádku r-1.
Zde,
- r = 3,4,5….
- nac = 2,3,4,…r-1.
Zde jsou kroky k sestavení Pascalova trojúhelníku:
Krok 1) Začněme vyplněním dvou řádků.
Krok 2) Druhý prvek pro třetí řádek je součtem prvního a druhého čísla ve druhém řádku.
Krok 3) Čtvrtý řádek bude začínat "1.". Druhé číslo je 3, což je součet 1 a 2 (zvýrazněno modře).
Níže uvedený obrázek ukazuje, jak vyplnit čtvrtý řádek:
Krok 4) Pátá řada se bude skládat z pěti čísel. Vzor pro vyplnění řádků již známe z předchozích kroků.
Pascalův trojúhelníkový vzorec – binomický koeficient
Binomický koeficient je číslo, které vyjadřuje různé metody pro výběr podmnožiny k prvků z kolekce n prvků. Často se zapisuje jako „C(n,k)“ nebo „n zvolte k“.
Binomický koeficient je definován jako
"!" označuje „faktoriální“.
n! = n.(n-1). (n-2)…3.2.1
Například,
5 = 5.4.3.2.1
= 120
Řekněme tedy, že C(5,3) nebo 5 zvolí 3 = 5! / 3! (5-3)!
= 120/(12)
= 10
Metoda 1: Sestavení Pascalova trojúhelníku podle předchozí řady
Kroky v tomto postupu jsou stejné jako kroky v Pascalově trojúhelníku. Řekněme, že chceme vytvořit Pascalův trojúhelník až do sedmi řad.
Kroky, jak toho dosáhnout, jsou následující:
Krok 1) Začněte nejvyšší řádek s „1“.
Krok 2) Pro řádek „r“ bude položka „c“ součinem „c-1“ a „c“ číslem řádku „r-1“.
Krok 3) První a poslední číslo v řadě bude vždy „1“.
Abychom vytvořili Pascalův trojúhelník, musíme dodržet tyto tři snadné kroky.
C++ Kód Pascalova trojúhelníku předchozí řadou
#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 Kód vzorce Pascal Triangle 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 byl použit při realizaci. Vzhledem k tomu, že N je počet řádků v Pascalově trojúhelníku. To bude vyžadovat N2 jednotkové prostory. Proto O bude prostorová složitost (N2).
Ve funkci máme dvě smyčky a každá smyčka běží „N“ krát. Tedy i časová náročnost NA2) nebo kvadrát časové složitosti.
Metoda 2: Sestavení Pascalova trojúhelníku výpočtem binomického koeficientu
Čísla Pascalova trojúhelníku můžeme jednoduše odvodit pomocí binomického koeficientu. Zde je schéma:
Zde jsou kroky k sestavení Pascalova trojúhelníku výpočtem binomu:
Krok 1) Nejvyšší řádek bude C(0,0). Pomocí výše uvedeného vzorce pro binomický koeficient je C(0,0) = 1. Protože 0! = 1.
Krok 2) Pro řádek „i“ bude celkový počet prvků „i“. Každá položka bude vypočítána C(n,r), kde n bude i-1.
Krok 3) Opakujte krok 2 pro požadovaný počet řádků pro pascalův trojúhelník.
C++ Kód 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 Kód 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
Při realizaci byly použity tři smyčky. Jedna smyčka je pro výpočet binomického koeficientu a další dvě jsou pro vytváření čísel pro všechny řádky. Pokud jde o počet řádků, máme tři smyčky, které se provádějí „n“ krát. V důsledku toho bude celková časová složitost 0 (n3).
Prostorová složitost je nyní konstantní, protože v úložišti neuchováváme žádná data. Program vypočítá prvek a vytiskne jej v řadě. Prostorová složitost se pak sníží na 0(1).
Metoda 3: Sestavení Pascalova trojúhelníku pomocí modifikovaného binomického koeficientu
V předchozí technice jsme již viděli, jak použít binomický koeficient k výpočtu každého prvku Pascalova trojúhelníku. Tento přístup určí C(n,r) z C. (n, r-1). Zjednoduší to o jednu objednávku.
Zde jsou kroky k sestavení Pascalova trojúhelníku pomocí modifikovaného binomického koeficientu:
Krok 1) Zahajte první řádek s „1“
Krok 2) Vypočítejte C(n,r), kde „n“ je číslo řádku a „r“ je sloupec nebo prvek. Přiřaďte hodnotu do proměnné C.
Krok 3) Pro výpočet C(n,k) to bude C*(nk)/k. Nyní přiřaďte tuto hodnotu C.
Krok 4) Pokračujte krokem 3, dokud „k“ nedosáhne konce řádku. Po každé iteraci zvyšte hodnotu K o jedna.
C++ Kód pro Pascalův trojúhelník upraveným binomickým koeficientem
#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 kód pro Pascalův trojúhelník upraveným binomickým koeficientem
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 má dvě smyčky. Každá smyčka běží maximálně po dobu „n“, kde „n“ znamená počet řádků v pascalském trojúhelníku. Časová složitost tedy je Na2), čas na druhou.
Pokud jde o složitost prostoru, nepotřebovali jsme žádné pole k uložení. Právě jsme použili jednu proměnnou k zachování předchozího binomického koeficientu. Takže jsme potřebovali jen jedno místo navíc. Vesmírná složitost se stala O (1).
Aplikace Pascalova trojúhelníku
Zde jsou některé aplikace Pascalova trojúhelníku:
Binomické rozšíření: Koeficient binomických rozšíření můžeme určit 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í: Viděli jsme, že prvky Pascalova trojúhelníku jsou ekvivalentní binomickým koeficientům. Například, pokud máte 6 míčků a byli jste požádáni, abyste si vybrali 3 míče, bude to tak 6C3. Nebo můžete číslo najít ve 3. prvku 6. řady z Pascalova trojúhelníku.
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 řadě je vždy mocninou 2.
- Diagonální součet prvků řádků generuje Fibonacciho posloupnost.
Shrnutí
- Pascalův trojúhelník udává koeficienty pro binomické expanze.
- Každá řada Pascalova trojúhelníku začíná a končí „1“. Mezihodnoty jsou součtem dvou prvků předchozího řádku.
- Diagonální přidání všech prvků v Pascalově trojúhelníku vám dá Fibonacciho sekvence.
- Pascalův trojúhelník lze také generovat pomocí binomických koeficientů.