↩ 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,
-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
lettres, ayant un sens ou non, formés avec exactement ces lettres).
- En choisissant d’abord les places des quatre S, puis celles des quatre I, puis celles des deux P, calculer le nombre
d’anagrammes. Vérifier que
. - Combien d’anagrammes contiennent le bloc IIII (les quatre I consécutifs) ?
- Combien d’anagrammes ne contiennent jamais deux S côte à côte ?
- 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
autres lettres, puis placer les S dans les « trous » entre ces lettres (y compris aux extrémités).
Corrigé
1. On choisit les
places des S parmi
:
; puis celles des I parmi les
restantes :
; puis celles des P parmi
:
; le M prend la dernière place. Donc
. Et
.
2. On range
objets : M, le bloc, quatre S et deux P :
anagrammes (soit
).
3. Les
lettres M, I, I, I, I, P, P peuvent s’écrire de
façons. Elles délimitent
trous ; les S doivent occuper
trous distincts :
choix. Total :
.
⇝
anagrammes sans S adjacents.
4. Les anagrammes étant équiprobables :
.
Exercice 2 · Le paradoxe des anniversaires ★★★★
On réunit
personnes (
). On suppose que les
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
-uplet de jours.
- Combien y a-t-il de listes possibles ? Combien de listes ont tous leurs jours distincts ?
- En déduire que la probabilité
qu’au moins deux personnes aient le même anniversaire est
. - Montrer que
. En déduire que la suite
est croissante. - Écrire une fonction Python qui renvoie le plus petit
tel que
. Quel résultat obtient-on ? Commenter.
Indications
1.
-uplets d’un ensemble à
éléments ;
-uplets d’éléments distincts (arrangements).
2. Événement contraire.
4. Calculer
de proche en proche avec la relation de la question 3.
Corrigé
1.
listes ;
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
contient un facteur de plus,
. Comme ce facteur est dans
,
, donc
.
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
(
,
). Avec
personnes,
. C’est contre-intuitif : on compare mentalement à
, mais le nombre de paires de personnes,
, est déjà très grand.
Exercice 3 · L’identité de Vandermonde ★★★★
Une classe compte
filles et
garçons. On veut former un comité de
élèves (
). On convient que
si
.
- Combien y a-t-il de comités possibles ?
- Combien de comités comportent exactement
filles ? En déduire l’identité de Vandermonde :
. - En prenant
, montrer que
. Vérifier pour
à l’aide du triangle de Pascal. - Combien y a-t-il de comités de
élèves contenant au moins
filles dans une classe de
filles et
garçons ?
Indications
2. Principe multiplicatif, puis principe additif selon le nombre de filles.
3.
.
4. Passer par le complémentaire :
ou
fille.
Corrigé
1.
comités (parties à
éléments d’un ensemble à
éléments).
2. Choisir
filles parmi
et
garçons parmi
:
comités. Chaque comité a un nombre de filles
bien déterminé ; en sommant sur
, on retrouve tous les comités une et une seule fois.
⇝
.
3. Avec
et
:
. Pour
:
.
4. Total
; sans fille :
; une fille :
. Réponse :
.
Exercice 4 · La formule de la crosse de hockey ★★★★
Soit
.
- Démontrer par récurrence sur
, à l’aide de la relation de Pascal, que
. - Redémontrer ce résultat par un dénombrement : on compte les parties à
éléments de
selon la valeur de leur plus grand élément. - Pour
, retrouver la somme
. - Montrer que
pour tout entier
. En déduire
. - Par la même méthode, calculer
.
Indications
1.
.
2. Si le plus grand élément est
, les
autres sont choisis dans
.
5.
.
Corrigé
1. Pour
:
. Si
, alors
par la relation de Pascal.
2. Une partie à
éléments de
a un plus grand élément
avec
, et ses
autres éléments forment une partie quelconque de
: il y en a
. En sommant sur
(principe additif), on obtient
.
3.
, soit
.
4.
. Donc
(le terme
de
est nul).
⇝
(pour
:
).
5.
, donc
.
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
et
deux réels.
- Démontrer par récurrence sur
que
. - En déduire
et, pour
,
. Combien un ensemble à
éléments possède-t-il de parties de cardinal pair ? - Soit
une variable aléatoire suivant la loi binomiale
, et
. Montrer que
. - Une pièce donne pile avec la probabilité
. On la lance
fois. Calculer la probabilité d’obtenir un nombre pair de piles. Que vaut la limite de
quand
(avec
) ?
Indications
1. Écrire
, développer, décaler l’indice dans l’une des sommes et utiliser la relation de Pascal.
2. Prendre
, puis
,
. Faire la demi-somme.
3. Calculer
avec la formule du binôme.
Corrigé
1. Pour
:
. Supposons la formule au rang
. Alors
. Dans la première somme, on pose
:
. En regroupant les termes en
: pour
, le coefficient est
(Pascal) ; pour
et
, il vaut
. D’où la formule au rang
.
2.
:
.
,
:
pour
. En faisant la demi-somme,
:
⇝ un ensemble à
éléments a
parties de cardinal pair (et autant de cardinal impair).
3.
et
. En ajoutant, les termes d’indice impair s’annulent et ceux d’indice pair doublent :
.
4.
. Si
, alors
, donc
et
.
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
au point
par des pas
(vers la droite,
) ou
(vers le haut,
). Un chemin est dit bon s’il ne passe jamais strictement au-dessus de la diagonale
. On note
le nombre de bons chemins.
- Combien y a-t-il de chemins (bons ou non) de
à
? Dessiner les bons chemins pour
et vérifier que
. - Montrer qu’un chemin est mauvais si et seulement s’il touche la droite
d’équation
. - À un mauvais chemin, on associe le chemin obtenu en remplaçant, après le premier point de contact avec
, chaque pas
par
et chaque pas
par
(symétrie par rapport à
). Montrer qu’on obtient un chemin de
à
, et que cette transformation est une bijection entre les mauvais chemins et tous les chemins de
à
. - En déduire que
, et calculer
. - On écrit des mots de
caractères formés de
parenthèses ouvrantes « ( » et
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
lettres comportant
lettres
.
2. Les coordonnées sont entières : être strictement au-dessus de
signifie
.
3. Après le premier contact en
, il reste
pas
et
pas
. Pour la réciproque, tout chemin vers
touche
: on lui applique la même transformation.
5. Associer « ( » à
et « ) » à
.
Corrigé
1. Il faut placer
pas
parmi
:
chemins. Pour
, les bons chemins sont DDDHHH, DDHDHH, DDHHDH, DHDDHH, DHDHDH :
.
2. Si le chemin passe par un point
avec
, alors
. Juste avant le premier tel point, on était sur la diagonale (
) et on a fait un pas
: on arrive en
. Réciproquement, un point de
est au-dessus de la diagonale.
3. Si le premier contact a lieu en
, la fin du chemin contient
pas
et
pas
; après échange, elle contient
pas
et
pas
, et l’on arrive en
. Réciproquement, un chemin vers
finit au-dessus de
en partant d’en dessous (
) : il touche
, et la même transformation (appliquée après son premier contact) le ramène à un mauvais chemin vers
. 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
chemins vers
(placer
pas
parmi
). Donc
. Or
, d’où
.
⇝
,
,
,
,
,
.
5. Avec « ( »
et « ) »
, 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
.
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.
