20 Exercices de Dénombrement Corrigés — Terminale et Prépa

Raisonnement : chaque roulette offre 10 choix, et les choix sont indépendants les uns des autres. On peut répéter un chiffre. C’est un p-uplet.

Calcul : \(10 \times 10 \times 10 \times 10 = 10^4 = 10\,000\) codes.

Raisonnement : on place chaque livre dans un emplacement. Le premier livre a 6 emplacements possibles, le deuxième 5, etc. L’ordre compte et on utilise tous les livres : c’est une permutation.

Calcul : \(6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\) rangements.

Raisonnement : l’ordre de sélection n’a pas d’importance (l’équipe {Alice, Bob, Clara} est la même que {Clara, Alice, Bob}). C’est une combinaison.

Calcul : \({10 \choose 3} = \displaystyle\frac{10!}{3!\times 7!} = \displaystyle\frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \displaystyle\frac{720}{6} = 120\) équipes.

Raisonnement : cette fois, l’ordre compte (être 1^er n’est pas la même chose qu’être 3^e). On choisit 3 athlètes parmi 8 avec ordre : c’est un arrangement.

Calcul : \(A_8^3 = \displaystyle\frac{8!}{(8-3)!} = 8 \times 7 \times 6 = 336\) podiums.

Raisonnement : chaque position est indépendante et les répétitions sont possibles (on peut avoir deux fois la même lettre). On applique le principe multiplicatif à 7 positions.

Calcul : \(26 \times 26 \times 10 \times 10 \times 10 \times 26 \times 26 = 26^4 \times 10^3\)

Soit \(456\,976 \times 1\,000 = 456\,976\,000\) plaques.

Technique : pour calculer \({n \choose k}\), prends les \(k\) facteurs consécutifs descendant depuis \(n\), puis divise par \(k!\).

(a) \({8 \choose 3} = \displaystyle\frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \displaystyle\frac{336}{6} = 56\)

(b) \({12 \choose 4} = \displaystyle\frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = \displaystyle\frac{11\,880}{24} = 495\)

(c) \({7 \choose 7} = 1\) (on prend tous les éléments : il n’y a qu’une seule façon).

Raisonnement : un tirage simultané signifie sans ordre et sans remise. C’est une combinaison.

Calcul : \({9 \choose 4} = \displaystyle\frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = \displaystyle\frac{3\,024}{24} = 126\) tirages.

Raisonnement : compter directement « au moins un chiffre » obligerait à examiner les cas 1 chiffre, 2 chiffres, 3 chiffres, 4 chiffres. C’est long et source d’erreurs. On utilise le complémentaire :

Mots de passe avec ≥ 1 chiffre = Total − Mots de passe sans aucun chiffre

Calcul :

• Total : \(36^4 = 1\,679\,616\)
• Sans aucun chiffre (uniquement des lettres) : \(26^4 = 456\,976\)

Conclusion : \(1\,679\,616 – 456\,976 = 1\,222\,640\) mots de passe.

Raisonnement : BANANE comporte 6 lettres : B (×1), A (×2), N (×2), E (×1). Si les 6 lettres étaient toutes distinctes, on aurait \(6!\) anagrammes. Mais les deux A sont interchangeables sans changer le mot, et de même pour les deux N. On divise par les factorielles des répétitions.

Calcul : \(\displaystyle\frac{6!}{2!\times 2!} = \displaystyle\frac{720}{4} = 180\) anagrammes.

Raisonnement : chaque chemin est une suite de 7 déplacements : exactement 4 « → » et 3 « ↑ ». Le chemin est entièrement déterminé par le choix des positions des 3 montées parmi les 7 étapes (le reste sera des déplacements vers la droite).

Calcul : \({7 \choose 3} = \displaystyle\frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\) chemins.

Vérification : on peut aussi choisir les 4 positions des « → » : \({7 \choose 4} = 35\). ✓

Raisonnement : on décompose le problème en deux choix indépendants :

1. Choisir les 2 as parmi les 4 du jeu.
2. Choisir les 3 cartes restantes parmi les 28 cartes qui ne sont pas des as.

Calcul : \({4 \choose 2} \times {28 \choose 3} = 6 \times 3\,276 = 19\,656\) mains.

(Détail : \({28 \choose 3} = \displaystyle\frac{28 \times 27 \times 26}{6} = 3\,276\).)

Raisonnement : un nombre pair se termine par 0, 2, 4, 6 ou 8. Mais le chiffre des milliers ne peut pas être 0 (sinon le nombre n’a que 3 chiffres). Il faut distinguer deux cas selon que le dernier chiffre est 0 ou non.

