Calcolo combinatorio

Il calcolo combinatorio è il termine che denota tradizionalmente la branca della matematica che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un insieme finito di oggetti. I Il calcolo combinatorio si interessa soprattutto di contare tali modi, ovvero le configurazioni e solitamente risponde a domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni..." ecc... .

Più formalmente, dato un insieme S 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 di un insieme di oggetti è una presentazione ordinata, cioè una sequenza, dei suoi elementi nella quale ogni oggetto viene presentato una ed una sola 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\cdot (n-1)\cdot (n-2)\cdot \dots \cdot 1=n!}$ 

Ad esempio le permutazioni degli elementi dell'insieme {a,b,c} sono 3! = 6:
abc, acb, bac, bca, cab, cba.

Disposizioni senza ripetizioni

Una disposizione semplice di lunghezza k di elementi di un insieme S di n oggetti, con k ≤ n, è una presentazione ordinata di k elementi di S nella quale non si possono avere ripetizioni di uno stesso oggetto. Per avere il numero di queste configurazioni si considera che il primo componente di una tale sequenza 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 ${\displaystyle D_{n}^{k}}$  di disposizioni semplici di ${\displaystyle k}$  oggetti estratti da un insieme di ${\displaystyle n}$  oggetti è dato dal prodotto:

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

Ad esempio le disposizioni semplici di lunghezza 2 degli elementi dell'insieme {1,2,3,4,5} sono ${\displaystyle 5\cdot 4=20}$ :
12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.

Si osserva che le permutazioni sono casi particolari delle disposizioni semplici: le permutazioni di un insieme di n oggetti sono le disposizioni semplici di tali oggetti di lunghezza n. In effetti per il loro numero:

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

Disposizioni con ripetizioni

Una presentazione ordinata di elementi di un insieme nella quale si possono avere ripetizioni di uno stesso elemento si dice disposizione con ripetizioni. Cerchiamo il numero delle possibili sequenze di ${\displaystyle k}$  oggetti che riproducono gli elementi di un insieme di ${\displaystyle n}$  oggetti ognuno dei quali può essere preso più volte. Si hanno ${\displaystyle n}$  possibilità per scegliere il primo componente, ${\displaystyle n}$  per il secondo ed altrettante per il terzo e così via sino al ${\displaystyle k-esimo}$  che completa la configurazione. Il numero cercato è pertanto:

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

Ad esempio le disposizioni con ripetizione di lunghezza 2 degli elementi di {1,2,3,4,5} sono ${\displaystyle 5\cdot 5=25}$ :
11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.

Combinazioni 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)!}}}$ 

Ad esempio le combinazioni semplici di :

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}}$ 

Ad esempio le combinazioni con ripetizione di :