Formula del triangolo di Pascal con esempi
Team editoriale
⚡ Riepilogo intelligente
Il triangolo di Pascal è una disposizione triangolare di numeri in cui ogni valore è uguale alla somma dei due numeri che lo sovrastano direttamente, rivelando schemi profondi di combinatoria, espansioni binomiali e probabilità che affascinano i matematici da secoli.
Cos’è il triangolo di Pascal?
Il triangolo di Pascal è una disposizione triangolare di numeri che segue uno schema semplice basato sulla riga sovrastante. Fu reso popolare dal matematico francese Blaise Pascal nel XVII secolo. Il triangolo inizia con un singolo "1" in cima, e ogni riga successiva inizia e finisce anch'essa con un "1".
Al di là della sua forma elegante, il triangolo di Pascal racchiude profonde relazioni matematiche. È strettamente legato al teorema binomiale, al conteggio combinatorio e alla probabilità, motivo per cui compare nei corsi di algebra, statistica e informatica di tutto il mondo.
Storia del triangolo di Pascal
Sebbene prenda il nome da Blaise Pascal, il triangolo è una figura che lo precede di secoli. Il testo matematico cinese "I nove capitoli sull'arte matematica" contiene uno dei primi esempi conosciuti, che mostra molti degli stessi schemi che utilizziamo ancora oggi.
Il matematico persiano Al-Karaji e lo studioso indiano PingAnche Ala esplorò strutture simili. Pascal formalizzò le proprietà del triangolo nel suo trattato del 1654 "Traité du triangle arithmétique", che diede alla struttura il suo nome moderno nella matematica occidentale.
Costruzione del triangolo di Pascal
Costruire il triangolo di Pascal è semplice. L'unica regola da ricordare è che ogni riga inizia e finisce con 1, e ogni altro numero è costruito a partire dalla riga superiore.
Per ogni riga r e colonna c, il valore è uguale alla somma dei numeri nelle 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) Iniziate riempiendo le prime due righe.
Passo 2) Il secondo elemento della terza riga è la somma del primo e del secondo numero della seconda riga.
Passo 3) La quarta riga inizia con “1”. Il secondo numero è 3, che è la somma di 1 e 2 (evidenziato in blu).
L'immagine qui sotto mostra come riempire la quarta riga:
Passo 4) La quinta riga è composta da cinque numeri. Conosciamo già lo schema per popolare le righe dai passaggi precedenti.
Formula del triangolo di Pascal – Coefficiente binomiale
Il coefficiente binomiale conta il numero di modi in cui è possibile scegliere un sottoinsieme di k elementi da una collezione di n elementi. Viene comunemente indicato come "C(n, k)" o "n su k".
Il coefficiente binomiale è definito come:
Il simbolo “!” indica il fattoriale di un numero.
n! = n.(n-1).(n-2)…3.2.1
Per esempio,
5! = 5.4.3.2.1
= 120
Quindi, C(5, 3) o “5 su 3” = 5! / 3!(5-3)!
= 120 / 12
= 10
Metodo 1: Costruire il triangolo di Pascal utilizzando la riga precedente
La procedura qui descritta rispecchia il modo in cui abbiamo disegnato il triangolo manualmente. Supponiamo di voler generare il triangolo di Pascal fino a sette righe.
Ecco i passaggi da seguire:
Passo 1) Inizia la riga più in alto con "1".
Passo 2) Per la riga “r”, l’elemento “c” sarà la somma della colonna “c-1” e della colonna “c” della riga “r-1”.
Passo 3) Il primo e l'ultimo numero di ogni riga saranno sempre "1".
Seguendo questi tre semplici passaggi, possiamo costruire sistematicamente l'intero triangolo.
C++ Code 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 Code della formula del triangolo di Pascal dalla 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 viene utilizzato in questa implementazione. Dato che N è il numero di righe nel triangolo di Pascal, ciò richiede N2 spazi unitari. Pertanto, la complessità dello spazio è O(N2).
La funzione utilizza due cicli annidati, ciascuno dei quali viene eseguito fino a “N” volte. Quindi, anche la complessità temporale è SU2), ovvero complessità temporale al quadrato.
Metodo 2: Costruzione del triangolo di Pascal mediante il calcolo del coefficiente binomiale
Possiamo ricavare direttamente i numeri del triangolo di Pascal utilizzando i coefficienti binomiali. Il diagramma seguente illustra la relazione:
Ecco i passaggi per costruire il triangolo di Pascal calcolando il coefficiente binomiale:
Passo 1) La riga più in alto è C(0, 0). Usando la formula sopra, C(0, 0) = 1, perché 0! = 1.
Passo 2) Per la riga “i”, ci saranno in totale “i” elementi. Ogni elemento viene calcolato come C(n, r), dove n è i-1.
Passo 3) Ripeti il passaggio 2 per generare il numero di righe del triangolo di Pascal che desideri.
C++ Code Triangolo di Pascal tramite 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 Code Triangolo di Pascal tramite 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à
In questa implementazione vengono utilizzati tre cicli: uno per calcolare il coefficiente binomiale e altri due per iterare su ogni riga e colonna. Rispetto al numero di righe, tutti e tre i cicli vengono eseguiti fino a "n" volte. Di conseguenza, la complessità temporale complessiva è O(n3).
La complessità spaziale è costante perché non memorizziamo alcun risultato intermedio. Il programma calcola ogni elemento al volo e lo stampa all'interno di una riga, quindi la complessità spaziale si riduce a O (1).
Metodo 3: costruzione del triangolo di Pascal mediante coefficiente binomiale modificato
Nella tecnica precedente, abbiamo utilizzato la formula del coefficiente binomiale per calcolare ciascun elemento. L'approccio modificato deriva C(n, r) direttamente da C(n, r-1), riducendo il lavoro di un ordine di grandezza.
Ecco i passaggi per costruire il triangolo di Pascal utilizzando 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" è l'indice di colonna. Assegna questo valore a una variabile C.
Passo 3) Per calcolare il coefficiente successivo, utilizzare C * (n – k) / k. Assegnare questo nuovo valore a C.
Passo 4) Continua il passaggio 3 finché “k” non raggiunge la fine della riga. Dopo ogni iterazione, incrementa k di uno.
C++ Code 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 Code 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 utilizza due cicli, ciascuno dei quali viene eseguito al massimo “n” volte, dove “n” è il numero di righe nel triangolo. Quindi, la complessità temporale è Sopra2), tempo al quadrato.
Per quanto riguarda la complessità spaziale, non abbiamo bisogno di alcun array per l'archiviazione. Utilizziamo solo una variabile per mantenere il coefficiente binomiale precedente, quindi abbiamo bisogno solo di uno spazio aggiuntivo. La complessità spaziale è quindi O (1).
Applicazione del triangolo di Pascal
Ecco alcune applicazioni pratiche del triangolo di Pascal:
Espansioni binomiali: I coefficienti di qualsiasi sviluppo binomiale possono essere letti direttamente 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: Gli elementi del triangolo di Pascal corrispondono direttamente ai coefficienti binomiali. Ad esempio, se hai 6 palline e vuoi sceglierne 3, la risposta è 6C3Puoi trovare quel valore nel terzo elemento della sesta riga del triangolo di Pascal.
Probabilità: Il triangolo di Pascal è ampiamente utilizzato per calcolare le probabilità nel lancio di una moneta, nei problemi con i dadi e in altri eventi combinatori in cui ogni risultato corrisponde a una distribuzione binomiale.
Fatti interessanti sul triangolo di Pascal
Ecco alcuni fatti che troverai interessanti sul triangolo di Pascal:
- La somma di tutti gli elementi di una qualsiasi riga è sempre una potenza di 2.
- La somma diagonale delle righe genera la sequenza di Fibonacci.
- Ogni riga corrisponde ai coefficienti nello sviluppo di (a+b)n.
- Se si colorano solo i numeri dispari, la figura risultante forma il frattale del triangolo di Sierpinski.