Cas 1 : dernier chiffre = 0

• 1^er chiffre : 9 choix (1 à 9)
• 2^e chiffre : 8 choix (0 à 9 sauf le 1^er et le 0 déjà pris)
• 3^e chiffre : 7 choix

Sous-total : \(9 \times 8 \times 7 = 504\)

Cas 2 : dernier chiffre ∈ {2, 4, 6, 8}

• Dernier chiffre : 4 choix
• 1^er chiffre : 8 choix (1 à 9, sauf le dernier — le 0 est interdit en tête)
• 2^e chiffre : 8 choix (0 à 9, sauf le 1^er et le dernier)
• 3^e chiffre : 7 choix

Sous-total : \(4 \times 8 \times 8 \times 7 = 1\,792\)

Total : \(504 + 1\,792 = 2\,296\) nombres.

Raisonnement : « au moins 2 femmes » est plus facile à compter par le complémentaire.

Au moins 2 femmes = Total − (0 femme) − (exactement 1 femme)

Calcul :

• Total : \({14 \choose 5} = 2\,002\)
• 0 femme (5 hommes) : \({8 \choose 5} = 56\)
• 1 femme et 4 hommes : \({6 \choose 1} \times {8 \choose 4} = 6 \times 70 = 420\)

Conclusion : \(2\,002 – 56 – 420 = 1\,526\) comités.

(a) Chaque nombre est la somme des deux nombres situés juste au-dessus :

n = 0 : 1
n = 1 : 1 — 1
n = 2 : 1 — 2 — 1
n = 3 : 1 — 3 — 3 — 1
n = 4 : 1 — 4 — 6 — 4 — 1
n = 5 : 1 — 5 — 10 — 10 — 5 — 1
n = 6 : 1 — 6 — 15 — 20 — 15 — 6 — 1

(b) Sur la ligne \(n = 6\), on lit \({6 \choose 2} = 15\) et \({6 \choose 4} = 15\).

(c) On constate que \({6 \choose 2} = {6 \choose 4}\). C’est la propriété de symétrie : \({n \choose k} = {n \choose n-k}\). Choisir 2 éléments parmi 6, c’est exactement la même chose que choisir les 4 éléments qu’on ne prend pas.

(a) Chaque dé a 6 faces : \(6^3 = 216\) résultats.

(b) Triplets de la forme \((a, a, a)\) : il y a 6 valeurs possibles pour \(a\). Soit 6 résultats.

(c) On procède en 3 étapes :

1. Choisir la valeur qui apparaît 2 fois : 6 choix.
2. Choisir les 2 positions (parmi 3) où cette valeur apparaît : \({3 \choose 2} = 3\).
3. Choisir la valeur du 3^e dé (différente de la première) : 5 choix.

Total : \(6 \times 3 \times 5 = 90\) résultats.

(d) Les trois cas (3 identiques, exactement 2 identiques, toutes différentes) forment une partition de l’univers :

\(216 – 6 – 90 = 120\) résultats avec 3 faces différentes.

Vérification : \(6 \times 5 \times 4 = 120\). ✓

Première égalité. La formule du binôme de Newton donne :

\((a+b)^n = \displaystyle\sum_{k=0}^{n} {n \choose k}\, a^k \, b^{n-k}\)

Avec \(a = 1\) et \(b = 1\) :

\((1+1)^n = \displaystyle\sum_{k=0}^{n} {n \choose k} \times 1^k \times 1^{n-k} = \displaystyle\sum_{k=0}^{n} {n \choose k}\)

D’où \(\displaystyle\sum_{k=0}^{n} {n \choose k} = 2^n\). ∎

Seconde égalité. Avec \(a = 1\) et \(b = -1\) :

\((1 + (-1))^n = \displaystyle\sum_{k=0}^{n} {n \choose k}\, (-1)^k\)

Pour \(n \geq 1\), \(0^n = 0\), d’où \(\displaystyle\sum_{k=0}^{n} (-1)^k {n \choose k} = 0\). ∎

Interprétation : la première égalité signifie que le nombre total de sous-ensembles d’un ensemble à \(n\) éléments est \(2^n\). La seconde signifie qu’il y a autant de sous-ensembles de cardinal pair que de cardinal impair.

Raisonnement : analysons la situation élément par élément. Pour chaque \(x \in E\), trois cas sont possibles :

1. \(x \notin B\) (et donc \(x \notin A\), car \(A \subset B\))
2. \(x \in B\) mais \(x \notin A\)
3. \(x \in A\) (et donc \(x \in B\), car \(A \subset B\))

