Calcolo combinatorio

Il calcolo combinatorio è quella branca della matematica che studia i modi per raggruppare e ordinare gli elementi di un insieme di oggetti. Un problema di tipo combinatorio è legato al concetto di contare tali modi, detti configurazioni e viene solitamente posto in termini di domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni..." ecc... .

Più formalmente, dato un insieme di ${\displaystyle n}$ oggetti si vuole contare le configurazioni che possono assumere ${\displaystyle k}$ oggetti tratti da questo insieme. Prima di affrontare un problema combinatorio bisogna capire due fatti importanti:

• Se l'ordinamento è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento (Es.: ${\displaystyle (x,y,z)}$ è uguale a ${\displaystyle (z,x,y)}$ ? )
• Se si possono avere più ripetizioni di uno stesso oggetto, ovvero se uno stesso oggetto dell'insieme può o meno essere riusato più volte all'interno di una stessa configurazione.

Permutazioni

Una permutazione è un riodinamento di un insieme di oggetti ed ogni oggetto può essere considerato al più una volta. Per contare quante siano le permutazioni di un insieme con n oggetti si osservi che il primo elemento della configurazione può essere scelto in ${\displaystyle n}$  modi diversi, il secondo in ${\displaystyle (n-1)}$ , il terzo in ${\displaystyle (n-2)}$  e così via sino all'ultimo che potrà essere preso in un solo modo essendo l'ultimo rimasto. Dunque, indicando con ${\displaystyle P_{n}}$  il numero delle possibili permutazioni si ottiene che esse sono esattamente ${\displaystyle n!}$  (${\displaystyle n}$  fattoriale):

${\displaystyle P_{n}=n\times (n-1)\times (n-2)\times \dots \times 1=n!}$ 

Esempio:

Disposizioni

Configurazioni ordinate di dimensione k senza ripetizioni

Una disposizione semplice è un ordinamento degli elementi nella quale non si possono avere ripetizioni di uno stesso oggetto. In questo caso si è interessati al numero di configurazioni che si possono creare prendendo ${\displaystyle k}$  oggetti distinti da un insieme di ${\displaystyle n}$  oggetti. Il primo può essere scelto in ${\displaystyle n}$  modi diversi, il secondo in ${\displaystyle (n-1)}$  e così via sino al ${\displaystyle k-esimo}$  che può essere scelto in ${\displaystyle (n-k+1)}$  modi diversi. Pertanto il numero di disposizioni semplici ${\displaystyle D_{n}^{k}}$  di ${\displaystyle k}$  oggetti su un insieme di ${\displaystyle n}$  oggetti è dato dal numero di permutazioni totali da cui si devono togliere gli oggetti non presi in considerazione, ovvero:

${\displaystyle D_{n}^{k}=P_{n}^{k}=n\times (n-1)\times \dots \times (n-k+1)={\frac {n\times (n-1)\times \dots \times 1}{(n-k)\times (n-k-1)\times \dots \times 1}}={\frac {n!}{(n-k)!}}}$ 

A titolo di ossservazione si noti come il numero di permutazioni di un insieme di oggetti sia effettivamente il numero di disposizioni semplici che si possono operare sugli stessi prendendoli ${\displaystyle n}$  per volta:

${\displaystyle P_{n}=D_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}={\frac {n!}{1}}=n!}$ 

Esempio:

Configurazioni ordinate di dimensione k con ripetizioni

Se l'ordine è rilevante nella configurazione ed è possibile avere ripetizioni di uno stesso elemento si parla di disposizioni con ripetizione. Quello che si sta cercando è il numero delle possibili sequenze di ${\displaystyle k}$  elementi scegliendoli da un insieme di ${\displaystyle n}$  oggetti e ognuno di essi può essere preso più volte. Si hanno dunque ${\displaystyle n}$  possibilità per scegliere il primo elemento, ${\displaystyle n}$  per il secondo ed altrettante per il terzo e così via sino al ${\displaystyle k-esimo}$  che completa la configurazione. Il numero di disposizioni con ripetizioni è pertanto:

${\displaystyle DR_{n}^{k}={\underbrace {n_{1}\times n_{2}\times \dots \times n_{k}} \atop {k-volte}}=n^{k}}$ 

Esempio:

Combinazioni

Configurazioni non ordinate di dimensione k senza ripetizioni

Si chiama combinazione semplice una configurazione in cui non ha importanza l'ordine degli elementi e non si può riperete lo stesso elemento più volte. Potendo scegliere ${\displaystyle k}$  elementi da ${\displaystyle n}$  oggetti distintiti si devono calcolare le permutazioni dei ${\displaystyle k}$  oggetti e togliere tutte le sequenze uguali a meno di un ordinamento. Le prime sono esattamente le disposizioni semplici mentre le ultime sono le permutazioni possibili della sequenza, ovvero ${\displaystyle k!}$ :

${\displaystyle C_{n}^{k}={n \choose k}={\frac {D_{n}^{k}}{k!}}={\frac {n!}{k!(n-k)!}}}$ 

Esempio:

Configurazioni non ordinate di dimensione k con ripetizioni

Quando l'ordine non è importante ma è possibile avere ripetizione degli elementi si parla di combinazioni con ripetizione. In questo caso un elemento ${\displaystyle n}$  può essere ripetuto fino a ${\displaystyle k}$  volte ma bisogna sempre eliminare tutte le sequenze simili a meno di un ordinamento:

${\displaystyle CR_{n}^{k}={\frac {DR_{n}^{k}}{k!}}={\frac {\underbrace {n_{1}\times \dots \times n_{k}} \atop {k-volte}}{k!}}={\frac {n\times [(n-1)+1]\times [(n-2)+2]\times \dots \times [(n-k)+k]}{k!}}=}$ 

${\displaystyle ={\frac {(n+k-1)!}{k!(n-1)!}}={\frac {(n+k-1)!}{k!(n+k-1-k)!}}}$ 

riscrivibile quindi come

${\displaystyle CR_{n}^{k}={n+k-1 \choose k}}$ 

Esempio: