Pascalova formula trokuta s primjerima
Uredništvo
⚡ Pametni sažetak
Pascalov trokut je trokutasti raspored brojeva gdje je svaka vrijednost jednaka zbroju dvaju brojeva neposredno iznad nje, otkrivajući duboke obrasce u kombinatorici, binomnim ekspanzijama i vjerojatnosti koji su fascinirali matematičare stoljećima.
Što je Pascalov trokut?
Pascalov trokut je trokutasti niz brojeva koji slijedi jednostavan uzorak na temelju retka iznad njega. Popularizirao ga je francuski matematičar Blaise Pascal u 17. stoljeću. Trokut počinje s jednom "1" na vrhu, a svaki sljedeći redak također počinje i završava s "1".
Osim elegantnog oblika, Pascalov trokut kodira duboke matematičke odnose. Usko je povezan s binomnim teoremom, kombinatornim brojanjem i vjerojatnošću, zbog čega se pojavljuje u učionicama algebre, statistike i informatike diljem svijeta.
Povijest Pascalovog trokuta
Iako je nazvan po Blaiseu Pascalu, trokut mu prethodi stoljećima. Kineski matematički tekst „Devet poglavlja o matematičkoj umjetnosti“ sadrži jedan od najranijih poznatih primjera, koji prikazuje mnoge iste obrasce koje koristimo danas.
Perzijski matematičar Al-Karaji i indijski učenjak Pingala je također istraživala slične nizove. Pascal je formalizirao svojstva trokuta u svojoj raspravi iz 1654. "Traité du triangle arithmétique", koja je strukturi dala moderno ime u zapadnoj matematici.
Konstrukcija Pascalovog trokuta
Konstrukcija Pascalovog trokuta je jednostavna. Jedino pravilo koje treba zapamtiti je da svaki redak počinje i završava s brojem 1, a svaki drugi broj se gradi iz retka iznad.
Za bilo koji redak r i stupac c, vrijednost je jednaka zbroju brojeva u stupcima c-1 i c retka r-1.
Ovdje,
- r = 3, 4, 5, …
- n i c = 2, 3, 4, …, r-1.
Evo koraka za izgradnju Pascalovog trokuta:
Korak 1) Počnite popunjavanjem prva dva reda.
Korak 2) Drugi element trećeg retka je zbroj prvog i drugog broja u drugom retku.
Korak 3) Četvrti redak počinje s „1“. Drugi broj je 3, što je zbroj brojeva 1 i 2 (označeno plavom bojom).
Donja slika prikazuje kako popuniti četvrti red:
Korak 4) Peti red sastoji se od pet brojeva. Uzorak za popunjavanje redova već znamo iz prethodnih koraka.
Formula Pascalovog trokuta – Binomni koeficijent
Binomni koeficijent broji koliko načina možemo odabrati podskup od k elemenata iz skupa od n elemenata. Obično se piše kao „C(n, k)“ ili „n bira k“.
Binomni koeficijent definiran je kao:
Simbol "!" označava faktorijel broja.
n! = n.(n-1)(n-2)…3.2.1
Na primjer,
5! = 5.4.3.2.1
= 120
Dakle, C(5, 3) ili „5 odaberi 3“ = 5! / 3!(5-3)!
= 120/12
= 10
Metoda 1: Izgradnja Pascalovog trokuta prema prethodnom retku
Postupak ovdje odražava kako smo ručno crtali trokut. Pretpostavimo da želimo generirati Pascalov trokut do sedam redaka.
Koraci za to su sljedeći:
Korak 1) Započnite najgornji redak s "1".
Korak 2) Za redak „r“, element „c“ bit će zbroj stupca „c-1“ i stupca „c“ retka „r-1“.
Korak 3) Prvi i zadnji broj u svakom retku uvijek će biti "1".
Slijedeći ova tri jednostavna koraka, sustavno ćemo konstruirati cijeli trokut.
C++ Code Pascalovog trokuta po prethodnom retku
#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); }
Izlaz:
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 Formula Pascalovog trokuta prema prethodnom retku
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)
Izlaz primjera Pascalovog trokuta:
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
Analiza složenosti
A dvodimenzionalni niz se koristi u ovoj implementaciji. S obzirom na to da je N broj redaka u Pascalovom trokutu, to zahtijeva N2 jedinični prostori. Stoga je složenost prostora O(N2).
Funkcija koristi dvije ugniježđene petlje, svaka se izvršava do "N" puta. Dakle, vremenska složenost je također NA2), ili kvadrat vremenske složenosti.
Metoda 2: Izgradnja Pascalovog trokuta izračunavanjem binomnog koeficijenta
Brojeve Pascalovog trokuta možemo izvesti izravno pomoću binomnih koeficijenata. Dijagram u nastavku ilustrira odnos:
Evo koraka za izgradnju Pascalovog trokuta izračunavanjem binomnog koeficijenta:
Korak 1) Najgornji redak je C(0, 0). Koristeći gornju formulu, C(0, 0) = 1, jer 0! = 1.
Korak 2) Za redak "i" bit će ukupno "i" elemenata. Svaka stavka se izračunava kao C(n, r), gdje je n i-1.
Korak 3) Ponovite korak 2 za onoliko redaka Pascalovog trokuta koliko želite generirati.
C++ Code Pascalov trokut pomoću binomnog koeficijenta
#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); }
Izlaz:
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 Pascalov trokut pomoću binomnog koeficijenta
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)
Izlaz primjera Pascalovog trokuta:
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
Analiza složenosti
U ovoj implementaciji koriste se tri petlje: jedna za izračunavanje binomnog koeficijenta i još dvije za iteraciju kroz svaki redak i stupac. S obzirom na broj redaka, sve tri petlje se izvode do "n" puta. Posljedično, ukupna vremenska složenost je O(n3).
Prostorna složenost je konstantna jer ne pohranjujemo nikakve međurezultate. Program izračunava svaki element u hodu i ispisuje ga unutar retka, pa se prostorna složenost smanjuje na O (1).
Metoda 3: Izrada Pascalovog trokuta pomoću modificiranog binomnog koeficijenta
U prethodnoj tehnici koristili smo formulu binomnog koeficijenta za izračun svakog elementa. Modificirani pristup izvodi C(n, r) izravno iz C(n, r-1), smanjujući rad za jedan red veličine.
Evo koraka za izgradnju Pascalovog trokuta modificiranim binomnim koeficijentom:
Korak 1) Započnite prvi redak s "1".
Korak 2) Izračunajte C(n, r), gdje je „n“ broj retka, a „r“ indeks stupca. Dodijelite tu vrijednost varijabli C.
Korak 3) Za izračunavanje sljedećeg koeficijenta koristite C * (n – k) / k. Dodijelite ovu novu vrijednost natrag C.
Korak 4) Nastavite korak 3 dok "k" ne dođe do kraja retka. Nakon svake iteracije, povećajte k za jedan.
C++ Code za Pascalov trokut modificiranim binomnim koeficijentom
#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); }
Izlaz:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code za Pascalov trokut modificiranim binomnim koeficijentom
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)
Izlazni obrasci Pascalovog trokuta:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Analiza složenosti
Implementacija koristi dvije petlje, svaka se izvršava maksimalno "n" puta, gdje je "n" broj redaka u trokutu. Dakle, vremenska složenost je Na2), vrijeme na kvadrat.
Što se tiče prostorne složenosti, ne treba nam nikakav niz za pohranu. Koristimo samo jednu varijablu za zadržavanje prethodnog binomnog koeficijenta, tako da nam je potreban samo jedan dodatni prostor. Prostorna složenost je stoga O (1).
Primjena Pascalovog trokuta
Evo nekih praktičnih primjena Pascalovog trokuta:
Binomna proširenja: Koeficijenti bilo koje binomne ekspanzije mogu se izravno očitati iz Pascalovog trokuta. Evo primjera:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2i + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3i + 6x2y2 + 4xy3 + 1y4 |
Izračunavanje kombinacija: Elementi Pascalovog trokuta izravno odgovaraju binomnim koeficijentima. Na primjer, ako imate 6 kuglica i želite odabrati 3, odgovor je 6C3Tu vrijednost možete pronaći u 3. elementu 6. retka Pascalovog trokuta.
Vjerojatnost: Pascalov trokut se široko koristi za izračunavanje vjerojatnosti u bacanju novčića, problemima s kockicama i drugim kombinatornim događajima gdje svaki ishod odgovara binomnoj distribuciji.
Zanimljive činjenice o Pascalovom trokutu
Evo nekoliko činjenica koje će vam biti zanimljive o Pascalovom trokutu:
- Zbroj svih elemenata u bilo kojem retku uvijek je potencija broja 2.
- Dijagonalne sume redaka generiraju Fibonaccijev niz.
- Svaki redak odgovara koeficijentima u razvoju jednadžbe (a+b)n.
- Ako zasjenite samo neparne brojeve, rezultirajuća figura tvori fraktal Sierpinskijevog trokuta.
