|

Exercices pour les élèves motivés : dénombrement (Terminale spécialité)

↩ Chapitre : Dénombrement (Terminale spécialité)

Introduction

Six exercices exigeants de dénombrement, pour les élèves qui maîtrisent déjà le cours et la fiche d’exercices corrigés du chapitre : trois exercices ★★★ et trois exercices ★★★★, dont deux de niveau première année de prépa (ECG et MPSI-PCSI). Outils utilisés : principes additif et multiplicatif, k-uplets, arrangements, permutations, combinaisons, relation de Pascal, raisonnement par récurrence et par bijection.

Mode d’emploi : cherchez chaque exercice au moins vingt minutes avant d’ouvrir les Indications, puis cherchez encore avant de lire le Corrigé. Les exercices ★★★ sont du niveau des questions les plus difficiles du bac ; les exercices ★★★★ demandent davantage d’initiative, et les deux derniers sont du niveau d’une première année de classe préparatoire, tout en restant dans le programme du chapitre.

Exercices

Exercice 1 · Les anagrammes de MISSISSIPPI ★★★★

On s’intéresse aux anagrammes du mot MISSISSIPPI (mots de 11 lettres, ayant un sens ou non, formés avec exactement ces lettres).

  1. En choisissant d’abord les places des quatre S, puis celles des quatre I, puis celles des deux P, calculer le nombre N d’anagrammes. Vérifier que N=\frac{11!}{4!\,4!\,2!}.
  2. Combien d’anagrammes contiennent le bloc IIII (les quatre I consécutifs) ?
  3. Combien d’anagrammes ne contiennent jamais deux S côte à côte ?
  4. On choisit une anagramme au hasard. Quelle est la probabilité qu’aucun S ne soit à côté d’un autre S ?
Indications

1. Une anagramme est déterminée par les ensembles de positions des lettres répétées.

2. Considérer le bloc IIII comme une seule « lettre ».

3. Écrire d’abord les 7 autres lettres, puis placer les S dans les « trous » entre ces lettres (y compris aux extrémités).

Corrigé

1. On choisit les 4 places des S parmi 11 : \binom{11}4=330 ; puis celles des I parmi les 7 restantes : \binom74=35 ; puis celles des P parmi 3 : \binom32=3 ; le M prend la dernière place. Donc N=330\times35\times3=34\,650. Et \frac{11!}{4!\,4!\,2!}=\frac{39\,916\,800}{24\times24\times2}=34\,650.

2. On range 8 objets : M, le bloc, quatre S et deux P : \binom84\binom42\times2=70\times6\times2=840 anagrammes (soit \frac{8!}{4!\,2!}).

3. Les 7 lettres M, I, I, I, I, P, P peuvent s’écrire de \binom74\binom32=35\times3=105 façons. Elles délimitent 8 trous ; les S doivent occuper 4 trous distincts : \binom84=70 choix. Total : 105\times70.

⇝ 7\,350 anagrammes sans S adjacents.

4. Les anagrammes étant équiprobables : p=\frac{7\,350}{34\,650}=\frac7{33}\approx0{,}212.

Exercice 2 · Le paradoxe des anniversaires ★★★★

On réunit n personnes (2\leqslant n\leqslant365). On suppose que les 365 jours de l’année sont équiprobables pour chaque anniversaire, indépendamment (on ignore le 29 février). On modélise la liste des anniversaires par un n-uplet de jours.

  1. Combien y a-t-il de listes possibles ? Combien de listes ont tous leurs jours distincts ?
  2. En déduire que la probabilité p_n qu’au moins deux personnes aient le même anniversaire est p_n=1-\frac{365\times364\times\cdots\times(365-n+1)}{365^n}.
  3. Montrer que 1-p_{n+1}=(1-p_n)\times\frac{365-n}{365}. En déduire que la suite (p_n) est croissante.
  4. Écrire une fonction Python qui renvoie le plus petit n tel que p_n > \frac12. Quel résultat obtient-on ? Commenter.
Indications

1. n-uplets d’un ensemble à 365 éléments ; n-uplets d’éléments distincts (arrangements).

2. Événement contraire.

4. Calculer 1-p_n de proche en proche avec la relation de la question 3.

Corrigé

1. 365^n listes ; 365\times364\times\cdots\times(365-n+1)=\frac{365!}{(365-n)!} listes de jours distincts.

2. Les listes sont équiprobables, et l’événement contraire est « tous les jours sont distincts » : d’où la formule.

