Interprétation combinatoire de $\binom{n}{k}$ : énoncé (MPSI)
Interprétation combinatoire de $\binom{n}{k}$
Si $\operatorname{Card}E=n$, alors pour tout $k\in\mathbb{N}$ : $$\operatorname{Card}\mathcal{P}_k(E)=\binom{n}{k}.$$ $\binom{n}{k}$ se lit « $k$ parmi $n$ ».
Démonstration : Interprétation combinatoire de $\binom{n}{k}$
Preuve
Si $k>n$, aucune partie de $E$ n'a $k$ éléments, et $\binom{n}{k}=0$. Si $k=0$, seule $\varnothing$ convient, et $\binom{n}{0}=1$.
Soit $1\le k\le n$ et $L_k$ l'ensemble des $k$-listes d'éléments distincts de $E$. L'application $$\sigma:L_k\to\mathcal{P}_k(E),\quad(y_1,\dots,y_k)\mapsto\{y_1,\dots,y_k\}$$ est bien à valeurs dans $\mathcal{P}_k(E)$ car les $y_i$ sont distincts. Elle est surjective. Une partie $A\in\mathcal{P}_k(E)$ a pour antécédents toutes les façons d'ordonner ses éléments, c'est-à-dire les bijections de $\llbracket1,k\rrbracket$ sur $A$ : il y en a $k!$.
Le lemme des bergers donne $\operatorname{Card}L_k=k!\operatorname{Card}\mathcal{P}_k(E)$, d'où $$\operatorname{Card}\mathcal{P}_k(E)=\frac{1}{k!}\cdot\frac{n!}{(n-k)!}=\binom{n}{k}.$$
Mains de cartes
Un jeu de $32$ cartes contient $4$ as. Une main est une partie à $5$ cartes.
- Nombre de mains : $\binom{32}{5}=\frac{32\times31\times30\times29\times28}{120}=201\,376$.
- Mains avec exactement $2$ as : on choisit les $2$ as parmi $4$, puis les $3$ autres cartes parmi les $28$ qui ne sont pas des as : $\binom{4}{2}\binom{28}{3}=6\times3276=19\,656$.
- Mains avec au moins un as : complémentaire des mains sans as, $\binom{32}{5}-\binom{28}{5}=201\,376-98\,280=103\,096$.
S’entraîner
- Parties emboîtées
- Comité avec président et vice-président
- Applications croissantes
- Parties sans entiers consécutifs et suite de Fibonacci (type CCINP)
- Points fixes et dérangements (type Mines-Ponts)
Dans le cours
Dénombrement : Interprétation combinatoire de $\binom{n}{k}$