Definizione. Dati i numeri interi $n$,$k$ tali che $0\leq k\leq n$, si chiama coefficiente binomiale la quantità
$$ {n\choose k} {\bf =} {n!\over k!(n{\bf -}k)!}\ \hbox{.} $$Proposizione. Dato un insieme $S$ di cardinalità $n$, l'insieme
$$ \mathcal{P}_k(S){\bf =}\{ A\in\mathcal{P}(S):\ \vert A\vert {\bf =}k\} $$dei sottoinsiemi di $S$ di cardinalità $k\leq n$ contiene ${n\choose k}$ elementi.
Dimostrazione. >Osservazione. In parole povere, ${n\choose k}$ è anche il numero di sottoinsiemi di $k$ oggetti che si possono formare con un insieme di $n$ oggetti, senza tenere conto dell'ordine.
Esempio. Quanti comitati composti da 2 donne e 3 uomini si possono formare a partire da un gruppo di 5 donne e un gruppo di 7 uomini? Abbiamo ${5\choose 2}$ possibili insiemi di 2 donne e ${7\choose 3}$ possibili insiemi di 3 uomini, quindi, per il principio di moltiplicazione ci sono
$${5\choose 2}{7\choose 3}=\frac{5\cdot 5}{2}\frac{7\cdot 6\cdot 5}{3\cdot 2}=350$$comitati possibili.
1. Per convenzione si pone ${n\choose k}{\bf =}0$ se gli interi $n$, $k$ sono tali che $n>0$ e $k<0$ oppure se $k>n$;
2. grazie alla convenzione $0!{\bf =}1$, risulta ${n\choose \hbox{o}}{\bf =}{n\choose n}{\bf =}1$;
3. se $n$, $k$ sono interi tali che $0\leq k\leq n$, allora vale la seguente proprietà di simmetria:
$$ {n\choose k}{\bf =}{n\choose n{\bf -}k}\ \hbox{;} $$4. per ogni $n\geq 2$ risulta ${n\choose 2}=\frac{1}{2}n(n-1)$;
5. vale la seguente formula di Pascal $\forall\ n>1$ e per $1\leq k<n$:
$$ {n\choose k}{\bf =}{n{\bf -}1\choose k{\bf -}1}{\bf +}{n{\bf -}1\choose k}\ \hbox{;} $$ Dimostrazione. >6. sviluppando i coefficienti binomiali si dimostra facilmente la seguente uguaglianza:
$$ k{n\choose k}=n{n-1\choose k-1}\ \hbox{;} $$7. vale la seguente proprietà di ricorrenza:
$$ {n\choose k{\bf +}1}{\bf =}{n\choose k}\cdot {n{\bf -}k\over k{\bf +}1}\ \hbox{;} $$8. vale la seguente formula di Vandermonde:
$$ \sum_{j=0}^k{n\choose j}{m\choose k{\bf -}j}{\bf =}{n+m\choose k} $$per $n$, $m\geq 0$;
9. se $n$ è un intero positivo, per ogni coppia di interi positivi $h$,$k$, vale la seguente identità combinatoria :
$$ {h{\bf +}k\choose h}{n\choose h{\bf +}k}={n\choose h}{n{\bf -}h\choose k}\ \hbox{.} $$Teorema (binomiale). Per ogni $x$, $y\in\mathbb{R}$ risulta
$$ (x{\bf +}y)^n{\bf =}\sum_{r{\bf =}0}^n{n\choose r}x^ry^{n{\bf -}r}\ \hbox{.} $$Osservazione. Insiemisticamente parlando, la proprietà 3 corrisponde al fatto che, dato un insieme $S$ di cardinalità $n$ e un intero $0\leq k\leq n$, scegliere un sottoinsieme $A\subseteq S$ di cardinalità $k$ equivale a scegliere il suo complementare $A^c\subseteq S$, ovvero un insieme di cardinalità $n{\bf -}k$:
$$ \vert \mathcal{P}_k(S)\vert {\bf =} \vert \mathcal{P}_{n{\bf -}k}(S)\vert\ \hbox{.} $$Dunque ${n\choose k}$ è anche il numero di ripartizioni differenti di una popolazione di $n$ individui in due sottopopolazioni composte rispettivamente da $k$ e $n{\bf -}k$ individui ciascuna. Basta infatti mettere in corrispondenza biunivoca le ripartizioni con le combinazioni semplici, associando alla ripartizione $(\{i_1,\dots, i_k\},S\setminus \{i_1,\dots, i_k\})$ la combinazione $\{i_1,\dots, i_k\}$.
Si noti che all'interno della sottopopolazione l'ordine non conta, mentre conta invece l'ordine delle due sottopopolazioni: se $n{\bf =}2$ e $k{\bf =}1$, si hanno le due ripartizioni distinte $(\{1\},\{2\})$ e $(\{2\},\{1\})$.
Osservazione. Il coefficiente binomiale ${n\choose k}$ è il numero di disposizioni in $n$ posti di $\{a,b\}$, dove $a$ si ripete $k$ volte e $b$ si ripete $n{\bf -}k$ volte. Consideriamo infatti l'insieme delle combinazioni semplici di $\{1,\dots, n\}$ in $k$ posti (che sappiamo essere ${n\choose k}$) e mettiamo tale insieme in corrispondenza biunivoca con il nostro insieme di ripartizioni: si associa a ogni combinazione $[(i_1,\dots, i_k)]$ la disposizione $(j_1,\dots, j_n)$, dove $j_h{\bf =}a$ $\Leftrightarrow$ $h\in\{i_1,\dots, i_k\}$.
Esercizio. Provare che la corrispondenza precedente è ben definita e biunivoca.