3. Le produit au rang n+1 contient un facteur de plus, \frac{365-n}{365}. Comme ce facteur est dans [0\,;1], 1-p_{n+1}\leqslant1-p_n, donc p_{n+1}\geqslant p_n.

4.

def seuil() :
q, n = 1, 1 # q = 1 - p_n
while 1 - q <= 0.5 :
q = q * (365 - n) / 365
n = n + 1
return n

On obtient n=23 (p_{22}\approx0{,}476, p_{23}\approx0{,}507). Avec 50 personnes, p_{50}\approx0{,}970. C’est contre-intuitif : on compare mentalement à 365, mais le nombre de paires de personnes, \binom{23}2=253, est déjà très grand.

Exercice 3 · L’identité de Vandermonde ★★★★

Une classe compte a filles et b garçons. On veut former un comité de n élèves (n\leqslant a+b). On convient que \binom pk=0 si k > p.

  1. Combien y a-t-il de comités possibles ?
  2. Combien de comités comportent exactement k filles ? En déduire l’identité de Vandermonde : \sum\limits_{k=0}^n\binom ak\binom b{n-k}=\binom{a+b}n.
  3. En prenant a=b=n, montrer que \sum\limits_{k=0}^n\binom nk^2=\binom{2n}n. Vérifier pour n=4 à l’aide du triangle de Pascal.
  4. Combien y a-t-il de comités de 5 élèves contenant au moins 2 filles dans une classe de 12 filles et 10 garçons ?
Indications

2. Principe multiplicatif, puis principe additif selon le nombre de filles.

3. \binom n{n-k}=\binom nk.

4. Passer par le complémentaire : 0 ou 1 fille.

Corrigé

1. \binom{a+b}n comités (parties à n éléments d’un ensemble à a+b éléments).

2. Choisir k filles parmi a et n-k garçons parmi b : \binom ak\binom b{n-k} comités. Chaque comité a un nombre de filles k\in\{0,\dots,n\} bien déterminé ; en sommant sur k, on retrouve tous les comités une et une seule fois.

⇝ \displaystyle\sum_{k=0}^n\binom ak\binom b{n-k}=\binom{a+b}n.

3. Avec a=b=n et \binom n{n-k}=\binom nk : \sum\binom nk^2=\binom{2n}n. Pour n=4 : 1+16+36+16+1=70=\binom84.

4. Total \binom{22}5=26\,334 ; sans fille : \binom{10}5=252 ; une fille : 12\times\binom{10}4=12\times210=2\,520. Réponse : 26\,334-252-2\,520=23\,562.

Exercice 4 · La formule de la crosse de hockey ★★★★

Soit p\in\mathbb N.

  1. Démontrer par récurrence sur n\geqslant p, à l’aide de la relation de Pascal, que \sum\limits_{k=p}^n\binom kp=\binom{n+1}{p+1}.
  2. Redémontrer ce résultat par un dénombrement : on compte les parties à p+1 éléments de \{1,2,\dots,n+1\} selon la valeur de leur plus grand élément.
  3. Pour p=1, retrouver la somme 1+2+\cdots+n.
  4. Montrer que k^2=2\binom k2+\binom k1 pour tout entier k\geqslant1. En déduire \sum\limits_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6.
  5. Par la même méthode, calculer \sum\limits_{k=1}^nk(k+1)(k+2).
Indications

1. \binom{n+1}{p+1}+\binom{n+1}p=\binom{n+2}{p+1}.

2. Si le plus grand élément est k+1, les p autres sont choisis dans \{1,\dots,k\}.

5. k(k+1)(k+2)=6\binom{k+2}3.

Corrigé

1. Pour n=p : \binom pp=1=\binom{p+1}{p+1}. Si \sum\limits_{k=p}^n\binom kp=\binom{n+1}{p+1}, alors \sum\limits_{k=p}^{n+1}\binom kp=\binom{n+1}{p+1}+\binom{n+1}p=\binom{n+2}{p+1} par la relation de Pascal.

2. Une partie à p+1 éléments de \{1,\dots,n+1\} a un plus grand élément k+1 avec p\leqslant k\leqslant n, et ses p autres éléments forment une partie quelconque de \{1,\dots,k\} : il y en a \binom kp. En sommant sur k (principe additif), on obtient \binom{n+1}{p+1}.

3. \sum\limits_{k=1}^n\binom k1=\binom{n+1}2, soit 1+2+\cdots+n=\frac{n(n+1)}2.

