La formule de Vandermonde

Soient $M$ et $N$ deux ensembles disjoints, de cardinaux $m$ et $n$ , et $E = M \cup N$ , de cardinal $m + n$ . Comptons les parties de $E$ à $r$ éléments.

Premier comptage, direct. Il y en a $(r m + n)$ , par définition.

Second comptage, par tri. Toute partie $X$ à $r$ éléments se scinde en $X \cap M$ et $X \cap N$ , qui sont disjointes et de réunion $X$ . Notons $k = Card (X \cap M)$ ; alors $Card (X \cap N) = r - k$ , et $k$ varie de $0$ à $r$ .

Pour chaque $k$ , choisir $X$ revient à choisir indépendamment $k$ éléments dans $M$ ( $(k m)$ façons) et $r - k$ dans $N$ ( $(r - k n)$ façons), soit $(k m) (r - k n)$ parties. Ces familles sont deux à deux disjointes — $k$ est déterminé par $X$ — et leur réunion est l'ensemble de toutes les parties à $r$ éléments.

Conclusion. Les deux comptages portant sur le même ensemble :

$k = 0 \sum r (k m) (r - k n) = (r m + n) .$

Deux remarques. La disjonction de $M$ et $N$ est essentielle : sans elle, une même partie serait comptée plusieurs fois. Et la convention $(q p) = 0$ pour $q > p$ rend la formule valable sans condition sur $r$ — les termes impossibles s'annulent d'eux-mêmes.

Cas particulier célèbre : $m = n = r$ donne $\sum_{k} (k n)^{2} = (n 2 n)$ , en utilisant $(n - k n) = (k n)$ .

Énoncé

Corrigé

Exercices semblables