In questo articolo, utilizzerò un semplice esempio per farvi ragionare sul calcolo combinatorio e spiegarvi la funzione del coefficiente binomiale.
Problema
Uno chef ha 5 ingredienti: speck, zucca, gorgonzola, radicchio e porro. Gli viene incaricato di creare quanti più risotti possibile ma, per ogni risotto, può usare soltanto 2 ingredienti. Quanti risotti prepara?
Brain storming
La prima cosa che verrebbe da pensare è che, avendo 5 ingredienti e facendo combinazioni di 2, basti fare
5\cdot 5=25
e ottenere 25 combinazioni, come riportato nella tabella seguente.
| Speck | Zucca | Gorg. | Rad. | Porro | |
| Speck | 1 | 2 | 3 | 4 | 5 |
| Zucca | 6 | 7 | 8 | 9 | 10 |
| Gorg. | 11 | 12 | 13 | 14 | 15 |
| Rad. | 16 | 17 | 18 | 19 | 20 |
| Porro | 21 | 22 | 23 | 24 | 25 |
Salta subito all’occhio un problema: le celle sulla diagonale principale riportano tutte un ingrediente doppio (come speck-speck, zucca-zucca…) e sono, quindi, da non considerare. Ecco la tabella aggiornata:
| Speck | Zucca | Gorg. | Rad. | Porro | |
| Speck | x | 1 | 2 | 3 | 4 |
| Zucca | 5 | x | 6 | 7 | 8 |
| Gorg. | 9 | 10 | x | 11 | 12 |
| Rad. | 13 | 14 | 15 | x | 16 |
| Porro | 17 | 18 | 19 | 20 | x |
C’è un’altra osservazione da fare. Ora, le x dividono la tabella in due matrici triangolari: la matrice triangolare superiore e la matrice triangolare inferiore.
La matrice triangolare inferiore contiene gli stessi elementi di quella superiore ma con ordine diverso. Per esempio, se quella superiore ha la combinazione speck-zucca, quella inferiore ha zucca-speck. È chiaro che queste ripetizioni non vanno contate; di conseguenza, tutta la matrice triangolare inferiore non va contata.
Risultato: ci sono 10 combinazioni.
| Speck | Zucca | Gorg. | Rad. | Porro | |
| Speck | x | 1 | 2 | 3 | 4 |
| Zucca | x | x | 5 | 6 | 7 |
| Gorg. | x | x | x | 8 | 9 |
| Rad. | x | x | x | x | 10 |
| Porro | x | x | x | x | x |
Soluzione matematica
Cerchiamo di ottenere il risultato appena trovato con un metodo matematico, anziché con metodo induttivo. Per farlo, bisonga prima introdurre il fattoriale di un numero.
Il fattoriale di un numero è la moltiplicazione di quel numero per tutti i numeri precedenti (fino a 1) e si esprime con un punto esclamativo. Ecco qualche esempio di fattoriale:
1!=1
2!=1\cdot2=2
3!=1\cdot2\cdot3=6
4!=1\cdot2\cdot3\cdot4=24
10!=1\cdot2\cdot3\cdot\cdots\cdot9\cdot10=3.628.800
Ora che sappiamo calcolare il fattoriale, introduciamo il protagonista di questo articolo: il coefficiente binomiale.
Il coefficiente binomiale di due numeri generici x e y (con x\geq y) si calcola come segue:
\binom{x}{y}=\frac{x!}{y!\cdot\left( x-y \right)!}Nella formula, x rappresenta il bacino di campioni complessivo da cui si possono prendere uno o più elementi e y il numero di elementi da prendere. In poche parole, x=5 e y=2.
\binom{x}{y}=\binom{5}{2}=\frac{5!}{2!\cdot\left( 5-2 \right)!} == \frac{1\cdot2\cdot3\cdot4\cdot5}{\left( 1\cdot2 \right) \cdot \left( 1\cdot2\cdot3 \right)}=\frac{120}{2\cdot6}=10Fatto, abbiamo risolto il problema con un procedimento puramente matematico e abbiamo confermato quanto dedotto prima.
Risultato: ci sono 10 combinazioni.