L'équipe, son capitaine et son bureau

Exercice de TD · niveau 2 · mathématiques (PTSI), chapitre 15 — Dénombrement · D. Problèmes et doubles comptages

Énoncé

Soit $n \geq 1$ , et un groupe de $n$ personnes.

a) Démontrer combinatoirement que $k = 0 \sum n k (k n) = n 2^{n - 1}$ , puis que $k (k n) = n (k - 1 n - 1)$ pour $1 \leq k \leq n$ .

b) (Comité et bureau) Démontrer combinatoirement que $(p n) (k p) = (k n) (p - k n - k)$ pour $0 \leq k \leq p \leq n$ . Que donne le cas $k = 1$ ?

c) En déduire que $p = 0 \sum n p (p - 1) (p n) = n (n - 1) 2^{n - 2}$ pour $n \geq 2$ .

d) Pour $x, y$ réels, montrer que $k = 0 \sum n k (k n) x^{k} y^{n - k} = n x (x + y)^{n - 1}$ . Que vaut $k = 0 \sum n k (k n) t^{k} (1 - t)^{n - k}$ pour $t \in [0, 1]$ ?

Corrigé

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), l'équipe étant une partie quelconque du groupe et le capitaine un de ses membres. Équipe d'abord : pour chaque taille $k$ , $(k n)$ équipes, puis $k$ capitaines ; en sommant, $\sum_{k} k (k n)$ — le terme $k = 0$ est nul, une équipe vide n'a pas de capitaine. Capitaine d'abord : $n$ choix, puis chacune des $n - 1$ autres personnes est dans l'équipe ou non : $n 2^{n - 1}$ . Le même ensemble compté deux fois : $\sum_{k = 0}^{n} k (k n) = n 2^{n - 1}$ . À taille fixée $k$ , le même double comptage donne $k (k n)$ d'un côté, et de l'autre $n$ capitaines puis $k - 1$ coéquipiers parmi $n - 1$ : $k (k n) = n (k - 1 n - 1)$ — la formule « du pion » du chapitre 2, qui reçoit ici sa démonstration combinatoire.

b) Comité et bureau. Comptons les couples (comité, bureau) où le comité compte $p$ personnes du groupe et le bureau $k$ membres du comité. Comité d'abord : $(p n)$ comités, puis $(k p)$ bureaux. Bureau d'abord : $(k n)$ bureaux, puis on complète le comité avec $p - k$ personnes prises parmi les $n - k$ qui ne sont pas au bureau : $(p - k n - k)$ . D'où $(p n) (k p) = (k n) (p - k n - k)$ . Le cas $k = 1$ est le capitaine du a) : $p (p n) = n (p - 1 n - 1)$ .

c) Le bureau de deux. Avec $k = 2$ , pour $2 \leq p \leq n$ : $(p n) \frac{p ( p - 1 )}{2} = (2 n) (p - 2 n - 2)$ . En sommant sur $p$ de $2$ à $n$ , et puisque $\sum_{p = 2}^{n} (p - 2 n - 2) = 2^{n - 2}$ : $p = 2 \sum n p (p - 1) (p n) = 2 (2 n) 2^{n - 2} = n (n - 1) 2^{n - 2},$ les termes $p = 0$ et $p = 1$ étant nuls. Contrôle pour $n = 3$ : $0 + 0 + 2 \times 3 + 6 \times 1 = 12 = 3 \times 2 \times 2$ .

d) La pondération. Par le a), pour $k \geq 1$ , $k (k n) = n (k - 1 n - 1)$ , donc, en posant $j = k - 1$ puis par la formule du binôme : $k = 1 \sum n k (k n) x^{k} y^{n - k} = n x j = 0 \sum n - 1 (j n - 1) x^{j} y^{(n - 1) - j} = n x (x + y)^{n - 1} .$ Avec $x = t$ et $y = 1 - t$ : $\sum_{k = 0}^{n} k (k n) t^{k} (1 - t)^{n - k} = n t$ . De même, le b) avec un bureau de deux donne $k (k - 1) (k n) = n (n - 1) (k - 2 n - 2)$ pour $k \geq 2$ , d'où $\sum_{k} k (k - 1) (k n) x^{k} y^{n - k} = n (n - 1) x^{2} (x + y)^{n - 2}$ , soit $n (n - 1) t^{2}$ pour $x = t$ et $y = 1 - t$ .

Ce que l'exercice installe. Changer l'ordre des choix est une démonstration. Et la pondération par $t^{k} (1 - t)^{n - k}$ annonce le chapitre 16 : $t$ y sera la probabilité d'un succès, $(k n) t^{k} (1 - t)^{n - k}$ la probabilité de $k$ succès en $n$ épreuves, et les deux sommes du d) donneront l'espérance $n t$ de la loi binomiale, puis, par $k^{2} = k (k - 1) + k$ , sa variance $n t (1 - t)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.