4. 2\binom k2+k=k(k-1)+k=k^2. Donc \sum\limits_{k=1}^nk^2=2\binom{n+1}3+\binom{n+1}2=\frac{(n+1)n(n-1)}3+\frac{(n+1)n}2=\frac{n(n+1)\big(2(n-1)+3\big)}6 (le terme k=1 de \binom k2 est nul).

⇝ \displaystyle\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}6 (pour n=10 : 385).

5. k(k+1)(k+2)=6\binom{k+2}3, donc \sum\limits_{k=1}^nk(k+1)(k+2)=6\sum\limits_{j=3}^{n+2}\binom j3=6\binom{n+3}4=\frac{n(n+1)(n+2)(n+3)}4.

Le nom vient de la forme du dessin dans le triangle de Pascal : une diagonale (le manche) et la case juste en dessous à côté (la lame).

Exercice 5 · Formule du binôme et parité ★★★★ — niveau prépa ECG

La formule du binôme de Newton n’est pas au programme de Terminale : on la démontre ici. Soient a et b deux réels.

  1. Démontrer par récurrence sur n\in\mathbb N que (a+b)^n=\sum\limits_{k=0}^n\binom nka^kb^{n-k}.
  2. En déduire \sum\limits_{k=0}^n\binom nk et, pour n\geqslant1, \sum\limits_{k=0}^n(-1)^k\binom nk. Combien un ensemble à n\geqslant1 éléments possède-t-il de parties de cardinal pair ?
  3. Soit X une variable aléatoire suivant la loi binomiale \mathcal B(n\,;p), et q=1-p. Montrer que P(X\text{ pair})=\frac{1+(q-p)^n}2.
  4. Une pièce donne pile avec la probabilité 0{,}3. On la lance 5 fois. Calculer la probabilité d’obtenir un nombre pair de piles. Que vaut la limite de P(X\text{ pair}) quand n\to+\infty (avec 0 < p < 1) ?
Indications

1. Écrire (a+b)^{n+1}=(a+b)(a+b)^n, développer, décaler l’indice dans l’une des sommes et utiliser la relation de Pascal.

2. Prendre a=b=1, puis a=-1, b=1. Faire la demi-somme.

3. Calculer (q+p)^n+(q-p)^n avec la formule du binôme.

Corrigé

1. Pour n=0 : 1=\binom00. Supposons la formule au rang n. Alors (a+b)^{n+1}=\sum\limits_{k=0}^n\binom nka^{k+1}b^{n-k}+\sum\limits_{k=0}^n\binom nka^kb^{n+1-k}. Dans la première somme, on pose j=k+1 : \sum\limits_{j=1}^{n+1}\binom n{j-1}a^jb^{n+1-j}. En regroupant les termes en a^jb^{n+1-j} : pour 1\leqslant j\leqslant n, le coefficient est \binom n{j-1}+\binom nj=\binom{n+1}j (Pascal) ; pour j=0 et j=n+1, il vaut 1. D’où la formule au rang n+1.

2. a=b=1 : \sum\binom nk=2^n. a=-1, b=1 : \sum(-1)^k\binom nk=0^n=0 pour n\geqslant1. En faisant la demi-somme, \sum\limits_{k\text{ pair}}\binom nk=\frac{2^n+0}2 :

⇝ un ensemble à n\geqslant1 éléments a 2^{n-1} parties de cardinal pair (et autant de cardinal impair).

3. (q+p)^n=\sum\binom nkp^kq^{n-k} et (q-p)^n=\sum\binom nk(-1)^kp^kq^{n-k}. En ajoutant, les termes d’indice impair s’annulent et ceux d’indice pair doublent : 1+(q-p)^n=2\sum\limits_{k\text{ pair}}\binom nkp^kq^{n-k}=2P(X\text{ pair}).

4. P=\frac{1+0{,}4^5}2=\frac{1+0{,}01024}2=0{,}50512. Si 0 < p < 1, alors -1 < q-p < 1, donc (q-p)^n\to0 et P(X\text{ pair})\to\frac12.

En ECG, la formule du binôme est un outil constant (calculs de probabilités, puissances de matrices) ; l’astuce de la demi-somme sert aussi à séparer termes pairs et impairs d’une somme.

Exercice 6 · Les nombres de Catalan et le principe de réflexion ★★★★ — niveau prépa MPSI-PCSI

