Il calcolo combinatorio è una branca della matematica che ci consente di capire in quanti modi possiamo raggruppare tra loro gli elementi di un insieme finito. Questo è molto importante ed è alla base del calcolo delle probabilità. Esistono tre tipi di raggruppamenti possibili:

  • le permutazioni;
  • le disposizioni;
  • le combinazioni;

Permutazioni

Permutazioni semplici (senza ripetizioni)
Una permutazione di un insieme è una sequenza ordinata nella quale ogni elemento viene presentato una ed una sola volta. Quindi ho \(n\) elementi e voglio disporli nelle \(n\) posizioni dell’insieme che sto considerando: possiamo pensare, per semplicità, che abbiamo \(n\) libri diversi tra loro e vogliamo disporli negli \(n\) spazi di uno scaffale. Prendendo un libro, possiamo notare che abbiamo \(n\) spazi in cui metterlo. Posizioniamolo in uno spazio qualunque. Ora prendiamo un secondo libro e notiamo che questa volta abbiamo \(n-1\) spazi in cui metterlo. Posizioniamo pure questo… procedendo in questo modo dispongo tutti i libri nello scaffale fino all’ultimo, che potrà essere messo nell’unico spazio rimasto. Quindi, mettendo in formule questo ragionamento, il numero di permutazioni \(P_n\) sarà:

$$ P_n = n\cdot (n-1)\cdot….\cdot 2\cdot 1= n!$$


e \(n!\) sarà detto il fattoriale di \(n\).

Permutazioni con ripetizioni
Alcuni insiemi possono contenere elementi che si ripetono! Se vado ad applicare la formula precedente ci sono delle permutazioni che si ripetono, nei diversi modi in cui posso disporre gli elementi. Quindi siano \(i\) gli elementi che si ripetono, rispettivamente \(k_1,…,k_i\) volte, allora stavolta il numero di permutazioni possibili sarà:

$$ P_{n}^{ k_1,…,k_i } =\frac{n!}{k_1!\cdot ….\cdot k_i!}$$


Qui non abbiamo fatto altro che togliere, al numero di permutazioni dell’insieme, il numero delle singole permutazioni degli elementi uguali. Infatti \(k_1!\) è il risultato che otteniamo se permutiamo gli elementi che si ripetono \(k_1\) volte tra loro…. e così via.

Disposizioni

Disposizioni semplici (senza ripetizioni)
Una disposizione semplice di lunghezza \(k\) in un insieme di \(n\) elementi (\(k<n\)) è una presentazione ordinata di \(k\) elementi nella quale gli elementi non si possono ripetere. Qui possiamo procedere come nel caso delle permutazioni semplici, femandoci però a disporre fino a \(k\) elementi. Quindi per il primo elemento abbiamo \(n\) modi di disporlo e procedendo come prima fino al \(k\)-esimo elemento le disposizioni \( D_{n,k} \) saranno

$$ D_{n,k} = n\cdot (n-1)\cdot….\cdot (n-k+2)\cdot (n-k+1)=\frac{n!}{(n-k)!}$$

Disposizioni con ripetizioni
Le disposizioni con ripetizioni sono sempre delle presentazioni ordinate di \(k\) elementi di un insieme di \(n\) elementi, ma qui gli elementi si possono ripetere più volte. Quindi ho \(n\) modi per scegliere il primo elemento della sequenza, n modi per scegliere il secondo e così via, fino a che non arrivo a \(k\) elementi:

$$ D’_{n,k} = \underbrace{n\cdot \cdots \cdot n}_{k-volte}=n^k$$

Combinazioni

Combinazioni semplici
La combinazione semplice è una presentazione non ordinata (non conta l’ordine con cui vengono disposti gli elementi) di \(k\) elementi in un insieme di \(n\) elementi dove non si può ripetere uno stesso elemento più volte. Questo non è altro che una restrizione del caso delle disposizioni, infatti:

$$C_{n,k}=\frac{D_{n,k}}{P_k}=\frac{n!}{k!(n-k)!}=\binom{n}{k}$$


dove non abbiamo fatto altro che togliere tutte le possibili permutazioni della sequenza di \(k\) elementi (tanto l’ordine non conta!) al numero di disposizioni. Con \(\binom{n}{k}\) coefficiente binomiale di \(n\) su \(k\).

Combinazioni con ripetizioni
La combinazione con ripetizione è una presentazione non ordinata di \(k\) elementi in un insieme di \(n\) elementi dove si può ripetere uno stesso elemento più volte. Diamo una formula di questo caso, poiché la motivazione di ciò non è del tutto ovvia:

$$C’_{n,k}=\binom{n+k-1}{k}$$