Pascalov trokut – formula, obrasci i primjeri
Sarah Chen
Što je Pascalov trokut?
Pascalov trokut je trokutasti niz brojeva iza kojeg slijedi određeni uzorak i veza s redom ispred njega. Izumio ga je Blaise Pascal. Ovaj trokut počinje s jednim elementom u prvom redu. Nakon toga, svaki red počinje i završava s "1".
Povijest Pascalovog trokuta
Kineska knjiga “Devet poglavlja o matematičkoj umjetnosti” sadrži jedan od prvih primjera Pascalovog trokuta. Osim toga, sadrži neke od istih uzoraka i kvaliteta koje danas možemo pronaći u trokutima.
Pascal je bio jedan od nekoliko ljudi u Europi koji su proučavali trokut. Drugi su matematičari prije njega ispitivali slične trokutaste nizove brojeva.
Konstrukcija Pascalovog trokuta
Konstruiranje Pascalovog trokuta je jednostavno. Jedina stvar koju trebate zapamtiti je da red počinje i završava s 1. Pravilo za ostale brojeve je sljedeće:
Za bilo koji redak r i stupac c, broj će biti zbroj stupaca c-1 i c iz 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čnimo s popunjavanjem dva reda.
Korak 2) Drugi element za treći red je zbroj prvog i drugog broja u drugom retku.
Korak 3) Četvrti red počinje s "1.". Drugi broj je 3, što je zbroj 1 i 2 (označeno plavom bojom).
Slika ispod pokazuje kako ispuniti četvrti red:
Korak 4) Peti red će se sastojati od pet brojeva. Već znamo uzorak za popunjavanje redaka iz ranijih koraka.
Formula Pascalovog trokuta – Binomni koeficijent
Binomni koeficijent je broj koji izražava različite metode za odabir podskupa od k elemenata iz kolekcije od n elemenata. Često se piše kao "C(n,k)" ili "n izaberi k."
Binomni koeficijent je definiran kao
"!" označava "faktorijel".
n! = n.(n-1). (n-2)…3.2.1
Na primjer,
5! = 5.4.3.2.1
= 120
Dakle, recimo C(5,3) ili 5 izaberi 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metoda 1: Izrada Pascalovog trokuta prema prethodnom redu
Koraci u ovom postupku su isti kao oni u Pascalovom trokutu. Recimo da želimo stvoriti Pascalov trokut do sedam redaka.
Koraci za postizanje toga su sljedeći:
Korak 1) Započnite najviši red s "1".
Korak 2) Za red "r", stavka "c" bit će umnožak "c-1" i "c" broja retka "r-1".
Korak 3) Prvi i zadnji broj u nizu uvijek će biti "1."
Moramo se pridržavati ova tri laka koraka za stvaranje Pascalovog trokuta.
C++ Kod Pascalovog trokuta prethodnim redom
#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 Kod Pascalove formule trokuta prethodnim redom
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 korišten je u provedbi. S obzirom da je N broj redaka u Pascalovom trokutu. Ovo će zahtijevati N2 jedinični prostori. Stoga će O biti kompleksnost prostora (N2).
Imamo dvije petlje u funkciji, a svaka se petlja izvodi “N” puta. Dakle, vremenska složenost je također NA2) ili kvadrat vremenske složenosti.
Metoda 2: Izrada Pascalovog trokuta izračunavanjem binomnog koeficijenta
Možemo jednostavno izvesti brojeve Pascalovog trokuta koristeći binomni koeficijent. Evo dijagrama:
Evo koraka za sastavljanje Pascalovog trokuta izračunavanjem binoma:
Korak 1) Najgornji red bit će C(0,0). Koristeći gornju formulu za binomni koeficijent, C(0,0) = 1. Jer 0! = 1.
Korak 2) Za redak “i” bit će ukupno “i” elemenata. Svaka stavka će se izračunati C(n,r) gdje će n biti i-1.
Korak 3) Ponovite korak 2 za broj redaka koji želite za Pascalov trokut.
C++ Kodiraj Pascalov trokut binomnim koeficijentom
#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 Kodiraj Pascalov trokut binomnim koeficijentom
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 izvedbi su korištene tri petlje. Jedna petlja služi za izračunavanje binomnog koeficijenta, a druge dvije služe za kreiranje brojeva za sve retke. Što se tiče broja redaka, imamo tri petlje koje se izvršavaju “n” puta. Posljedično, ukupna vremenska složenost bit će 0(n3).
Složenost prostora sada je konstantna jer ne držimo nikakve podatke u pohrani. Program izračunava element i on se ispisuje u nizu. Složenost prostora tada se smanjuje na 0(1).
Metoda 3: Izrada Pascalovog trokuta pomoću modificiranog binomnog koeficijenta
U prethodnoj tehnici već smo vidjeli kako koristiti binomni koeficijent za izračunavanje svakog elementa Pascalovog trokuta. Ovaj pristup će odrediti C(n,r) iz C. (n, r-1). To će pojednostaviti stvari jednim redom.
Ovdje su koraci za izgradnju Pascalovog trokuta pomoću modificiranog binomnog koeficijenta:
Korak 1) Započnite prvi red s "1"
Korak 2) Izračunajte C(n,r), gdje je "n" broj retka, a "r" je stupac ili element. Dodijelite vrijednost varijabli C.
Korak 3) Za izračun C(n,k), to će biti C*(nk)/k. Sada dodijelite ovu vrijednost C.
Korak 4) Nastavite s korakom 3 dok "k" ne dođe do kraja reda. Nakon svakog ponavljanja, povećajte vrijednost K za jedan.
C++ Kod 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 kod 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 ima dvije petlje. Svaka se petlja izvodi maksimalno "n" vremena, gdje "n" znači broj redaka u Pascal trokutu. Dakle, vremenska složenost je Na2), vrijeme na kvadrat.
Što se tiče složenosti prostora, nije nam trebao nikakav niz za pohranu. Upravo smo upotrijebili jednu varijablu da zadržimo prethodni binomni koeficijent. Dakle, trebao nam je samo jedan dodatni prostor. Složenost prostora postala je O (1).
Primjena Pascalovog trokuta
Evo nekih primjena Pascalovog trokuta:
Binomna proširenja: Možemo odrediti koeficijent binomnih proširenja 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: Vidjeli smo da su elementi Pascalovog trokuta ekvivalentni binomnim koeficijentima. Na primjer, ako imate 6 lopti i od vas se traži da odaberete 3 loptice, to će biti 6C3. Ili, možete pronaći broj u 3. elementu 6. reda iz Pascalovog trokuta.
Zanimljive činjenice o Pascalovom trokutu
Evo nekoliko činjenica koje će vam biti zanimljive o Pascalovom trokutu:
- Zbroj svih elemenata u nizu uvijek je potencija broja 2.
- Dijagonalni zbroj elemenata redaka generira Fibonaccijev niz.
Rezime
- Pascalov trokut daje koeficijente za binomna proširenja.
- Svaki red Pascalovog trokuta počinje i završava s "1". Međuvrijednosti su zbroj dva elementa prethodnog reda.
- Dijagonalno zbrajanje svih elemenata u Pascalovom trokutu će vam dati Fibonacci slijed.
- Pascalov trokut također se može generirati s binomnim koeficijentima.
