Identité de Vandermonde

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques combinatoires, l'identité de Vandermonde, nommée d'après Alexandre-Théophile Vandermonde (1772), 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)!} (parfois aussi notés C_n^k) sont les coefficients binomiaux, « ! » désignant la factorielle.

Preuve[modifier | modifier le code]

Algébrique[modifier | modifier le code]

Elle peut être démontrée de façon algébrique.

Le produit de deux polynômes à une variable est donné par :

\left( \sum_{i=0}^n a_ix^i \right) \left( \sum_{i=0}^m b_ix^i \right) = \sum_{k=0}^{m+n} \left( \sum_{j=0}^k a_jb_{k-j} \right) x^k \quad\text{ avec } m, n \in \mathbb{N}

Par la formule du binôme de Newton, nous savons que

 (1+x)^{m+n} = \sum_{r=0}^{m+n} \binom{m+n}{r}x^r

Nous pouvons transformer cette égalité en produit de polynômes.

    \begin{array}{ll}
          \sum_{r=0}^{m+n} \binom{m+n}{r}x^r  & = (1+x)^{m+n} \\
                                              & = (1+x)^{n} (1+x)^{m} \\
                                              & = \left( \sum_{i=0}^{n} \binom{n}{i}x^i \right) \left( \sum_{j=0}^{m} \binom{m}{j}x^j \right)
    \end{array}

En utilisant le développement du produit donné plus haut, et en identifiant les coefficients, l'identité de Vandermonde apparaît :


    \begin{array}{ll}
        \sum_{r=0}^{m+n} \binom{m+n}{r}x^r & = \sum_{r=0}^{m+n} \left( \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} \right) x^r \\
                        \binom{m+n}{r}x^r  & = \left( \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} \right) x^r \\
                           \binom{n+m}{r}  & = \sum_{k=0}^{r} \binom{n}{k} \binom{m}{r-k} 
    \end{array}

Bijective[modifier | modifier le code]

Une preuve bijective basée sur le dénombrement est aussi possible. Ainsi, en considérant deux ensembles E et F finis et disjoints de cardinaux respectifs m et n, \operatorname{Card} E \cup F = m+n ce qui implique que le nombre de combinaisons de r éléments de EF est égal à

{m+n \choose r}

D’autre part, on peut obtenir toutes les combinaisons en choisissant r éléments dans E et aucun dans F, ou r-1 dans E et un dans Fetc. Les ensembles E et F étant définis disjoints, toutes les combinaisons possibles de r éléments parmi les m+n de EF ont été comptées une seule fois, ce qui donne l’égalité.

Distribution de probabilités hypergéométrique[modifier | modifier le code]

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[modifier | modifier le code]

L'identité de Chu-Vandermonde (publiée par Zhu Shijie en 1303) la généralise pour des valeurs non entières (en utilisant la définition générale des coefficients binomiaux : {z \choose k} = \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!})

{s+t \choose n}=\sum_{k=0}^\infty{s \choose k}{t \choose n-k}

Elle est vraie pour tous nombres complexes s et t.

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

\;_2F_1(a,b;c;1) = \frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)}

\;_2F_1 est la série hypergéométrique et \Gamma(n+1)=n! est la fonction gamma. Il suffit d'appliquer a = -n et l'identité

{n\choose k} = (-1)^k {k-n-1 \choose k} à plusieurs reprises.

Lien externe[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

(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)