Coefficiente binomiale
Dati $n, k in mathbb{N}$, con $n ge k$, si definisce coefficiente binomiale di $n$ su $k$
$((n),(k)) = frac{n!}{k! (n-k)!}$
Esempio: $((4),(2)) = frac{4!}{2! (4-2)!} = frac{4!}{2! cdot 2!} = frac{4 cdot 3 cdot 2 cdot 1}{2 cdot 1 cdot 2 cdot 1} = 6$
Proprietà del coefficiente binomiale
I coefficienti binomiali rispettano le seguenti proprietà
$((n),(0)) = ((n),(n)) = 1 quad forall n in mathbb{N}$
$((n),(1)) = ((n),(n – 1)) = n quad forall n in mathbb{N}$
$((n),(k)) = ((n),(n-k)) quad forall n,k in mathbb{N}$, $n ge k$
$((n+1),(k+1)) = ((n),(k+1)) + ((n),(k)) quad forall n,k in mathbb{N}$, $n ge k$
$sum_{k=0}^n ((n),(k)) a^k b^{n-k} = (a+b)^n$
In particolare, dall’ultima proprietà discende che
$sum_{k=0}^n ((n),(k)) = 2^n quad forall n in mathbb{N}$
Coefficiente multinomiale
Dati $r+1$ numeri naturali, $n, k_1, k_2, ldots, k_r in mathbb{N}$, tali che $k_1 + k_2 + ldots + k_r = n$, si definisce coefficiente multinomiale
$((n),(k_1"," k_2"," ldots"," k_r)) = frac{n!}{k_{1}! cdot k_{2}! cdot ldots cdot k_{r}!} = frac{n!}{prod_{i=1}^r k_{i}!}$
e comunque si scelgano i numeri naturali $n, k_1, k_2, ldots, k_r$ (purché $k_1 + k_2 + ldots + k_r = n$), risulta
$((n),(k_1"," k_2"," ldots"," k_r)) in mathbb{N}$
Proprietà del coefficiente multinomiale
Fissato $n in mathbb{N}$, e detto $A_n subset mathbb{N}^r$ l’insieme di tutte le $r$-ple di naturali $(k_1, k_2, ldots, k_r)$ tali che $k_1 + k_2 + ldots + k_r = n$, risulta
$(x_1 + x_2 + ldots + x_r)^n = sum_{(k_1, k_2, ldots, k_r) in A_n} ((n),(k_1"," k_2"," ldots"," k_r)) cdot x_1^{k_1} cdot x_2^{k_2} cdot ldots cdot x_r^{k_r}$
Permutazioni semplici
Dato un insieme $X$ con $n$ elementi, si chiama permutazione ogni ordinamento dell’insieme $X$. Equivalentemente, dati $n$ oggetti distinti, il numero di permutazioni $P_n$ è il numero di tutti i possibili ordinamenti degli $n$ oggetti, e risulta
$P_n = n!$
Esempio: in quanti modi diversi si possono disporre $10$ persone in fila? Risposta: $10!$
Permutazioni con ripetizione
Dati $n$ oggetti non tutti distinti fra di loro, un ordinamento di tali oggeti si chiama permutazione con ripetizione. Supponiamo di poter suddividere gli $n$ oggetti in $h$ tipi diversi (ovviamente $h le n$). Siano $n_i$ il numero di elementi di tipo $i$, per ogni $i=1, 2, ldots, h$, allora $n = n_1 + n_2 + ldots + n_h$. Indicando con $P_{n_1, n_2, ldots, n_h}^{**}$ il numero delle permutazioni con ripetizione, ovvero il numero di tutti i possibili ordinamenti degli $n$ oggetti, risulta
$P_{n_1, n_2, ldots, n_h}^{**} = frac{n!}{n_{1}! cdot n_{2}! cdot ldots cdot n_{h}!}$
Esempio: Quanti sono i possibili anagrammi della parola matematica?
Si hanno in totale $10$ elementi, visto che la parola matematica è costituita da $10$ lettere. Tali lettere non sono tutte distinte, ma possono essere partizionate in $6$ tipi diversi
1° tipo: lettera m, $n_1 = 2$
2° tipo: lettera a, $n_2 = 3$
3° tipo: lettera t, $n_3 = 2$
4° tipo: lettera e, $n_4 = 1$
5° tipo: lettera i, $n_5 = 1$
6° tipo: lettera c, $n_6 = 1$
Per determinare il numero di tutti i possibili anagrammi della parola matematica basta calcolare le permutazioni con ripetizione
$frac{10!}{2! cdot 3 ! cdot 2! cdot 1! cdot 1! cdot 1!} = 10 cdot 9 cdot 8 cdot 7 cdot 6 cdot 5 = 151200$
Combinazioni semplici
Dato un insieme $X$ con cardinalità $n$ (quindi contenente $n$ elementi distinti), ogni sottoinsieme di $X$ con $k$ elementi ($0 le k le n$) viene detto combinazione di $n$ oggetti di classe $k$, e si indica con $C_{n,k}$.
$C_{n,k}$ rappresenta il numero di tutti possibili modi con cui si possono scegliere $k$ elementi fra $n$ oggetti dati, e risulta
$C_{n,k} = ((n),(k)) = frac{n!}{k! (n-k)!}$
ed inoltre
$C_{n,k} = frac{n!}{k! (n-k)!} = P_{k, n-k}^{**}$
Esempio: Quanti sono i possibili sottoinsiemi di un insieme $n$ elementi? I possibili sottoinsiemi possono essere l’insieme vuoto, gli insiemi con $1$ elemento, gli insiemi con $2$ elementi, etc. Quindi il numero di tutti i possibili sottoinsiemi è
$sum_{k=0}^n ((n),(k)) = 2^n$
Combinazioni con ripetizione
Dato un insieme $X$ di cardinalità $n$, ossia dati $n$ oggetti distinti, ogni raggruppamento di $k$ elementi di $X$, ammettendo anche ripetizioni di oggetti, viene detto combinazione con ripetizione di $n$ oggetti di classe $k$. Notare che $k$ può essere maggiore di $n$, e in ogni raggruppamento non conta l’ordine con cui vengono elencati gli elementi. Indicando con $C_{n,k}^{**}$ il numero di tutte le possibili combinazioni con ripetizione di $n$ oggetti di classe $k$, risulta
$C_{n,k}^{**} = ((n+k-1),(k))$
Esempio: Dato $X = {a, b, c, d}$, quante sono le possibili coppie formate da elementi di $X$, ammettendo anche ripetizioni, senza contare l’ordine con cui tali elementi sono elencati? Risposta: $C_{4,2} = ((4+2-1),(2)) = ((5),(2)) = 10$. E infatti tutte le coppie possibili sono
Esempio: In quanti modi si possono scegliere $5$ carte da un mazzo di $40$ con rimpiazzo? Risposta: $C_{40,5}^{**} = ((40 + 5 – 1),(5)) = ((44),(5))$
Disposizioni semplici
Dati $n$ oggetti, ogni ordinamento di $k$ oggetti ($0 le k le n)$ comunque scelti fra gli $n$ si chiama disposizione di $n$ oggetti di classe $k$. Notare che due disposizioni possono differire o per gli oggetti contenuti o per l’ordine degli oggetti. Il numero di tutte le possibili disposizioni di $n$ oggetti di classe $k$ si indica con $D_{n,k}$ e risulta
$D_{n,k} = frac{n!}{(n-k)!} = n cdot (n-1) cdot ldots cdot (n-k+1)$
Esempio: Da un’urna contenente $90$ palline numerate, quante sono le possibili sequenze di $5$ numeri che si possono ottenere estraendo, senza rimpiazzo, cinque palline? Risposta: $D_{90,5} = frac{90!}{85!}$
Disposizioni con ripetizione
Dati $n$ oggetti, ogni ordinamento di $k$ oggetti in cui sono ammesse anche ripetizioni (quindi $k$ può essere qualsiai) si chiama disposizione con ripetizione di $n$ oggetti di classe $k$. Indicando con $D_{n,k}^{**}$ il numero di tutte le possibili disposizioni con ripetizioni di $n$ oggetti di classe $k$, risulta
$D_{n,k}^{**} = n^k$
Esempio: Da un’urna contenente $90$ palline numerate, quante sono le possibili sequenze di $5$ numeri che si possono ottenere estraendo, con rimpiazzo, cinque palline? Risposta: $D_{90,5}^{**} = 90^5$
Esempio: quante sono le parole di $4$ lettere che si possono formare utilizzando le lettere ${a,b,c,d,e}$? Risposta: $D_{5,4}^{**} = 5^4$.