Identité de Vandermonde

En mathématiques combinatoires, l'identité de Vandermonde, ou formule de Vandermonde, ainsi nommée en l'honneur d'Alexandre-Théophile Vandermonde (1772), ou encore formule de convolution, affirme que, pour des entiers naturels ${\displaystyle k,m,n}$, on a

${\displaystyle {\binom {m+n}{k}}=\sum _{\overset {0\leqslant i,j\leqslant k}{i+j=k}}{\binom {m}{i}}{\binom {n}{j}}=\sum _{i=0}^{k}{\binom {m}{i}}{\binom {n}{k-i}}=\sum _{j=0}^{k}{\binom {m}{k-j}}{\binom {n}{j}}}$

où les nombres ${\displaystyle {b \choose a}}$, avec ${\displaystyle a,b\in \mathbb {N} }$, sont des coefficients binomiaux, c'est-à-dire que ${\displaystyle {b \choose a}={\frac {b!}{a!\,(b-a)!}}}$ si ${\displaystyle 0\leqslant a\leqslant b}$ (le point d'exclamation « ! » désignant la factorielle) et ${\displaystyle {b \choose a}=0}$ si ${\displaystyle a>b}$.

Les contributions non nulles à la somme de droite proviennent des valeurs de j pour lesquelles les coefficients binomiaux sont non nuls, c'est-à-dire pour ${\displaystyle \max(0,k-m)\leqslant j\leqslant \min(n,k)}$.

Le cas ${\displaystyle n=m=k}$ donne l'expression suivante du coefficient binomial central : ${\displaystyle {\binom {2n}{n}}=\sum _{i=0}^{n}{\binom {n}{i}}^{2}}$.

Démonstrations

Algébrique

La formule peut être démontrée de façon algébrique^[1], en utilisant la formule du binôme pour développer de deux façons l'identité polynomiale

${\displaystyle (1+X)^{m+n}=(1+X)^{m}(1+X)^{n}}$

puis en identifiant les coefficients du terme de degré ${\displaystyle k}$ de chacun des membres de l'égalité.

Combinatoire

Une preuve par double dénombrement est aussi possible^[2] : les deux expressions correspondent à deux façons de dénombrer les parties à ${\displaystyle k}$ éléments de E ∪ F, où E et F sont deux ensembles disjoints fixés, de cardinaux respectifs ${\displaystyle m}$ et ${\displaystyle n}$.

Probabiliste

Les ensembles E et F précédents sont modélisés par une urne contenant ${\displaystyle m}$ boules rouges et ${\displaystyle n}$ boules bleues. On effectue un tirage sans remise de ${\displaystyle k}$ boules. On demande la loi de probabilité du nombre ${\displaystyle X}$ de boules rouges ; la réponse est ${\displaystyle P(X=i)={\frac {{\binom {m}{i}}{\binom {n}{k-i}}}{\binom {n+m}{k}}}}$ (il s'agit de la loi hypergéométrique).

L'identité de Vandermonde s'interprète alors comme le fait que la somme de ces probabilités est égale à 1.

Identité de Chu-Vandermonde

L'identité de Chu-Vandermonde — du nom de Vandermonde et du mathématicien chinois Zhu Shijie (environ 1260 - environ 1320)^[3] — généralise l'identité de Vandermonde à des valeurs non entières (en utilisant la définition générale des coefficients binomiaux) :

${\displaystyle {\binom {s+t}{n}}=\sum _{k=0}^{n}{\binom {s}{k}}{\binom {t}{n-k}}}$,

qui vient d'une réécriture de la « formule du binôme pour les factorielles décroissantes » établie par Vandermonde^[4], exprimant que la suite des polynômes ${\displaystyle x^{\underline {n}}=x(x-1)(x-2)\cdots (x-n+1)}$ est de type binomial :

${\displaystyle (s+t)^{\underline {n}}=\sum _{k=0}^{n}{n \choose k}s^{\underline {n-k}}~t^{\underline {k}}}$.

L'identité de Chu-Vandermonde est vraie pour tous nombres complexes s et t.

Elle est elle-même un cas particulier du théorème hypergéométrique de Gauss qui affirme que

${\displaystyle _{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (c-a-b)}{\Gamma (c-a)\Gamma (c-b)}}}$

où ₂F₁ est la fonction hypergéométrique et Γ est la fonction gamma. Il suffit de prendre a = –n et d'appliquer l'identité

${\displaystyle {\binom {n}{k}}=(-1)^{k}{\binom {k-n-1}{k}}}$ à plusieurs reprises.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Vandermonde's identity » (voir la liste des auteurs).

1. Voir par exemple (en) Thomas Koshy, Catalan Numbers with Applications, Oxford University Press, 2008 (lire en ligne), p. 92, ou cet exercice corrigé sur Wikiversité.
2. Voir par exemple Steeve Sarfati et Matthias Fegyvères, Mathématiques : méthodes, savoir-faire et astuces, Bréal, 1997 (lire en ligne), p. 402, ou cet exemple de la leçon « Sommation » sur Wikiversité.
3. (en) Richard P. Stanley, Enumerative Combinatorics, vol. 1, CUP, 2011, 2^e éd. (lire en ligne), p. 97.
4. V.-A. Lebesgue, « Mémoire sur une formule de Vandermonde et son application à la démonstration d'un théorème de M. Jacobi », J. Math. Pures Appl., 1^re série, vol. 6,‎ 1841, p. 17-35 (lire en ligne).

Voir aussi

• q-analogue de l'identité de Vandermonde

Lien externe

(en) BinomialCoefficients contient quelques démonstrations de l'identité de Vandermonde

• Arithmétique et théorie des nombres