Il 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 matrice seguente.

Salta subito all’occhio un problema: le celle sulla diagonale riportano tutte un ingrediente doppio (come speck-speck, zucca-zucca…) e sono, quindi, da non considerare.

C’è un’altra osservazione da fare. Ora, la diagonale principale divide 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 è una ripetizione di cui tenere conto. Di conseguenza, tutta la matrice triangolare inferiore (o superiore, quella che si preferisce) non va contata.

Siamo arrivati al nostro risultato. Le possibili combinazioni sono 10!

Soluzione

Per risolvere questo problema matematico, parliamo prima del fattoriale.

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

Il problema di questo articolo si risolve con il coefficiente binomiale, che fa uso dei fattoriali. 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.

Nel nostro caso, la formula diventa

\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}=10

Il risultato è 10.