Identité de Vandermonde

En mathématiques combinatoires, l'identité de Vandermonde, ainsi nommée en l'honneur d'Alexandre-Théophile Vandermonde (1772), ou formule de convolution, affirme que

{n+m \choose r}=\sum _{k=0}^{r}{n \choose k}{m \choose r-k}

,

où les nombres ${n \choose k}={\frac {n!}{k!\,(n-k)!}}$ sont les coefficients binomiaux, « ! » désignant la factorielle.

Preuves

Algébrique

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

(1+X)^{m+n}=(1+X)^{m}(1+X)^{n}

puis en identifiant les coefficients.

Bijective

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

Distribution de probabilités hypergéométrique

Lorsque les deux côtés de cette identité sont divisés par l'expression de gauche, alors les termes obtenus peuvent être interprétés comme des probabilités, lesquelles sont donnés par la distribution hypergéométrique. C'est la probabilité de tirer des billes rouges en r tirages sans remise d'une urne contenant n billes rouges et m billes bleues. Par exemple, supposons qu'une personne est responsable de créer un comité de r membres tirés au hasard parmi n verts et m jaunes. Alors quelle est la probabilité qu'il y ait exactement k verts dans le comité ? La réponse se trouve dans cette distribution.

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 :

{\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 $x^{\underline {n}}=x(x-1)(x-2)\cdots (x-n+1)$ est de type binomial (en) :

(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

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

où $2 F 1$ est la fonction hypergéométrique et $Γ$ est la fonction gamma. Il suffit de prendre $a = - n$ et d'appliquer l'identité

{\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).

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é.
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é.
(en) Richard P. Stanley, Enumerative Combinatorics, vol. 1, CUP, 2011, 2^e éd. (lire en ligne), p. 97.
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

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[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).