Triangolo di Pascal: formula, modelli ed esempi
Sara Chen
Cos’è il triangolo di Pascal?
Il triangolo di Pascal è una serie triangolare di numeri seguita da uno schema particolare e da una connessione alla riga precedente. È stato inventato da Blaise Pascal. Questo triangolo inizia con un elemento nella prima riga. Successivamente, ogni riga inizia e termina con “1”.
Storia del triangolo di Pascal
Il libro cinese “I nove capitoli dell'arte matematica” contiene uno dei primi esempi del triangolo di Pascal. Inoltre, contiene alcuni degli stessi modelli e qualità che si trovano oggi nei triangoli.
Pascal era una delle tante persone in Europa che studiarono il triangolo. Altri matematici avevano esaminato simili serie triangolari di numeri prima di lui.
Costruzione del triangolo di Pascal
Costruire il triangolo di Pascal è semplice. L'unica cosa che devi ricordare è che la riga inizia e finisce con 1. La regola per il resto dei numeri è la seguente:
Per ogni riga r e colonna c, il numero sarà la somma delle colonne c-1 e c della riga r-1.
Qui,
- r = 3,4,5….
- n e c = 2,3,4,…r-1.
Ecco i passaggi per costruire il triangolo di Pascal:
Passo 1) Iniziamo riempiendo due righe.
Passo 2) Il secondo elemento per la terza riga è la somma del primo e del secondo numero nella seconda riga.
Passo 3) La quarta riga inizierà con “1.”. Il secondo numero è 3, che è la somma di 1 e 2 (evidenziato in blu).
L'immagine seguente mostra come riempire la quarta riga:
Passo 4) La quinta riga sarà composta da cinque numeri. Conosciamo già lo schema per popolare le righe dai passaggi precedenti.
Formula del triangolo di Pascal – Coefficiente binomiale
Un coefficiente binomiale è un numero che esprime diversi metodi per selezionare un sottoinsieme di k elementi da una raccolta di n elementi. Spesso viene scritto come “C(n,k)” o “n scegli k”.
Il coefficiente binomiale è definito come
IL "!" denota il “fattoriale”.
N! = n.(n-1). (n-2)…3.2.1
Per esempio,
5! = 5.4.3.2.1
= 120
Quindi, diciamo che C(5,3) o 5 scegliamo 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
Metodo 1: costruire il triangolo di Pascal con la riga precedente
I passaggi di questa procedura sono gli stessi del triangolo di Pascal. Diciamo che vogliamo creare il triangolo di Pascal fino a sette righe.
I passaggi per farlo sono i seguenti:
Passo 1) Inizia la riga più in alto con "1".
Passo 2) Per la riga “r”, l'elemento “c” sarà il prodotto di “c-1” e “c” il numero della riga “r-1”.
Passo 3) Il primo e l'ultimo numero di fila saranno sempre "1".
Dobbiamo rispettare questi tre semplici passaggi per creare il triangolo di Pascal.
C++ Codice del triangolo di Pascal dalla riga precedente
#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);
}
Produzione:
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 Codice della formula del triangolo di Pascal per la riga precedente
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)
Output di esempio del triangolo di Pascal:
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
Analisi della complessità
A matrice bidimensionale è stato utilizzato nell'implementazione. Dato che N è il numero di righe nel triangolo di Pascal. Ciò richiederà N2 spazi unitari. Pertanto, O sarà la complessità dello spazio (N2).
Abbiamo due cicli nella funzione, e ogni ciclo viene eseguito per "N" volte. Quindi, anche la complessità temporale è SU2) o complessità temporale al quadrato.
Metodo 2: costruire il triangolo di Pascal calcolando il coefficiente binomiale
Possiamo semplicemente ricavare i numeri del triangolo di Pascal utilizzando il coefficiente binomiale. Ecco il diagramma:
Ecco i passaggi per costruire il triangolo di Pascal calcolando il binomio:
Passo 1) La riga più in alto sarà C(0,0). Usando la formula sopra per il coefficiente binomiale, C(0,0) = 1. Perché 0! = 1.
Passo 2) Per la riga "i", ci saranno elementi "i" totali. Ciascun elemento verrà calcolato C(n,r) dove n sarà i-1.
Passo 3) Ripeti il passaggio 2 per il numero di righe che desideri per il triangolo di Pascal.
C++ Codice Triangolo di Pascal mediante coefficiente binomiale
#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);
}
Produzione:
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 Codice Triangolo di Pascal mediante coefficiente binomiale
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)
Output di esempio del triangolo di Pascal:
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
Analisi della complessità
Nell'implementazione sono stati utilizzati tre loop. Un loop è per calcolare il coefficiente binomiale e gli altri due sono per creare numeri per tutte le righe. Per quanto riguarda il numero di righe, abbiamo tre loop che vengono eseguiti "n" volte. Di conseguenza, la complessità temporale complessiva sarà 0(n3).
La complessità dello spazio è ora costante perché non conserviamo alcun dato in memoria. Il programma calcola l'elemento e lo stampa in una riga. La complessità dello spazio quindi diminuisce a 0(1).
Metodo 3: costruzione del triangolo di Pascal mediante coefficiente binomiale modificato
Nella tecnica precedente abbiamo già visto come utilizzare un coefficiente binomiale per calcolare ogni elemento del triangolo di Pascal. Questo approccio determinerà C(n,r) da C. (n, r-1). Semplificherà le cose con un ordine.
Ecco i passaggi per costruire il triangolo di Pascal mediante il coefficiente binomiale modificato:
Passo 1) Inizia la prima riga con "1"
Passo 2) Calcola C(n,r), dove “n” è il numero di riga e “r” è la colonna o l'elemento. Assegnare il valore in una variabile C.
Passo 3) Per calcolare C(n,k), sarà C*(nk)/k. Ora assegna questo valore a C.
Passo 4) Continuare il passaggio 3 finché la “k” non raggiunge la fine della riga. Dopo ogni iterazione, incrementare il valore di K di uno.
C++ Codice per il triangolo di Pascal mediante coefficiente binomiale modificato
#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);
}
Produzione:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python codice per il triangolo di Pascal mediante coefficiente binomiale modificato
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)
Risultati dei modelli triangolari di Pascal:
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Analisi della complessità
L'implementazione ha due loop. Ogni loop esegue un massimo di "n" tempo, dove "n" indica il numero di righe nel triangolo pascal. Quindi, la complessità temporale è Sopra2), tempo al quadrato.
Per quanto riguarda la complessità dello spazio, non avevamo bisogno di alcun array da memorizzare. Abbiamo solo usato una variabile per mantenere il coefficiente binomiale precedente. Quindi, avevamo solo bisogno di uno spazio extra. La complessità dello spazio è diventata O (1).
Applicazione del triangolo di Pascal
Ecco alcune applicazioni del Triangolo di Pascal:
Espansioni binomiali: Possiamo determinare il coefficiente degli sviluppi binomiali dal triangolo di Pascal. Ecco un esempio:
| (x + y)0 | 1 |
| (x + y)1 | 1.x+ 1.y |
| (x + y)2 | 1x2 + 2xy+ 1y2 |
| (x + y)3 | 1x3 + 3x2e + 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3e + 6x2y2 + 4xy3 + 1y4 |
Calcolo delle combinazioni: Abbiamo visto che gli elementi del triangolo di Pascal sono equivalenti ai coefficienti binomiali. Ad esempio, se hai 6 palline e ti è stato chiesto di sceglierne 3, lo sarà 6C3. Oppure puoi trovare il numero nel 3° elemento della 6a riga del triangolo di Pascal.
Fatti interessanti sul triangolo di Pascal
Ecco alcuni fatti che troverai interessanti sul triangolo di Pascal:
- La somma di tutti gli elementi di una riga è sempre la potenza di 2.
- La somma diagonale degli elementi delle righe genera la sequenza di Fibonacci.
Sintesi
- Il triangolo di Pascal fornisce i coefficienti per le espansioni binomiali.
- Ogni riga del triangolo pascal inizia e termina con "1". I valori intermedi sono la somma di due elementi della riga precedente.
- La somma diagonale di tutti gli elementi del triangolo di Pascal ti darà: Sequenza di Fibonacci.
- Il triangolo di Pascal può essere generato anche con coefficienti binomiali.
