La formule de Vandermonde

La stratégie. Une somme de produits de coefficients binomiaux est le signe d'un dénombrement à deux paramètres, trié par cas selon l'un des deux. On fabrique l'ensemble, on le compte globalement, puis par tranches.

a) Le double comptage. Une assemblée compte $m$ femmes et $n$ hommes, $m + n$ personnes en tout ; comptons les délégations de $p$ personnes. Directement : une délégation est une partie à $p$ éléments d'un ensemble à $m + n$ éléments, il y en a $(p m + n)$ . En triant selon le nombre $k$ de femmes : pour $k$ fixé entre $0$ et $p$ , on choisit les $k$ femmes parmi $m$ , soit $(k m)$ façons, puis les $p - k$ hommes parmi $n$ , soit $(p - k n)$ façons ; le principe de multiplication donne $(k m) (p - k n)$ délégations à $k$ femmes. Les classes « exactement $k$ femmes » sont disjointes et recouvrent l'ensemble des délégations — une délégation a un nombre de femmes et un seul. Par le principe d'addition, $(p m + n) = k = 0 \sum p (k m) (p - k n) .$ La convention $(b a) = 0$ pour $b > a$ rend la formule vraie sans restriction : il n'y a pas de délégation à $k$ femmes si $k > m$ .

b) Le coefficient binomial central. Prenons $m = n = p$ . La formule donne $(n 2 n) = k = 0 \sum n (k n) (n - k n)$ , et la symétrie $(n - k n) = (k n)$ — choisir les présents ou les absents — transforme chaque produit en un carré : $(n 2 n) = k = 0 \sum n (k n)^{2} .$ Contrôle pour $n = 3$ : $1 + 9 + 9 + 1 = 20 = (3 6)$ . Pour $n = 4$ : $1 + 16 + 36 + 16 + 1 = 70 = (4 8)$ .

c) Par les polynômes. Dans $R [x]$ , la formule du binôme donne $(1 + x)^{m} = i = 0 \sum m (i m) x^{i}$ et $(1 + x)^{n} = j = 0 \sum n (j n) x^{j}$ . Le coefficient de $x^{p}$ dans le produit de deux polynômes est la somme, sur les couples $(i, j)$ avec $i + j = p$ , des produits des coefficients (chapitre 10) : c'est $k = 0 \sum p (k m) (p - k n)$ . Or le produit vaut $(1 + x)^{m + n}$ , dont le coefficient de $x^{p}$ est $(p m + n)$ . Deux polynômes égaux ont les mêmes coefficients : on retrouve a). Le double comptage est le même raisonnement, où le rôle du produit de polynômes est tenu par le tri.

Ce que l'exercice installe. Trier par cas selon un paramètre : une somme de produits de deux coefficients binomiaux est toujours un « $k$ d'un côté, $p - k$ de l'autre ». Ce sera, au chapitre 19, la loi de la somme de deux variables binomiales indépendantes — la formule de Vandermonde y est exactement le calcul de la loi de $X + Y$ .

Énoncé

Corrigé