Abbiamo già visto che da un insieme $S$ di cardinalità $n$ se ne possono estrarre ${n\choose k}$ di cardinalità $k\leq n$. Se $A\in\mathcal{P}_k(S)$, allora chiaramente $A^c\in\mathcal{P}_{n{\bf -}k}(S)$, $S{\bf =}A\cup A^c$ e $A\cap A^c{\bf =}\emptyset$.
Scegliere un sottoinsieme di $S$ di cardinalità $k$ equivale, in altri termini, a scegliere una partizione ordinata di $S$ in un insieme di $k$ elementi e nel suo complementare di $n{\bf -}k$ elementi:
$$ (A,A^c)\in \mathcal{P}_k(S)\times \mathcal{P}_{n{\bf -}k}(S)\ \hbox{.} $$Più in generale , sia $r\geq 1$ un intero e siano $n_1,\dots, n_r\geq 1$ interi tali che $n{\bf =}\sum_{i{\bf =}1}^r n_i$. Indichiamo con $\mathcal{P}_{(n_1,\dots, n_r)}(S)$ l'insieme delle partizioni ordinate di $S$ in $r$ sottoinsiemi disgiunti di cardinalità $n_1,$ $\dots,$ $n_r$ rispettivamente, ovvero
$\mathcal{P}_{(n_1,\dots, n_r)}(S)$ ${\bf =}$ $\{(A_1,\dots, A_r)$ $\in\mathcal{P}_{n_1}(S)\times$ $\dots$ $\times\mathcal{P}_{n_r}(S)$ $:$ $A_i\cap A_j{\bf =}\emptyset$ se $i\not= j\}$.
Ovviamente se $(A_1,\dots, A_r)\in\mathcal{P}_{(n_1,\dots, n_r)}(S)$, allora $S{\bf =}A_1\cup\ldots\cup A_r$, infatti la cardinalità è additiva nelle unioni disgiunte e quindi
$$ \left| \bigcup_i A_i\right| {\bf =}\sum_i\vert A_i\vert {\bf =}\vert S\vert\ \hbox{.} $$Proposizione. L'insieme delle partizioni ordinate di $S$ ha cardinalità
$$ \vert \mathcal{P}_{(n_1,\dots, n_r)}(S)\vert {\bf =} {n!\over n_1!\dots n_r!}\quad \hbox{(K)} $$ Dimostrazione. >Esempio. L'insegnante di una classe di $30$ alunni deve sceglierne $3$ per una ricerca di geografia, $7$ per una ricerca di storia, $10$ per una visita guidata al museo e $7$ per uno stage in biblioteca. Se ogni alunno deve partecipare a un progetto, in quanti modi l'insegnante può scegliere i vari gruppi?
Si tratta di ripartire l'insieme $A$ dei $30$ alunni in $4$ sottoinsiemi: $A_G$ di $6$ alunni, $A_S$ di $7$ alunni, $A_M$ di $10$ alunni e $A_B$ di $7$ alunni. Il numero di scelte possibili sarà dunque ${30!\over 6!\ 7!\ 10!\ 7!}$.
Definizione. Se $n{\bf =}\sum_{i{\bf =}1}^r n_i$, si dice coefficiente multinomiale il numero
$$ {n\choose n_1,\dots,n_r}{\bf =}{n!\over \prod_{i{\bf =}1}^r n_i!}\ \hbox{.} $$Proprietà del coefficiente multinomiale
1. ${n+k\choose n\ ,\ k}$ ${\bf =}$ ${n+k\choose n}$ ${\bf =}$ ${n+k\choose k}$; 2. ${n\choose n_1,\dots,n_r}$ ${\bf =}$ ${n\choose n_1}\cdot$ ${n{\bf -}n_1\choose n_2}\cdot$ $\dots$ $\cdot{n{\bf -}n_1{\bf -}\ldots {\bf -}n_{r{\bf -}1}\choose n_r}$; 3. (Teorema multinomiale) $\forall$ $x_1,$ $\dots,$ $x_r\in\mathbb{R}$ $$ (x_1+\ldots +x_r)^n {\bf =} $$ $$ \sum_{\left.\matrix{(n_1\dots n_r)\hbox{:} \cr n_i\geq 0 \cr \sum n_i{\bf =}n \cr}\right.} {n\choose n_1,\dots ,n_r}x_1^{n_1}\cdot\ldots\cdot x_r^{n_r} $$ (la somma a secondo membro è cioè estesa ai vettori di interi non negativi $(n_1,\dots, n_r)$ tali che $n_1+\ldots +n_r{\bf =}n$); 4. vale la seguente formula di Pascal generalizzata: $${n\choose n_1,\dots, n_r} {\bf =}$$ $$ {\bf =} \sum_{\left.\matrix{i{\bf =}1 \cr n_i\geq 1 \cr}\right.}^r {n{\bf -}1\choose n_1,\dots,n_i{\bf -}1,\dots ,n_r} $$