Calcolo combinatorio

Il calcolo combinatorio è quella branchia 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