On considère les chemins du quadrillage qui vont du point (0\,;0) au point (n\,;n) par des pas D (vers la droite, (1\,;0)) ou H (vers le haut, (0\,;1)). Un chemin est dit bon s’il ne passe jamais strictement au-dessus de la diagonale y=x. On note C_n le nombre de bons chemins.

  1. Combien y a-t-il de chemins (bons ou non) de (0\,;0) à (n\,;n) ? Dessiner les bons chemins pour n=3 et vérifier que C_3=5.
  2. Montrer qu’un chemin est mauvais si et seulement s’il touche la droite \Delta d’équation y=x+1.
  3. À un mauvais chemin, on associe le chemin obtenu en remplaçant, après le premier point de contact avec \Delta, chaque pas D par H et chaque pas H par D (symétrie par rapport à \Delta). Montrer qu’on obtient un chemin de (0\,;0) à (n-1\,;n+1), et que cette transformation est une bijection entre les mauvais chemins et tous les chemins de (0\,;0) à (n-1\,;n+1).
  4. En déduire que C_n=\binom{2n}n-\binom{2n}{n-1}=\frac1{n+1}\binom{2n}n, et calculer C_1,\dots,C_6.
  5. On écrit des mots de 2n caractères formés de n parenthèses ouvrantes « ( » et n fermantes « ) ». Combien sont « bien parenthésés » (chaque fermante correspond à une ouvrante qui la précède) ?
Indications

1. Un chemin est un mot de 2n lettres comportant n lettres H.

2. Les coordonnées sont entières : être strictement au-dessus de y=x signifie y\geqslant x+1.

3. Après le premier contact en (a\,;a+1), il reste n-a pas D et n-a-1 pas H. Pour la réciproque, tout chemin vers (n-1\,;n+1) touche \Delta : on lui applique la même transformation.

5. Associer « ( » à D et « ) » à H.

Corrigé

1. Il faut placer n pas H parmi 2n : \binom{2n}n chemins. Pour n=3, les bons chemins sont DDDHHH, DDHDHH, DDHHDH, DHDDHH, DHDHDH : C_3=5.

2. Si le chemin passe par un point (x\,;y) avec y > x, alors y\geqslant x+1. Juste avant le premier tel point, on était sur la diagonale (y=x) et on a fait un pas H : on arrive en (x\,;x+1)\in\Delta. Réciproquement, un point de \Delta est au-dessus de la diagonale.

3. Si le premier contact a lieu en (a\,;a+1), la fin du chemin contient n-a pas D et n-a-1 pas H ; après échange, elle contient n-a pas H et n-a-1 pas D, et l’on arrive en (a+n-a-1\,;a+1+n-a)=(n-1\,;n+1). Réciproquement, un chemin vers (n-1\,;n+1) finit au-dessus de \Delta en partant d’en dessous (0 < 1) : il touche \Delta, et la même transformation (appliquée après son premier contact) le ramène à un mauvais chemin vers (n\,;n). Les deux transformations sont réciproques l’une de l’autre, car le premier point de contact n’est pas modifié : c’est une bijection.

4. Il y a \binom{2n}{n-1} chemins vers (n-1\,;n+1) (placer n-1 pas D parmi 2n). Donc C_n=\binom{2n}n-\binom{2n}{n-1}. Or \binom{2n}{n-1}=\frac{(2n)!}{(n-1)!\,(n+1)!}=\frac n{n+1}\binom{2n}n, d’où C_n=\frac1{n+1}\binom{2n}n.

⇝ C_1=1, C_2=2, C_3=5, C_4=14, C_5=42, C_6=132.

5. Avec « ( » \leftrightarrow D et « ) » \leftrightarrow H, un mot est bien parenthésé si et seulement si, à chaque instant, on a écrit au moins autant d’ouvrantes que de fermantes, c’est-à-dire si le chemin reste sous la diagonale (au sens large). Il y en a donc C_n.

Les nombres de Catalan apparaissent dans des dizaines de problèmes de dénombrement (triangulations d’un polygone, arbres binaires…). Le principe de réflexion, dû à D. André (1887), est une idée typique des oraux de prépa.


Pour aller plus loin

Besoin d’aide sur ce chapitre, ou envie de viser plus haut ?

Un blocage sur une notion, un contrôle à préparer — ou l’ambition d’une mention au Bac et d’une bonne prépa : Pr. Elakili, agrégé de mathématiques depuis 1991, propose des cours particuliers aux lycéens (Première, Terminale, Maths expertes), en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

🎯 Objectif : réussir son Bac, viser la mention et arriver dans le supérieur avec une formation solide.

Publications similaires