L'équipe et son capitaine

La stratégie. Changer l'ordre des choix : l'équipe puis son capitaine, ou le capitaine puis le reste de l'équipe. Ce que la dérivation du binôme dit par le calcul, le comptage le dit sans calcul.

a) Équipe puis capitaine, ou l'inverse. Comptons les couples (équipe, capitaine), où l'équipe est une partie quelconque d'un ensemble de $n$ personnes et le capitaine un membre de l'équipe. Équipe d'abord : pour chaque taille $k$, il y a $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ équipes, puis $k$ choix de capitaine ; en sommant sur $k$, $\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ couples — le terme $k=0$ est nul, une équipe vide n'a pas de capitaine. Capitaine d'abord : $n$ choix pour le capitaine, puis chacune des $n-1$ autres personnes est dans l'équipe ou non, soit $2^{n-1}$ équipes contenant ce capitaine : $n{2}^{n-1}$ couples. Le même ensemble compté deux fois : $\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$.

b) À taille fixée. Comptons les couples (équipe, capitaine) où l'équipe a exactement $k$ membres. Équipe d'abord : $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ équipes, $k$ capitaines : $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. Capitaine d'abord : $n$ choix, puis les $k-1$ autres membres parmi les $n-1$ autres personnes : $n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. D'où $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ — ce que le calcul confirme : $k\cdot \frac{n!}{k!(n-k)!}=n\cdot \frac{(n-1)!}{(k-1)!(n-k)!}$. En sommant sur $k$ de $1$ à $n$, on retrouve a) : $\sum _{k=1}^{n}n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=n\sum _{j=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{j}\right)=n{2}^{n-1}$.

c) Capitaine et vice-capitaine. Comptons les triplets (équipe, capitaine, vice-capitaine), le capitaine et le vice-capitaine étant deux membres distincts de l'équipe. Équipe d'abord : $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ équipes de taille $k$, puis $k$ choix de capitaine et $k-1$ de vice-capitaine : $\sum _{k=0}^{n}k(k-1)\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. Les deux dirigeants d'abord : $n(n-1)$ couples ordonnés, puis chacune des $n-2$ autres personnes est dans l'équipe ou non, ce qui suppose $n\ge 2$ : $n(n-1)2^{n-2}$. Donc $$\sum _{k=0}^{n}k(k-1)\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n(n-1)2^{n-2}(n\ge 2),$$ et la somme est nulle pour $n=1$, ce que la formule donne aussi.

d) Par la dérivation. La formule du binôme donne l'égalité polynomiale $(1+x{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k$. Dérivons (chapitre 10) : $n(1+x{)}^{n-1}=\sum _{k=1}^{n}k(\genfrac{}{}{0ex}{}{n}{k})x^{k-1}$. En $x=1$ : $n{2}^{n-1}=\sum _{k=1}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, c'est a). En identifiant le coefficient de $x^{k-1}$ des deux membres, le binôme donnant $n(1+x{)}^{n-1}=n\sum _{j=0}^{n-1}(\genfrac{}{}{0ex}{}{n-1}{j})x^j$ : $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, c'est b). Dérivons une seconde fois, pour $n\ge 2$ : $n(n-1)(1+x{)}^{n-2}=\sum _{k=2}^{n}k(k-1)(\genfrac{}{}{0ex}{}{n}{k})x^{k-2}$, et en $x=1$ : $n(n-1)2^{n-2}$, c'est c).

La somme des $k^2$. Comme $k^2=k(k-1)+k$, par linéarité, $$\sum _{k=0}^n{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n(n-1)2^{n-2}+n{2}^{n-1}=n{2}^{n-2}((n-1)+2)=n(n+1)2^{n-2}.$$ Contrôle pour $n=3$ : $0+3+12+9=24=3\cdot 4\cdot 2$.

Ce que l'exercice installe. Changer l'ordre des choix est une démonstration ; et la décomposition $k^2=k(k-1)+k$, écrire un polynôme en $k$ dans la base des factorielles descendantes, est le calcul qui donnera au chapitre 19 l'espérance $np$ et la variance $np(1-p)$ de la loi binomiale : $\sum _{k}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$ se calcule exactement comme ici, avec $p^k$ en plus.