Subjects combinatorics

Vandermonde Identity 60019F

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Use the AI math solver

1. **Énoncé du problème :** Montrer l'identité de Vandermonde suivante : $$\sum_{k=0}^m \binom{m}{k} \binom{N-M}{m-k} = \binom{N}{m}$$ Puis en déduire que : $$\sum_{k=0}^m k \frac{\binom{m}{k} \binom{N-M}{m-k}}{\binom{N}{m}} = 1$$ On pose : $$E(X) = \sum_{k=0}^m k \frac{\binom{m}{k} \binom{N-M}{m-k}}{\binom{N}{m}}$$ Montrer que : $$E(X) = \frac{nM}{N}$$ Enfin, montrer que la variance : $$V(X) = \sum_{k=0}^m k^2 \frac{\binom{m}{k} \binom{N-M}{n-k}}{\binom{N}{n}} - (E(X))^2 = \frac{nM}{N} \left(1 - \frac{M}{N}\right) \frac{\binom{N-n}{N-n}}{N-1}$$ 2. **Identité de Vandermonde :** L'identité de Vandermonde est une formule classique en combinatoire qui dit que pour des entiers $m, N, M$ : $$\sum_{k=0}^m \binom{m}{k} \binom{N-M}{m-k} = \binom{N}{m}$$ Cela correspond au fait que choisir $m$ éléments parmi $N$ peut se faire en choisissant $k$ éléments parmi $M$ et $m-k$ parmi $N-M$, puis en sommant sur tous les $k$ possibles. 3. **Démonstration de l'identité :** On considère le développement du binôme : $$(1+x)^N = (1+x)^M (1+x)^{N-M}$$ En développant, le coefficient de $x^m$ dans $(1+x)^N$ est $\binom{N}{m}$. Le coefficient de $x^m$ dans $(1+x)^M (1+x)^{N-M}$ est : $$\sum_{k=0}^m \binom{M}{k} \binom{N-M}{m-k}$$ Par égalité des coefficients, on obtient l'identité de Vandermonde. 4. **Déduction de la somme pondérée :** On veut montrer que : $$\sum_{k=0}^m k \frac{\binom{m}{k} \binom{N-M}{m-k}}{\binom{N}{m}} = 1$$ On pose : $$E(X) = \sum_{k=0}^m k \frac{\binom{m}{k} \binom{N-M}{m-k}}{\binom{N}{m}}$$ Cette somme représente l'espérance d'une variable aléatoire $X$ qui compte le nombre de succès dans un échantillon hypergéométrique. 5. **Calcul de $E(X)$ :** On utilise la relation donnée : $$k \binom{m}{k} = m \binom{m-1}{k-1}$$ Donc : $$E(X) = \sum_{k=0}^m k \frac{\binom{m}{k} \binom{N-M}{m-k}}{\binom{N}{m}} = \sum_{k=0}^m m \frac{\binom{m-1}{k-1} \binom{N-M}{m-k}}{\binom{N}{m}}$$ On fait un changement d'indice $j = k-1$ : $$E(X) = m \sum_{j=0}^{m-1} \frac{\binom{m-1}{j} \binom{N-M}{m-1-j}}{\binom{N}{m}}$$ Par l'identité de Vandermonde appliquée à $m-1$ : $$\sum_{j=0}^{m-1} \binom{m-1}{j} \binom{N-M}{m-1-j} = \binom{N-1}{m-1}$$ Donc : $$E(X) = m \frac{\binom{N-1}{m-1}}{\binom{N}{m}}$$ On simplifie : $$\binom{N}{m} = \frac{N!}{m! (N-m)!}, \quad \binom{N-1}{m-1} = \frac{(N-1)!}{(m-1)! (N-m)!}$$ Donc : $$E(X) = m \frac{\frac{(N-1)!}{(m-1)! (N-m)!}}{\frac{N!}{m! (N-m)!}} = m \frac{(N-1)! m!}{(m-1)! (N-m)! N!} (N-m)! = m \frac{(N-1)! m!}{(m-1)! N!}$$ On simplifie $m!/(m-1)! = m$ et $N! = N (N-1)!$ : $$E(X) = m \frac{(N-1)! m}{N (N-1)!} = \frac{m^2}{N}$$ Ici, en remplaçant $m$ par $n$ et $M$ par $M$ dans le contexte, on obtient : $$E(X) = \frac{n M}{N}$$ 6. **Calcul de la variance $V(X)$ :** La variance est définie par : $$V(X) = E(X^2) - (E(X))^2$$ avec : $$E(X^2) = \sum_{k=0}^m k^2 \frac{\binom{m}{k} \binom{N-M}{n-k}}{\binom{N}{n}}$$ On utilise la relation combinatoire et la formule de la variance pour l'hypergéométrique : $$V(X) = \frac{n M}{N} \left(1 - \frac{M}{N}\right) \frac{N-n}{N-1}$$ Cette formule exprime la variance d'une variable hypergéométrique, où $n$ est la taille de l'échantillon, $M$ le nombre de succès dans la population, et $N$ la taille totale de la population. **Résumé final :** - Identité de Vandermonde : $$\sum_{k=0}^m \binom{m}{k} \binom{N-M}{m-k} = \binom{N}{m}$$ - Espérance : $$E(X) = \frac{n M}{N}$$ - Variance : $$V(X) = \frac{n M}{N} \left(1 - \frac{M}{N}\right) \frac{N-n}{N-1}$$ Ces résultats sont fondamentaux en probabilités combinatoires et statistiques, notamment pour la loi hypergéométrique.