Formule de Vandermonde : énoncé (MPSI)
Formule de Vandermonde
Pour $p,q,n\in\mathbb{N}$ : $$\sum_{k=0}^n\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}.$$ Cette formule n'est pas explicitement au programme, mais elle est classique et sa preuve est exigible dans l'esprit du chapitre.
Démonstration : Formule de Vandermonde
Preuve combinatoire
Soit $E=A\cup B$ avec $A$, $B$ disjoints, $\operatorname{Card}A=p$, $\operatorname{Card}B=q$. Alors $\operatorname{Card}E=p+q$ et $\operatorname{Card}\mathcal{P}_n(E)=\binom{p+q}{n}$.
On partage $\mathcal{P}_n(E)$ selon $k=\operatorname{Card}(X\cap A)\in\llbracket0,n\rrbracket$. Une partie $X$ avec $\operatorname{Card}(X\cap A)=k$ est déterminée par le couple $(X\cap A,X\cap B)\in\mathcal{P}_k(A)\times\mathcal{P}_{n-k}(B)$, et tout tel couple convient (sa réunion a $n$ éléments). Il y a donc $\binom{p}{k}\binom{q}{n-k}$ telles parties. Le principe additif donne la formule (les termes avec $k>p$ ou $n-k>q$ sont nuls, ce qui est cohérent).
S’entraîner
- Multiples dans un intervalle d'entiers
- Chemins évitant des points
- Surjections sur un ensemble à trois éléments
- Couples de parties (type CCINP)