Chaque élément a exactement 3 choix, et ces choix sont indépendants les uns des autres.

Conclusion : il y a \(3^n\) couples \((A, B)\) avec \(A \subset B\).

Vérification pour \(n = 2\) : \(E = \{1, 2\}\). Les couples sont \((\emptyset, \emptyset)\), \((\emptyset, \{1\})\), \((\emptyset, \{2\})\), \((\emptyset, \{1,2\})\), \((\{1\}, \{1\})\), \((\{1\}, \{1,2\})\), \((\{2\}, \{2\})\), \((\{2\}, \{1,2\})\), \((\{1,2\}, \{1,2\})\). Soit 9 = \(3^2\). ✓

Raisonnement : notons \(\mathcal{A}\) l’événement « au moins un as » et \(\mathcal{R}\) « au moins un roi ». On cherche \(|\mathcal{A} \cap \mathcal{R}|\). Le principe d’inclusion-exclusion donne :

\(|\mathcal{A} \cap \mathcal{R}| = |\Omega| – |\overline{\mathcal{A}} \cup \overline{\mathcal{R}}| = |\Omega| – |\overline{\mathcal{A}}| – |\overline{\mathcal{R}}| + |\overline{\mathcal{A}} \cap \overline{\mathcal{R}}|\)

Calcul :

• \(|\Omega| = {32 \choose 5} = 201\,376\)
• \(|\overline{\mathcal{A}}|\) (aucun as) : on choisit 5 cartes parmi 28 → \({28 \choose 5} = 98\,280\)
• \(|\overline{\mathcal{R}}|\) (aucun roi) : de même → \({28 \choose 5} = 98\,280\)
• \(|\overline{\mathcal{A}} \cap \overline{\mathcal{R}}|\) (ni as ni roi) : on choisit 5 cartes parmi 24 → \({24 \choose 5} = 42\,504\)

Conclusion : \(201\,376 – 98\,280 – 98\,280 + 42\,504 = 47\,320\) mains.

Méthode 1 — Inclusion-exclusion.

On note \(S(4,3)\) le nombre de surjections. La formule d’inclusion-exclusion donne :

\(S(4,3) = \displaystyle\sum_{k=0}^{3} (-1)^k {3 \choose k} (3-k)^4\)

Calcul :

Méthode 2 — Dénombrement direct.

Pour qu’une application de \(E\) (4 éléments) dans \(F\) (3 éléments) soit surjective, exactement un élément de \(F\) doit avoir 2 antécédents, et les deux autres en ont 1 chacun.

1. Choisir quel élément de \(F\) reçoit 2 antécédents : \({3 \choose 1} = 3\).
2. Choisir les 2 éléments de \(E\) qui lui sont envoyés : \({4 \choose 2} = 6\).
3. Affecter les 2 éléments restants de \(E\) aux 2 éléments restants de \(F\) : \(2! = 2\).

Total : \(3 \times 6 \times 2 = 36\) surjections. ✓

Ce que le correcteur attend : les deux méthodes sont acceptées en concours, mais la méthode 1 (inclusion-exclusion) est plus générale et se transpose à tout couple \((|E|, |F|)\). La méthode 2 (dénombrement direct) est plus élégante ici mais nécessite d’identifier la partition \((2, 1, 1)\), ce qui est spécifique au cas \(|E| = 4, |F| = 3\).

Démonstration combinatoire.

Considérons un groupe de \(m + n\) personnes, réparti en deux sous-groupes : le groupe \(G_1\) de \(m\) personnes et le groupe \(G_2\) de \(n\) personnes.

On veut choisir \(p\) personnes parmi les \(m + n\). Le membre de gauche, \({m+n \choose p}\), compte directement ce nombre.

Comptons autrement : si l’on choisit exactement \(k\) personnes dans \(G_1\), on en choisit \(p – k\) dans \(G_2\). Pour \(k\) fixé, cela donne \({m \choose k} \times {n \choose p-k}\) choix.

En sommant sur toutes les valeurs possibles de \(k\) (de 0 à \(p\)) :

\({m+n \choose p} = \displaystyle\sum_{k=0}^{p} {m \choose k}\,{n \choose p-k}\) ∎

Application : avec \(m = 6\), \(n = 8\), \(p = 4\) :

Ce que le correcteur attend : en concours, la preuve combinatoire est la plus appréciée car elle montre une vraie compréhension. Une preuve algébrique (via les séries génératrices ou le produit de Cauchy) est également acceptée mais plus lourde.