Identité de Vandermonde

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques combinatoires, l'identité de Vandermonde, nommée d'après Alexandre-Théophile Vandermonde, affirme que

${n+m \choose r}=\sum_{k=0}^r{n \choose k}{m \choose r-k}.$

Sommaire

1 Preuve
- 1.1 Algébrique
- 1.2 Bijective
2 Distribution de probabilités hypergéométrique
3 Identité de Chu-Vandermonde
4 Lien externe

[modifier] Preuve

[modifier] Algébrique

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 le théorème 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 l'équation du produit de polynômes plus haut et en simplifiant le résultat, 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}$

[modifier] Bijective

Une preuve bijective est aussi possible. Supposons qu'un comité parlementaire soit composé de membres de deux partis politiques seulement, l'un comptant n membres, les « vert », l'autre m membres, les « jaunes ». Combien peut-on former de comités de taile r à partir de ces deux partis? La réponse est bien sûr

${n+m \choose r}.$

Cette valeur est aussi donnée par la somme de toutes les valeurs de k du nombre de comités composé de k verts et r − k jaunes.

[modifier] Distribution de probabilités hypergéométrique

Lorsque les deux côtés de cette identité sont divisés par l'expression à la 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 rouge et m billes bleu. 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 jaune. Alors quelle est la probabilité qu'il y ait exactement k verts dans le comité ? La réponse se trouve dans cette distribution.