Soit $E$ un ensemble à $n$ éléments et $j,k$ des entiers tels que $0\le j\le k\le n$.
- En dénombrant de deux façons l'ensemble $$X=\{(B,A)\in\mathcal P(E)^2\mid B\subset A,\ \operatorname{Card}B=j,\ \operatorname{Card}A=k\},$$ démontrer que $$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}.$$
- Retrouver cette égalité par le calcul avec les factorielles.
- En déduire, pour $0\le j\le n$ : $$\sum_{k=j}^n\binom{n}{k}\binom{k}{j}=\binom{n}{j}2^{n-j}.$$
- Vérifier ce résultat pour $n=4$ et $j=2$.
Premier comptage : choisir d'abord la grande partie $A$.
Second comptage : choisir d'abord $B$ ; une partie $A$ contenant $B$ est déterminée par $A\setminus B$.
Pour la question 3, poser $i=k-j$ et reconnaître une somme classique.
- Premier comptage : on choisit d'abord $A\in\mathcal P_k(E)$ ($\binom nk$ choix), puis $B\in\mathcal P_j(A)$ ($\binom kj$ choix, puisque $\operatorname{Card}A=k$). Le nombre de choix de $B$ ne dépend pas de $A$, donc $\operatorname{Card}X=\binom nk\binom kj$.
Second comptage : on choisit d'abord $B\in\mathcal P_j(E)$ ($\binom nj$ choix). Une partie $A$ à $k$ éléments contenant $B$ s'écrit de façon unique $A=B\cup C$ avec $C=A\setminus B\in\mathcal P_{k-j}(E\setminus B)$. Réciproquement, toute telle partie $C$ fournit une partie $A=B\cup C$ convenable (réunion disjointe de cardinal $j+(k-j)=k$). Comme $\operatorname{Card}(E\setminus B)=n-j$, il y a $\binom{n-j}{k-j}$ choix de $C$. Donc $\operatorname{Card}X=\binom nj\binom{n-j}{k-j}$.
Les deux expressions valent $\operatorname{Card}X$ : elles sont égales.
-
On a $$\binom nk\binom kj=\frac{n!}{k!\,(n-k)!}\cdot\frac{k!}{j!\,(k-j)!}=\frac{n!}{j!\,(k-j)!\,(n-k)!}$$ et, comme $(n-j)-(k-j)=n-k$, $$\binom nj\binom{n-j}{k-j}=\frac{n!}{j!\,(n-j)!}\cdot\frac{(n-j)!}{(k-j)!\,(n-k)!}=\frac{n!}{j!\,(k-j)!\,(n-k)!}.$$
-
On somme l'égalité de la question 1 pour $k\in\llbracket j,n\rrbracket$, puis on pose $i=k-j$ : $$\sum_{k=j}^n\binom nk\binom kj=\binom nj\sum_{k=j}^n\binom{n-j}{k-j}=\binom nj\sum_{i=0}^{n-j}\binom{n-j}{i}=\binom nj2^{n-j},$$ en utilisant $\sum_{i=0}^m\binom mi=2^m$.
Interprétation : on compte les couples $(B,A)$ avec $B\subset A\subset E$ et $\operatorname{Card}B=j$, sans contrainte sur le cardinal de $A$ ; une fois $B$ choisi, $A\setminus B$ est une partie quelconque de $E\setminus B$.
- Pour $n=4$, $j=2$ : $\binom42\binom22+\binom43\binom32+\binom44\binom42=6+12+6=24$, et $\binom42\times2^2=24$.
$\sum_{k=j}^n\binom nk\binom kj=\binom nj2^{n-j}$ ; $24$ pour $n=4$, $j=2$