Rimane da capire per quale motivo C(n,k) sia al tempo stesso coefficiente di an-k x bk nella potenza del binomio e numero dei sottoinsiemi di S con k elementi.
Calcoliamo il prodotto di a+b per se stesso n volte
(a+b)x(a+b)x...x(a+b)
prendendo a oppure b in ognuna delle n parentesi e moltiplicandoli tra di loro.
Otterremo una somma di addendi del tipo an-k x bk con k che varia da 0 a n. Quante volte otteniamo l'addendo an-k x bk? Si tratta di scegliere b k volte in tutti i modi possibili tra le n parentesi; questo numero è dunque uguale al numero dei sottoinsiemi con k elementi estratti dall'insieme S={1, 2, ..., n}, cioè è uguale C(n,k).
Conoscere il significato combinatorico dei coefficienti binomiali C(n,k) permette di svelare facilmente il segreto della formazione "automatica" del triangolo di Pascal.
Ci proponiamo di calcolare C(n+1,k) quando ci siano noti i C(n,k). Consideriamo per questo gli insiemi S={1,2,...,n} ed S'={1,2,...,n,
n+1
}. Per calcolare C(n+1,k) dobbiamo estrarre tutti i sottoinsiemi con k elementi da S' e contare quanti sono. Questi sottoinsiemi si possono dividere in due categorie separate: quelli che contengono n+1 e quelli che non lo contengono. Il numero di quelli che non contengono n+1 è uguale al numero di sottoinsiemi con k elementi di S, cioè è C(n,k); del resto i sottoinsiemi con k elementi di S' che contengono n+1 sono tutti e soli quelli che contengono esattamente k-1 elementi compresi tra 1 ed n: dunque il loro numero è C(n,k-1). Concludendo otteniamo la fondamentale formula di addizione.
C(n+1,k) = C(n,k-1)+C(n,k)
Questo vuol dire che il triangolo di Pascal è semplicemente un automa cellulare con 3 intorni che obbedisce alla legge 90! Osserviamo la tavola seguente:
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
2
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
1
|
0
|
3
|
0
|
3
|
0
|
1
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
1
|
0
|
4
|
0
|
6
|
0
|
4
|
0
|
1
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
5
|
0
|
10
|
0
|
10
|
0
|
5
|
0
|
1
|
0
|
0
|
L'automa parte da uno stato centrato: la prima riga è formata tutta di 0 con un 1 al centro. Ad ogni istante lo stato di una cella è dato dalla somma degli interi che stanno nelle due celle adiacenti nell'istante precedente: questa è esattamente la legge di formazione dei C(n,k), ed è la legge 90
se consideriamo tutti gli interi modulo 2, cioè scriviamo 0 se l'intero è pari e 1 se l'intero è dispari. Per studiare questo triangolo e visualizzarlo con le nostre applet lo struttureremo in un modo diverso, mettendo in verticale il lato sinistro formato tutto di 1, cosicché l'automa diventa:
|
1
|
0
|
0
|
0
|
0
|
0
|
|
1
|
1
|
0
|
0
|
0
|
0
|
|
1
|
2
|
1
|
0
|
0
|
0
|
|
1
|
3
|
3
|
1
|
0
|
0
|
|
1
|
4
|
6
|
4
|
1
|
0
|
|
1
|
5
|
10
|
10
|
5
|
1
|
In questo nuovo modello la prima riga della matrice inizia con 1 ed è seguita da zeri; la prima colonna è tutta formata da 1; si segue poi questa regola: l'elemento di posto i,j della matrice, chiamiamolo Pascal[i,j] è posto uguale a Pascal[i-1,j-1]+Pascal[i-1,j]. Quindi Pascal[i,j] è la somma dell'elemento che lo sovrasta con quello che sta in alto a sinistra. Supponiamo ora di colorare di nero tutti gli elementi pari della matrice e lasciare bianchi gli altri. Si ottiene allora questo disegno:
Più in generale, dato un modulo M possiamo nella matrice di Pascal annerire gli elementi divisibili per M e lasciare bianchi gli altri.