La combinatoria studia, dato un insieme finito di oggetti, i modi e le possibilità di ordinare, disporre o presentare i suoi elementi, in base a determinate regole o restrizioni.

Principio del prodotto

Partiamo con un esempio. Se vogliamo andare da A a C abbiamo prima due possibilità e, in seguito, altre tre: a seconda di quale scegliamo prima abbiamo sempre tre possibilità dopo. Vale quindi che A → C vale 3+3 oppure 2×3. Le possibilità di A → C equivalgono a (A → B) (B → C). Valutiamo quindi tutte le possibili strade che da A mi portano in C : 2 x 3.

Facciamo un esempio ancora più concreto. Con tre magliette, quattro pantaloni e due scarpe per ogni scelta che facciamo su un capo d’abbigliamento possiamo ancora scegliere tutte le altre: 3 possibilità di scegliere la maglietta x 4 per i pantaloni x 2 per le scarpe.

Alla base della combinatoria c’è questo semplice principio che applichiamo quotidianamente: moltiplicando correttamente le possibilità di effettuare delle scelte ottengo tutte le possibilità del caso.

n = n_1 \cdot ... \cdot n_k

Permutazioni

Introduciamo un altro concetto fondamentale della combinatoria – le permutazioni – con un esempio pratico. Se dobbiamo sistemare tre oggetti in tre vani di un armadio, avremo tre possibilità di scelta per il primo, due per il secondo e una per il terzo. Secondo il principio del prodotto avrò quindi 1x 2 x 3 possibilità di mettere gli oggetti nei vani.

Allo stesso modo, se vogliamo determinare tutti i possibili anagrammi di “MANO” (quattro lettere distinte), possiamo sempre ragionare con un modello a scatole: per la prima possiamo scegliere fra quattro lettere, per la seconda tre, e avanti così fino all’ultima quando avremo una sola scelta. Quindi possiamo dire di avere n possibilità, con n = 4 x 3 x 2 x 1.

Notiamo uno schema comune: quando dobbiamo presentare in maniera ordinata degli oggetti finiamo sempre per avere la moltiplicazione del numero di oggetti con tutti i suoi minori fino a 1. In combinatoria questa operazione è chiamata fattoriale.

n!=\prod\limits_{k=1}^{n}k=n\cdot(n-1)\cdot...\cdot 1

Le presentazioni ordinate di oggetti si chiamano permutazioni: in entrambi gli esempi si può pensare che abbiamo dovuto determinare quante diverse possibilità ci fossero di ordinare gli elementi.

Tuttavia ci sono dei casi in cui alcune permutazioni si ripetono. Per esempio, se dovessimo calcolare quanti anagrammi della parola “MAMMA” esistono, ci accorgeremmo che potremmo ottenere “MAMMA” oppure “MAMMA”: per quanto siano permutazioni diverse, danno sempre lo stesso risultato.

Come risolvere il problema delle ripetizioni? Basta dividere la permutazione totale per le permutazioni delle lettere che si ripetono, sempre secondo il principio del prodotto: se le stesse lettere cambiano di posizione, il risultato non cambia.

Anagrammi \space di \space mamma: \frac{5!}{3! \cdot 2!} 

P_n^{k_i}=\frac{n!}{k_1! \cdot...\cdot k_i!}

Disposizioni

In alcuni casi potrebbe essere utile non prendere in considerazione tutti gli elementi che compongono un insieme. Se dovessimo stilare tutte le possibilità di comporre una classifica dei primi dieci concorrenti in una competizione con venti concorrenti come potremmo fare? Potremmo pensare al problema come una permutazione dove i dieci che non consideriamo siano indistinguibili e quindi non aggiungano configurazioni. Oppure ancora, secondo il principio del prodotto, ciò equivarrebbe a moltiplicare tutte le possibilità che abbiamo fino all’11 (20 x 19 x … x 11) e per 1 con tutti i concorrenti che non consideriamo. Questo tipo di presentazione prende il nome di disposizione.

D_k^n=\frac{n!}{(n-k)!}

Se i k elementi scelti fra n si ripetessero potremmo semplicemente applicare il principio del prodotto: n possibilità per il primo, per il secondo, fino al k-esimo.

\overline{D_k^n} = n^k

Combinazioni

Arriviamo ora al tema caldo della combinatoria: giustamente, le combinazioni. Pensiamo di voler determinare tutte le possibilità che abbiamo di formare un comitato di k persone scelte fra n. Rispetto alle disposizioni semplici, l’ordine in cui sono disposti i membri non aumenta le possibili configurazioni: k persone che formano un comitato saranno sempre lo stesso comitato indipendentemente dall’ordine con cui le consideriamo. Ci sono k! possibilità di permutare l’ordine del comitato, ma queste non vanno considerate: si tratta sempre dello stesso comitato. Con le combinazioni siamo quindi unicamente interessati a sapere quanti comitati riusciamo a formare.

Quello che facciamo è dividere le permutazioni totali n! oltre che per i membri che escludiamo (n-k)! anche per le permutazioni di quelli che scegliamo (k!), mantenendo così una sola formazione per tutti i modi possibili che avremmo di ordinarli.

C_k^n=\frac{n!}{(n-k)! \cdot k!}

C_k^n=\frac{D_k^n}{k!}

\begin{pmatrix}
n \\
k
\end{pmatrix}
:=
C_k^n
=
\frac{n!}{(n-k)! \cdot k!}

Il coefficiente binomiale ha una particolarità: per ogni coppia n e k, con k da 0 a n, il valore del coefficiente binomiale corrisponde al k-esimo elemento dell’n-esima riga del triangolo di Tartaglia.

Da questa considerazione segue che, con meno calcolo rispetto a quello richiesto dal triangolo di Tartaglia, è possibile sfruttare il coefficiente binomiale per sviluppare un binomio. I coefficienti di (a+b)ⁿ sono appunto n_k con k = 0, …, n.

Per saperne di più vi consigliamo questo articolo di weschool.

Riassunto delle principali formule della combinatoria

Principio del prodotto

n = n_1 \cdot ... \cdot n_k

Permutazioni

P_n=n!

Permutazioni con ripetizione

P_n^{k_i}=\frac{n!}{k_1!\cdot ...\cdot k_i!}

Disposizioni

D_n^k=\frac{n!}{(n-k)!}

Disposizioni con ripetizione

\overline{D_n^k}=n^k

Combinazioni

C_n^k=\frac{n!}{(n-k)!\cdot k!}