Triunghiul lui Pascal – Formule, modele și exemple
Sarah Chen
Ce este triunghiul lui Pascal?
Triunghiul lui Pascal este o matrice triunghiulară de numere urmate de un anumit model și conexiune la rândul dinaintea acestuia. A fost inventat de Blaise Pascal. Acest triunghi începe cu un element din primul rând. După aceea, fiecare rând începe și se termină cu „1”.
Istoria triunghiului lui Pascal
Cartea chineză „Cele nouă capitole despre arta matematică” conține unul dintre primele exemple ale triunghiului lui Pascal. În plus, conține unele dintre aceleași modele și calități întâlnite astăzi în triunghiuri.
Pascal a fost unul dintre câțiva oameni din Europa care au studiat triunghiul. Alți matematicieni examinaseră rețele triunghiulare similare de numere înaintea lui.
Construcția triunghiului lui Pascal
Construirea triunghiului lui Pascal este simplă. Singurul lucru pe care trebuie să-l rețineți este că rândul începe și se termină cu 1. Regula pentru restul numerelor este următoarea:
Pentru orice rând r și coloana c, numărul va fi suma coloanelor c-1 și c din rândul r-1.
Aici,
- r = 3,4,5….
- n și c = 2,3,4,...r-1.
Iată pașii pentru a construi Triunghiul lui Pascal:
Pas 1) Să începem prin a umple două rânduri.
Pas 2) Al doilea element pentru a treia linie este suma primului și celui de-al doilea număr din al doilea rând.
Pas 3) Al patrulea rând va începe cu „1.”. Al doilea număr este 3, care este suma lui 1 și 2 (evidențiat cu albastru).
Imaginea de mai jos arată cum să umpleți al patrulea rând:
Pas 4) Al cincilea rând va fi format din cinci numere. Cunoaștem deja modelul pentru popularea rândurilor din pașii anteriori.
Formula triunghiului lui Pascal – Coeficient binomial
Un coeficient binomial este un număr care exprimă diferite metode de selectare a unui subset de k elemente dintr-o colecție de n elemente. Frecvent, este scris ca „C(n,k)” sau „n alege k”.
Coeficientul binom este definit ca
„!” denotă „factorialul”.
n! = n.(n-1). (n-2)…3.2.1
De exemplu,
5! = 5.4.3.2.1
= 120
Deci, să spunem C(5,3) sau 5 alege 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metoda 1: Construirea triunghiului lui Pascal după rândul anterior
Pașii din această procedură sunt aceiași cu cei din triunghiul lui Pascal. Să presupunem că vrem să creăm triunghiul lui Pascal cu până la șapte rânduri.
Pașii pentru a realiza acest lucru sunt următorii:
Pas 1) Începeți primul rând cu „1”.
Pas 2) Pentru rândul „r”, elementul „c” va fi produsul dintre „c-1” și „c” numărul rândului „r-1”.
Pas 3) Primul și ultimul număr dintr-un rând vor fi întotdeauna „1”.
Trebuie să respectăm acești trei pași simpli pentru a crea triunghiul lui Pascal.
C++ Codul triunghiului lui Pascal după rândul anterior
#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);
}
ieșire:
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 Codul formulei triunghiului Pascal după rândul anterior
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)
Triunghiul lui Pascal Exemplu de ieșire:
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 complexității
A matrice bidimensională a fost folosit în implementare. Având în vedere că N este numărul de rânduri din triunghiul lui Pascal. Acest lucru va necesita N2 spatii unitare. Prin urmare, O va fi complexitatea spațiului (N2).
Avem două bucle în funcție și fiecare buclă rulează de „N” ori. Deci, complexitatea timpului este de asemenea PE2) sau complexitatea timpului la pătrat.
Metoda 2: Construirea triunghiului lui Pascal prin calculul coeficientului binomial
Putem deduce pur și simplu numerele triunghiului lui Pascal folosind coeficientul binomial. Iată diagrama:
Iată pașii pentru a construi triunghiul lui Pascal prin calculul binomului:
Pas 1) Rândul de sus va fi C(0,0). Folosind formula de mai sus pentru coeficientul binomial, C(0,0) = 1. Pentru că 0! = 1.
Pas 2) Pentru rândul „i”, vor exista elemente „i” totale. Fiecare element va fi calculat C(n,r) unde n va fi i-1.
Pas 3) Repetați pasul 2 pentru numărul de rânduri dorit pentru triunghiul lui Pascal.
C++ Codați triunghiul lui Pascal prin coeficient binomial
#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);
}
ieșire:
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 Codați triunghiul lui Pascal prin coeficient binomial
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)
Triunghiul lui Pascal Exemplu de ieșire:
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 complexității
În implementare au fost utilizate trei bucle. O buclă este pentru calcularea coeficientului Binomial, iar celelalte două sunt pentru crearea numerelor pentru toate rândurile. În ceea ce privește numărul de rânduri, avem trei bucle care se execută de „n” ori. În consecință, complexitatea generală a timpului va fi 0 (n3).
Complexitatea spațiului este acum constantă, deoarece nu păstrăm date în stocare. Programul calculează elementul și este imprimat într-un rând. Complexitatea spațiului scade apoi la 0(1).
Metoda 3: Construirea triunghiului lui Pascal prin coeficient binomial modificat
În tehnica anterioară, am văzut deja cum să folosim un coeficient binomial pentru a calcula fiecare element al triunghiului lui Pascal. Această abordare va determina C(n,r) din C. (n, r-1). Va simplifica lucrurile printr-o singură ordine.
Iată pașii pentru construirea triunghiului lui Pascal prin coeficient binomial modificat:
Pas 1) Inițiază primul rând cu „1”
Pas 2) Calculați C(n,r), unde „n” este numărul rândului și „r” este coloana sau elementul. Atribuiți valoarea unei variabile C.
Pas 3) Pentru calcularea C(n,k), acesta va fi C*(nk)/k. Acum, atribuiți această valoare lui C.
Pas 4) Continuați pasul 3 până când „k” ajunge la sfârșitul rândului. După fiecare iterație, crește valoarea lui K cu unu.
C++ Cod pentru triunghiul lui Pascal prin coeficient binomial modificat
#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);
}
ieșire:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python cod pentru Triunghiul lui Pascal prin coeficient binomial modificat
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)
Ieșire modele triunghiulare a lui Pascal:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Analiza complexității
Implementarea are două bucle. Fiecare buclă rulează maximum „n” timp, unde „n” înseamnă numărul de rânduri din triunghiul pascal. Deci, complexitatea timpului este Pe2), timp la pătrat.
În ceea ce privește complexitatea spațiului, nu am avut nevoie de nicio matrice pentru a stoca. Am folosit doar o variabilă pentru a păstra coeficientul binom anterior. Deci, aveam nevoie doar de un spațiu suplimentar. Complexitatea spațiului a devenit O (1).
Aplicarea triunghiului lui Pascal
Iată câteva aplicații ale triunghiului lui Pascal:
Expansiuni binomiale: Putem determina coeficientul expansiunilor binomiale din triunghiul lui Pascal. Iată un exemplu:
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2xy + 1y2 |
| (x + y)3 | 1x3 + 3x2și + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3și + 6x2y2 + 4xy3 + 1y4 |
Calcularea combinațiilor: Am văzut că elementele triunghiului lui Pascal sunt echivalente cu coeficienții binomi. De exemplu, dacă aveți 6 bile și vi s-a cerut să alegeți 3 bile, va fi 6C3. Sau, puteți găsi numărul în al 3-lea element al celui de-al 6-lea rând din triunghiul lui Pascal.
Fapte interesante despre triunghiul lui Pascal
Iată câteva fapte pe care le veți găsi interesante despre triunghiul lui Pascal:
- Suma tuturor elementelor dintr-un rând este întotdeauna puterea lui 2.
- Suma diagonală a elementelor rândurilor generează succesiunea Fibonacci.
Rezumat
- Triunghiul lui Pascal dă coeficienții expansiunilor binomiale.
- Fiecare rând de triunghi al lui Pascal începe și se termină cu „1”. Valorile intermediare sunt suma a două elemente din rândul anterior.
- Adăugarea în diagonală a tuturor elementelor din triunghiul lui Pascal vă va oferi Secvență Fibonacci.
- Triunghiul lui Pascal poate fi generat și cu coeficienți binomiali.
