Combinazioni
Una combinazione è un sottoinsieme di k elementi estratti da un insieme di n elementi. $$ \begin{pmatrix} n \\ k \end{pmatrix} $$
Se la combinazione è composta da k elementi, è detta combinazione di classe k.
Essendo un insieme, in una combinazione l'ordine degli elementi non è importante.
Esistono due tipi di combinazioni: semplici e con ripetizione.
Le combinazioni semplici
Una combinazione semplice non ha elementi ripetuti al suo interno. $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D(n,k)}{k!} = \frac{n!}{k!(n-k)!} $$ con k intero positivo tale che 0≤k≤n
Per calcolare la combinazione semplice di n oggetti di classe k, divido il numero delle disposizioni semplici D(n,k) per il fattoriale di k ossia k!.
Una combinazione semplice deve essere necessariamente di classe k≤n.
Un esempio
Ho un insieme con le prime tre lettere dell'alfabeto
$$ I = \{ A,B,C \} $$
Voglio trovare le combinazioni di classe 2 semplici, ossia i raggruppamenti possibili delle lettere prese a coppia.
$$ n=3 \\ k=2 $$
Applico la formula per il calcolo delle combinazioni semplici
$$ C_{3,2} = \frac{3!}{2!(3-2)!} = \frac{6}{2} = 3 $$
Le combinazioni semplici possibili sono tre.
E così via.
Le combinazioni con ripetizione
Una combinazione con ripetizione può contenere elementi ripetuti al suo interno. $$ C'_{n,k} = \begin{pmatrix} n+k-1 \\ k \end{pmatrix} = \frac{(n+k-1)!}{k!(n-1)!} $$
Il numero delle combinazioni con ripetizione C' eguaglia le combinazioni semplici C(n+k-1, k).
Un esempio
Ho un insieme con tre lettere
$$ I = \{ A,B,C \} $$
Devo calcolare le combinazioni di classe 2 con ripetizione
$$ n=3 \\ k=2 $$
Detto in altri termini, i raggruppamenti a coppia delle lettere.
In ogni coppia può esserci anche due volte la stessa lettera.
$$ C'_{3,2} = \frac{(3+2-1)!}{2!(3-1)!} = \frac{4!}{2!2!} = \frac{24}{4} = 6 $$
Le combinazioni possibili sono sei.
Le proprietà delle combinazioni
Ci sono importanti proprietà delle combinazioni da tenere a mente
$$ \begin{pmatrix} n \\ 0 \end{pmatrix} = 1 $$
$$ \begin{pmatrix} n \\ 1 \end{pmatrix} = n $$
$$ \begin{pmatrix} n \\ n \end{pmatrix} = 1 $$
$$ \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n \\ n-k \end{pmatrix} $$
Esempio. $$ \begin{pmatrix} 5 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 5-2 \end{pmatrix} $$ $$ \begin{pmatrix} 5 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 3 \end{pmatrix} $$ $$ \frac{5!}{2!(5-2)!} = \frac{5!}{3!(5-3)!} $$ $$ 10 = 10 $$
$$ \begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k-1 \end{pmatrix} $$
Esempio. $$ \begin{pmatrix} 5+1 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 2 \end{pmatrix} + \begin{pmatrix} 5 \\ 2-1 \end{pmatrix} $$ $$ \begin{pmatrix} 6 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 2 \end{pmatrix} + \begin{pmatrix} 5 \\ 1 \end{pmatrix} $$ $$ 15 = 10 + 5 $$
I coefficienti binomiali
I termini n e k di una combinazione sono anche detti coefficienti binomiali perché la combinazione C(n,k) è usata nello sviluppo della potenza di un binomio
$$ (a+b)^n = \sum_{k=0}{n} \begin{pmatrix} n \\ k \end{pmatrix} a^{n-k}b^k $$
Esempio. Devo sviluppare il quadrato n=2 di un binomio (a+b) $$ (a+b)^2 = \begin{pmatrix} 2 \\ 0 \end{pmatrix} a^{2-0}b^0 + \begin{pmatrix} 2 \\ 1 \end{pmatrix} a^{2-1}b^1 + \begin{pmatrix} 2 \\ 2 \end{pmatrix} a^{2-2}b^2 $$ $$ (a+b)^2 = \begin{pmatrix} 2 \\ 0 \end{pmatrix} a^{2} + \begin{pmatrix} 2 \\ 1 \end{pmatrix} ab + \begin{pmatrix} 2 \\ 2 \end{pmatrix} b^2 $$ Calcolo i coefficienti binomiali ossia le combinazioni $$ (a+b)^2 = \frac{2!}{0!(2-0)!} \cdot a^{2} + \frac{2!}{1!(2-1)!} \cdot ab + \frac{2!}{2!(2-2)!} \cdot b^2 $$ $$ (a+b)^2 = \frac{2!}{0! \cdot 2!} \cdot a^{2} + \frac{2!}{1! \cdot 1!} \cdot ab + \frac{2!}{2! \cdot 0!} \cdot b^2 $$ Sapendo che 0! = 1 per convenzione, 1! = 1 e 2!=2·1=2 $$ (a+b)^2 = \frac{2}{1 \cdot 2} \cdot a^{2} + \frac{2}{1 \cdot 1} \cdot ab + \frac{2}{2 \cdot 1} \cdot b^2 $$ $$ (a+b)^2 = \frac{2}{2} \cdot a^{2} + \frac{2}{1} \cdot ab + \frac{2}{2} \cdot b^2 $$ $$ (a+b)^2 = 1 \cdot a^{2} + 2 \cdot ab + 1 \cdot b^2 $$ $$ (a+b)^2 = a^{2} + 2 ab + b^2 $$ Il risultato è il quadrato del binomio. Con lo stesso procedimento si può sviluppare qualsiasi altra potenza ennesima del binomio.
E così via
