Dénombrement : corrigé des exercices de maths sup.

Corrigé de l’exercice 1 : Codes à quatre chiffres

1. Un code est une \(4\)-liste d’éléments de \(\{0, \ldots, 9\}\), ensemble à \(10\) éléments. L’ordre compte et les répétitions sont permises. Il y a donc \(10^4 = 10\,000\) codes.
2. On cherche cette fois les \(4\)-listes d’éléments distincts. Le premier chiffre se choisit parmi \(10\), le deuxième parmi les \(9\) restants, et ainsi de suite. Il y a \(10 \times 9 \times 8 \times 7 = 5\,040\) codes à chiffres distincts.
3. L’événement « au moins deux chiffres égaux » est le complémentaire de « chiffres deux à deux distincts ». Par conséquent, il y a \(10\,000 – 5\,040 = 4\,960\) codes comportant au moins deux chiffres égaux.
4. Un code strictement croissant a des chiffres distincts. De plus, il est entièrement déterminé par l’ensemble de ses quatre chiffres : il suffit de ranger ceux-ci dans l’ordre croissant. Ainsi, l’application « ensemble des chiffres » est une bijection des codes strictement croissants sur les parties à \(4\) éléments de \(\{0, \ldots, 9\}\). Il y en a \(\binom\,{10}{4} = 210\).
5. On construit un tel code en deux étapes. D’abord, on choisit les deux positions du \(7\) : \(\binom\,{4}{2} = 6\) choix. Ensuite, on remplit les deux autres positions avec des chiffres différents de \(7\) : \(9^2 = 81\) choix. Chaque code est obtenu une seule fois. Il y a donc \(6 \times 81 = 486\) codes contenant exactement deux \(7\).

Point de méthode : l’ordre compte dans un code, donc on travaille avec des listes. Cependant, dès qu’une contrainte impose l’ordre (croissance), il ne reste qu’à choisir un ensemble : on passe alors aux combinaisons.

Corrigé de l’exercice 2 : Langues vivantes dans une classe

1. D’après la formule de la réunion de deux ensembles finis,
   \[\operatorname{card}(A \cup S) = \operatorname{card}(A) + \operatorname{card}(S) – \operatorname{card}(A \cap S) = 25 + 18 – 7 = 36.\]
   Ainsi, \(36\) étudiants suivent au moins une option.
2. Les étudiants sans option forment le complémentaire de \(A \cup S\) dans la classe \(E\). Donc \(\operatorname{card}(E \setminus (A \cup S)) = 40 – 36\). Exactement \(4\) étudiants ne suivent aucune option.
3. Les étudiants qui suivent exactement une option forment \((A \cup S) \setminus (A \cap S)\). Comme \(A \cap S \subset A \cup S\), on obtient \(36 – 7 = 29\). Il y a \(29\) étudiants qui suivent une seule option.
4. D’abord, \(\operatorname{card}(A \setminus S) = 25 – 7 = 18\) et \(\operatorname{card}(S \setminus A) = 18 – 7 = 11\). Un binôme est alors un couple de \((A \setminus S) \times (S \setminus A)\). En effet, les rôles des deux étudiants sont distincts. Le principe multiplicatif donne \(18 \times 11 = 198\) binômes.

Le diagramme ci-dessous récapitule l’effectif de chaque région. On vérifie que \(18 + 7 + 11 + 4 = 40\).

Corrigé de l’exercice 3 : Anagrammes du mot BANANE

1. Numérotons provisoirement les lettres répétées : \(\text{B}\,\text{A}_1\,\text{N}_1\,\text{A}_2\,\text{N}_2\,\text{E}\). Ces six lettres distinctes donnent \(6! = 720\) mots. Or chaque anagramme de \(\text{BANANE}\) provient exactement de \(2! \times 2! = 4\) de ces mots, obtenus en permutant les indices des A et des N. Le mot \(\text{BANANE}\) possède donc \(720 / 4 = 180\) anagrammes.
2. Si la première lettre est B, les cinq suivantes forment une anagramme de \(\text{ANANE}\). Le même raisonnement donne \(\frac{5!}{2!\,2!} = \frac{120}{4}\). Il y a \(30\) anagrammes commençant par B.
3. Collons les deux N en un seul bloc \(\boxed{\text{NN}}\). On doit alors ordonner cinq objets : B, A, A, E et le bloc. Deux d’entre eux sont identiques, d’où \(\frac{5!}{2!} = 60\) mots. Inversement, chaque anagramme à N voisins donne un unique tel mot. Il y a \(60\) anagrammes où les deux N sont côte à côte.
4. Par passage au complémentaire, il y a \(180 – 60 = 120\) anagrammes où les deux N ne sont pas voisins.

Corrigé de l’exercice 4 : Mains de cinq cartes

1. Une main est une partie à \(5\) éléments d’un ensemble à \(32\) éléments. Ainsi,
   \[\binom\,{32}{5} = \frac{32 \times 31 \times 30 \times 29 \times 28}{120} = 201\,376.\]
   Il existe \(201\,376\) mains.
2. On choisit d’abord \(2\) as parmi \(4\), soit \(\binom\,{4}{2} = 6\) choix. Ensuite, on choisit \(3\) cartes parmi les \(28\) qui ne sont pas des as, soit \(\binom\,{28}{3} = 3\,276\) choix. Il y a donc \(6 \times 3\,276 = 19\,656\) mains avec exactement deux as.
3. On passe au complémentaire. Une main sans cœur est une partie à \(5\) éléments des \(24\) cartes qui ne sont pas des cœurs. Or \(\binom\,{24}{5} = 42\,504\). Par conséquent, \(201\,376 – 42\,504 = 158\,872\) mains contiennent au moins un cœur.
4. On choisit la couleur (\(4\) choix), puis \(5\) hauteurs parmi \(8\) dans cette couleur (\(\binom\,{8}{5} = 56\) choix). On obtient \(4 \times 56 = 224\) mains unicolores.

Point de méthode : pour « au moins un cœur », ne choisissez jamais « un cœur, puis quatre cartes quelconques ». En effet, une main à deux cœurs serait alors comptée deux fois.

Corrigé de l’exercice 5 : Applications entre deux petits ensembles

1. On a \(\operatorname{card}(E) = 3\) et \(\operatorname{card}(F) = 4\). Le nombre d’applications de \(E\) dans \(F\) vaut donc \(4^3\). De plus, une injection correspond à une \(3\)-liste d’éléments distincts de \(F\). Il y a \(64\) applications de \(E\) dans \(F\), dont \(4 \times 3 \times 2 = 24\) injectives.
2. Si \(f : E \to F\) était surjective, on aurait \(F = f(E)\). Or \(\operatorname{card}(f(E)) \leq\, \operatorname{card}(E) = 3 < 4\). Il n’existe donc aucune surjection de \(E\) sur \(F\).
3. Il y a \(3^4 = 81\) applications de \(F\) dans \(E\). En revanche, une injection de \(F\) dans \(E\) imposerait \(4 \leq\, 3\), ce qui est faux. Il y a \(81\) applications de \(F\) dans \(E\) et aucune n’est injective.
4. Soit \(f : F \to E\). Pour \(y \in E\), notons \(n_y\) le nombre d’antécédents de \(y\). Les ensembles \(f^{-1}(\{y\})\) forment une partition de \(F\), donc \(n_1 + n_2 + n_3 = 4\). Si \(f\) est surjective, chaque \(n_y\) vaut au moins \(1\). La seule possibilité est alors qu’un \(n_y\) vaille \(2\) et les deux autres \(1\). Réciproquement, dans ce cas, chaque élément de \(E\) a un antécédent, et \(f\) est surjective.

   Construisons une telle surjection. D’abord, on choisit l’élément de \(E\) qui a deux antécédents : \(3\) choix. Ensuite, on choisit ces deux antécédents dans \(F\) : \(\binom\,{4}{2} = 6\) choix. Enfin, les deux éléments restants de \(F\) s’envoient bijectivement sur les deux éléments restants de \(E\) : \(2! = 2\) choix. Il y a donc \(3 \times 6 \times 2 = 36\) surjections de \(F\) sur \(E\).

Corrigé de l’exercice 6 : Lancers de trois dés

1. Un résultat est un élément de \([\![1, 6]\!]^3\). Il y a \(6^3 = 216\) résultats.
2. Pour trois faces distinctes, on compte les \(3\)-listes d’éléments distincts : \(6 \times 5 \times 4 = 120\). Pour exactement deux faces égales, on choisit d’abord le dé qui diffère des deux autres (\(3\) choix). Ensuite, on choisit la valeur commune (\(6\) choix), puis la valeur différente (\(5\) choix). On obtient \(90\) résultats. Enfin, il y a \(6\) résultats à trois faces égales. On vérifie que \(120 + 90 + 6 = 216\). Il y a \(120\), \(90\) et \(6\) résultats respectivement.
3. Les résultats sans six sont les éléments de \([\![1, 5]\!]^3\), au nombre de \(125\). Par passage au complémentaire, \(216 – 125 = 91\) résultats comportent au moins un six.
4. Avec \(x = r – 1\), \(y = v – 1\) et \(z = b – 1\), la condition \(r + v + b = 10\) devient \(x + y + z = 7\), avec \(x, y, z \in [\![0, 5]\!]\). D’après l’exercice 12, l’équation \(x + y + z = 7\) a \(\binom\,{9}{2} = 36\) solutions dans \(\mathbb{N}^3\). Il faut retirer celles où une coordonnée dépasse \(5\).

   Supposons \(x \geq\, 6\). En posant \(x^{\prime} = x – 6\), on obtient \(x^{\prime} + y + z = 1\), qui a \(3\) solutions. Il en va de même pour \(y\) et pour \(z\). De plus, deux coordonnées ne peuvent pas dépasser \(5\) simultanément, car leur somme serait au moins \(12 > 7\). Ces trois cas sont donc disjoints et totalisent \(9\) solutions. Ainsi, \(36 – 9 = 27\) résultats ont une somme égale à \(10\).

L’histogramme ci-dessous donne le nombre de résultats pour chaque somme. La valeur \(27\) est atteinte pour les sommes \(10\) et \(11\), qui sont les plus fréquentes.

Corrigé de l’exercice 7 : Injectivité et surjectivité en cardinal fini

1. Si \(f(n) = f(m)\), alors \(n + 1 = m + 1\), donc \(n = m\) : \(f\) est injective. Cependant, \(f(n) \geq\, 1\) pour tout \(n\), donc \(0\) n’a pas d’antécédent. Ensuite, pour tout \(m \in \mathbb{N}\), on a \(g(2m) = m\) : \(g\) est surjective. En revanche, \(g(0) = g(1) = 0\), donc \(g\) n’est pas injective. Cela ne contredit pas le cours, car \(\mathbb{N}\) est infini : le théorème exige des ensembles finis de même cardinal.
2. D’abord, \(\varphi\) va bien de \([\![0, n-1]\!]\) dans lui-même, car un reste modulo \(n\) appartient à cet ensemble. Supposons \(\varphi(x) = \varphi(y)\). Alors \(n\) divise \(a(x – y)\). Comme \(a\) est premier avec \(n\), le lemme de Gauss donne \(n \mid x – y\). Or \(|x – y| \leq\, n – 1\), donc \(x = y\). Ainsi, \(\varphi\) est injective. Comme elle va d’un ensemble fini dans lui-même, elle est bijective. Enfin, \(1 \in [\![0, n-1]\!]\) car \(n \geq\, 2\). Il existe donc \(u\) tel que \(\varphi(u) = 1\), c’est-à-dire \(au \equiv 1 \pmod n\).
3. Pour \(n = 7\) et \(a = 3\), les restes de \(3x\) modulo \(7\) donnent la table suivante.
   \[\begin{array}{c|ccccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \varphi(x) & 0 & 3 & 6 & 2 & 5 & 1 & 4 \end{array}\]
   On constate que chaque valeur est atteinte une fois. On lit \(\varphi(5) = 1\), donc \(u = 5\) convient : \(3 \times 5 = 15 = 2 \times 7 + 1\).
4. Si \(f(x) = f(y)\), alors \(x = g(f(x)) = g(f(y)) = y\). Donc \(f\) est injective. Comme \(f\) va de \(E\) fini dans \(E\), le théorème du cours montre que \(f\) est bijective. Ensuite, \(g = g \circ f \circ f^{-1} = f^{-1}\). Par conséquent, \(g\) est bijective et \(f \circ g = f \circ f^{-1} = \mathrm{id}_E\).

Corrigé de l’exercice 8 : Couples de parties d’un ensemble

1. On a \(\operatorname{card}(\mathcal{P}(E)^2) = (2^n)^2\). Il y a \(4^n\) couples de parties.
2. À un couple \((A, B)\) avec \(A \subset B\), associons \(\varphi : E \to \{0, 1, 2\}\) définie ainsi : \(\varphi(x) = 2\) si \(x \in A\), \(\varphi(x) = 1\) si \(x \in B \setminus A\), et \(\varphi(x) = 0\) si \(x \notin B\). Réciproquement, toute \(\varphi\) donne le couple \(A = \varphi^{-1}(\{2\})\) et \(B = \varphi^{-1}(\{1, 2\})\), qui vérifie bien \(A \subset B\). Ces deux constructions sont réciproques l’une de l’autre. Il y a donc autant de couples que d’applications de \(E\) dans \(\{0, 1, 2\}\), soit \(3^n\).
3. Si \(A \cap B = \varnothing\), chaque élément de \(E\) est soit dans \(A\), soit dans \(B\), soit hors des deux. Le même codage par une application à trois valeurs donne \(3^n\) couples. Si de plus \(A \cup B = E\), la troisième possibilité disparaît. Alors \(B = E \setminus A\), et le couple est déterminé par \(A\). Il y a \(3^n\) couples de parties disjointes, dont \(2^n\) vérifient aussi \(A \cup B = E\).
4. Classons les couples \((A, B)\) avec \(A \subset B\) selon le cardinal \(k\) de \(B\). Il y a \(\binom\,{n}{k}\) choix de \(B\), puis \(2^k\) choix de \(A\) parmi les parties de \(B\). Les cas \(k = 0, \ldots, n\) sont disjoints. Le principe additif et la question 2 donnent alors
   \[\sum_{k=0}^{n} \binom\,{n}{k} 2^k = 3^n.\]
   C’est l’identité demandée, obtenue par double dénombrement.

Point de méthode : on retrouve aussi ce résultat avec le binôme, car \((1 + 2)^n = 3^n\). Cependant, la preuve combinatoire explique d’où vient le \(3\).

Corrigé de l’exercice 9 : Chemins dans un quadrillage

1. Chaque pas augmente l’abscisse ou l’ordonnée de \(1\). Pour aller de \((0, 0)\) à \((5, 3)\), il faut donc exactement \(5\) pas \(D\) et \(3\) pas \(H\), soit \(8\) pas. Inversement, tout mot de \(8\) lettres ayant \(5\) lettres \(D\) et \(3\) lettres \(H\) décrit un chemin de \(O\) à \(B\). Un tel mot est déterminé par la position de ses \(3\) lettres \(H\) parmi \(8\). Il y a donc \(\binom\,{8}{3} = 56\) chemins de \(O\) à \(B\).
2. Un chemin passant par \(C\) est la concaténation d’un chemin de \(O\) à \(C\) et d’un chemin de \(C\) à \(B\). Le premier comporte \(2\) pas \(D\) et \(1\) pas \(H\) : \(\binom\,{3}{1} = 3\) choix. Le second comporte \(3\) pas \(D\) et \(2\) pas \(H\) : \(\binom\,{5}{2} = 10\) choix. Il y a donc \(3 \times 10 = 30\) chemins passant par \(C\).
3. Par passage au complémentaire, \(56 – 30 = 26\) chemins évitent le point \(C\).
4. Le raisonnement de la question 1 donne \(\binom\,{p+q}{p}\) chemins de \(O\) à \((p, q)\). Pour \(p, q \geq\, 1\), le dernier pas d’un tel chemin vient soit de \((p – 1, q)\), soit de \((p, q – 1)\). Ces deux cas sont disjoints. Donc
   \[\binom\,{p+q}{p} = \binom\,{p+q-1}{p-1} + \binom\,{p+q-1}{p}.\]
   Avec \(n = p + q\) et \(k = p\), on reconnaît la formule de Pascal pour \(1 \leq\, k \leq\, n – 1\). Le cas \(k = n\) est immédiat, car les deux membres valent \(1\).

La figure ci-dessous montre deux chemins : l’un passe par \(C\), l’autre l’évite.

Corrigé de l’exercice 10 : Diagonales et triangles d’un polygone

1. Un segment joignant deux sommets est une partie à \(2\) éléments de l’ensemble des sommets. Il y en a \(\binom\,{n}{2} = \frac{n(n-1)}{2}\). Parmi eux, \(n\) sont des côtés. Le nombre de diagonales vaut donc \(\frac{n(n-1)}{2} – n = \frac{n(n-3)}{2}\), soit \(20\) pour l’octogone.
2. Un triangle est déterminé par l’ensemble de ses trois sommets. Il y a \(\binom\,{n}{3}\) triangles, soit \(56\) pour \(n = 8\).
3. Numérotons les sommets \(1, \ldots, n\) dans l’ordre, modulo \(n\). Comme \(n \geq\, 4\), un triangle ne peut pas avoir trois côtés du polygone. Un triangle a deux côtés du polygone si et seulement si ses sommets sont trois sommets consécutifs \(\{i, i+1, i+2\}\). En effet, le troisième segment \([i, i+2]\) est alors une diagonale. Il y a donc \(n\) triangles ayant exactement deux côtés du polygone.

   Pour exactement un côté, on choisit d’abord ce côté \(\{i, i+1\}\) : \(n\) choix. Ensuite, le troisième sommet ne doit être ni \(i\), ni \(i + 1\), ni voisin de l’un d’eux. On exclut ainsi les quatre sommets distincts \(i – 1, i, i + 1, i + 2\). Il reste \(n – 4\) choix. Chaque triangle obtenu a un seul côté du polygone, donc il n’est compté qu’une fois. Il y a \(n(n-4)\) triangles ayant exactement un côté du polygone.

4. Par passage au complémentaire, le nombre cherché vaut
   \[\binom\,{n}{3} – n – n(n-4) = \frac{n\big[(n-1)(n-2) – 6 – 6(n-4)\big]}{6} = \frac{n(n^2 – 9n + 20)}{6}.\]
   Or \(n^2 – 9n + 20 = (n – 4)(n – 5)\). On obtient \(\frac{n(n-4)(n-5)}{6}\), soit \(\frac{8 \times 4 \times 3}{6} = 16\) pour \(n = 8\). On vérifie : \(56 – 8 – 32 = 16\).

Corrigé de l’exercice 11 : Mois de naissance

1. Les listes de mois distincts sont les \(5\)-listes d’éléments distincts d’un ensemble à \(12\) éléments. Il y en a \(12 \times 11 \times 10 \times 9 \times 8 = 95\,040\).
2. Il y a \(12^5 = 248\,832\) listes en tout. La probabilité que les mois soient distincts vaut donc \(\frac{95\,040}{248\,832}\). En simplifiant par \(1\,728 = 12^3\), on obtient \(\frac{55}{144}\). L’événement « au moins deux personnes nées le même mois » est l’événement contraire. Sa probabilité vaut \(1 – \frac{55}{144} = \frac{89}{144} \approx 0{,}618\).
3. Pour \(k \leq\, 12\), le nombre de \(k\)-listes d’éléments distincts vaut \(\frac{12!}{(12-k)!}\). Ainsi,
   \[q_k = \frac{12!}{(12-k)!\,12^k}.\]
   Pour \(k = 13\), aucune liste de \(13\) mois distincts n’existe, d’après le principe des tiroirs. Donc \(q_{13} = 0\) : parmi \(13\) personnes, deux sont forcément nées le même mois.
4. On a \(q_{k+1} = q_k \times \frac{12 – k}{12}\). De proche en proche, on trouve \(q_2 = \frac{11}{12} \approx 0{,}917\), puis \(q_3 = \frac{55}{72} \approx 0{,}764\). Ensuite, \(q_4 = \frac{55}{96} \approx 0{,}573\) et \(q_5 = \frac{55}{144} \approx 0{,}382\). La probabilité d’une coïncidence vaut donc environ \(0{,}427\) pour \(k = 4\), et \(0{,}618\) pour \(k = 5\). De plus, la suite \((q_k)\) est décroissante. Le plus petit \(k\) cherché est \(k = 5\).

La courbe ci-dessous représente \(1 – q_k\) pour \(k\) de \(1\) à \(13\). Elle franchit le seuil \(\frac{1}{2}\) entre \(k = 4\) et \(k = 5\).

Corrigé de l’exercice 12 : Solutions entières d’une équation

1. Le mot associé à \((x_1, \ldots, x_p)\) contient \(x_1 + \cdots + x_p = n\) étoiles et \(p – 1\) barres. Il a donc \(n + p – 1\) caractères. Réciproquement, soit un mot de \(n + p – 1\) caractères comportant \(p – 1\) barres, donc \(n\) étoiles. Les barres découpent les étoiles en \(p\) groupes, éventuellement vides. On note \(x_i\) le nombre d’étoiles du \(i\)-ème groupe. On obtient ainsi un \(p\)-uplet de somme \(n\). Ces deux constructions sont réciproques, d’où la bijection annoncée.
2. Un mot de \(n + p – 1\) caractères est déterminé par la position de ses \(p – 1\) barres. Le nombre de solutions dans \(\mathbb{N}^p\) vaut donc \(\binom\,{n+p-1}{p-1}\).
3. Avec \(n = 10\) et \(p = 3\), on obtient \(\binom\,{12}{2} = 66\). Dans \((\mathbb{N}^*)^3\), on pose \(x = x^{\prime} + 1\), \(y = y^{\prime} + 1\) et \(z = z^{\prime} + 1\). L’équation devient \(x^{\prime} + y^{\prime} + z^{\prime} = 7\) dans \(\mathbb{N}^3\). Ce changement de variables est bijectif. Il y a \(66\) solutions dans \(\mathbb{N}^3\) et \(\binom\,{9}{2} = 36\) dans \((\mathbb{N}^*)^3\).
4. Les pièces étant identiques, une répartition est déterminée par le nombre de pièces de chaque enfant. C’est donc une solution de \(x + y + z = 10\) dans \((\mathbb{N}^*)^3\). Il y a \(36\) répartitions.

La figure ci-dessous illustre le codage pour la solution \((3, 0, 7)\) de \(x + y + z = 10\).

Corrigé de l’exercice 13 : Applications croissantes

1. Une application strictement croissante \(f\) est injective. Donc \(f(I_p)\) est une partie de \(I_n\) à \(p\) éléments. Réciproquement, soit \(X = \{y_1 < \cdots < y_p\}\) une partie à \(p\) éléments de \(I_n\). L’unique application strictement croissante d’image \(X\) est \(i \mapsto y_i\). En effet, une telle application doit énumérer \(X\) dans l’ordre croissant. Ainsi, \(f \mapsto f(I_p)\) est bijective. Il y a \(\binom\,{n}{p}\) applications strictement croissantes de \(I_p\) dans \(I_n\).
2. Pour \(1 \leq\, i < p\), on a \(g(i+1) – g(i) = f(i+1) – f(i) + 1 \geq\, 1\). Donc \(g\) est strictement croissante. De plus, \(g(1) = f(1) \geq\, 1\) et \(g(p) = f(p) + p – 1 \leq\, n + p – 1\). Ainsi, \(g\) va de \(I_p\) dans \(I_{n+p-1}\). Réciproquement, soit \(g\) strictement croissante de \(I_p\) dans \(I_{n+p-1}\), et posons \(f(i) = g(i) – i + 1\). Alors \(f(i+1) – f(i) = g(i+1) – g(i) – 1 \geq\, 0\). De plus, \(f(1) = g(1) \geq\, 1\) et \(f(p) = g(p) – p + 1 \leq\, n\). Donc \(f\) est croissante de \(I_p\) dans \(I_n\), et les deux constructions sont réciproques.
3. D’après les deux questions précédentes, il y a \(\binom\,{n+p-1}{p}\) applications croissantes au sens large de \(I_p\) dans \(I_n\).
4. Pour \(p = 3\) et \(n = 5\), on obtient \(\binom\,{5}{3} = 10\) applications strictement croissantes. Il y a \(\binom\,{7}{3} = 35\) applications croissantes au sens large.

Corrigé de l’exercice 14 : Formule de Pascal et parties de cardinal pair

1. Les parties de \(E\) à \(k\) éléments qui contiennent \(a\) s’écrivent \(\{a\} \cup B\), avec \(B\) partie à \(k – 1\) éléments de \(E \setminus \{a\}\). Il y en a \(\binom\,{n-1}{k-1}\). Celles qui ne contiennent pas \(a\) sont les parties à \(k\) éléments de \(E \setminus \{a\}\). Il y en a \(\binom\,{n-1}{k}\). Ces deux classes sont disjointes et recouvrent tous les cas. Le principe additif donne \(\binom\,{n}{k} = \binom\,{n-1}{k-1} + \binom\,{n-1}{k}\).
2. L’application \(\sigma\) retire \(a\) s’il est présent et l’ajoute sinon. En l’appliquant deux fois, on retrouve donc \(A\) : \(\sigma \circ \sigma = \mathrm{id}\). Ainsi, \(\sigma\) est une bijection de \(\mathcal{P}(E)\), égale à sa réciproque. De plus, \(\operatorname{card}(\sigma(A)) = \operatorname{card}(A) \pm 1\). Donc \(\sigma\) envoie les parties de cardinal pair sur celles de cardinal impair, et inversement.
3. Notons \(\mathcal{P}_0\) et \(\mathcal{P}_1\) les ensembles des parties de cardinal pair et impair. La restriction de \(\sigma\) est une bijection de \(\mathcal{P}_0\) sur \(\mathcal{P}_1\). Donc ces deux ensembles ont le même cardinal. Comme ils partitionnent \(\mathcal{P}(E)\), chacun a \(2^n / 2 = 2^{n-1}\) éléments. Enfin,
   \[\sum_{k=0}^{n} (-1)^k \binom\,{n}{k} = \operatorname{card}(\mathcal{P}_0) – \operatorname{card}(\mathcal{P}_1) = 0.\]
   On a bien \(2^{n-1}\) parties de cardinal pair et une somme alternée nulle.
4. Pour \(n = 10\), il y a \(2^9 = 512\) parties de cardinal pair. La partie vide en fait partie. Il y a \(512\) parties de cardinal pair, dont \(511\) non vides.

Corrigé de l’exercice 15 : Comité et président

1. Comptons les couples \((C, x)\) où \(C\) est un comité de \(k\) membres et \(x \in C\). D’une part, on choisit \(C\), puis \(x\) dans \(C\) : \(k\binom\,{n}{k}\) couples. D’autre part, on choisit d’abord le président \(x\) parmi les \(n\) membres, puis les \(k – 1\) autres membres parmi \(n – 1\). On obtient \(n\binom\,{n-1}{k-1}\) couples. Donc \(k\binom\,{n}{k} = n\binom\,{n-1}{k-1}\).
2. En sommant pour \(k\) de \(1\) à \(n\), puis en posant \(j = k – 1\), on obtient
   \[\sum_{k=1}^{n} k\binom\,{n}{k} = n\sum_{j=0}^{n-1} \binom\,{n-1}{j} = n\,2^{n-1}.\]
   La somme vaut \(n\,2^{n-1}\).
3. Comptons les triplets \((C, x, y)\) où \(C\) est un comité de \(k\) membres, \(x\) son président et \(y\) son secrétaire, avec \(x \neq y\). D’une part, on choisit \(C\), puis \(x\) et \(y\) : \(\binom\,{n}{k}k(k-1)\) triplets. D’autre part, on choisit \(x\), puis \(y \neq x\), puis les \(k – 2\) autres membres : \(n(n-1)\binom\,{n-2}{k-2}\) triplets. D’où l’identité. En sommant pour \(k\) de \(2\) à \(n\), avec \(n \geq\, 2\), on obtient
   \[\sum_{k=2}^{n} k(k-1)\binom\,{n}{k} = n(n-1)\sum_{j=0}^{n-2}\binom\,{n-2}{j} = n(n-1)\,2^{n-2}.\]
   La somme vaut \(n(n-1)\,2^{n-2}\).
4. On écrit \(k^2 = k(k-1) + k\). Les termes d’indice \(k = 0\) et \(k = 1\) sont nuls dans la somme des \(k(k-1)\binom\,{n}{k}\). Ainsi,
   \[\sum_{k=0}^{n} k^2\binom\,{n}{k} = n(n-1)\,2^{n-2} + n\,2^{n-1} = n\,2^{n-2}(n – 1 + 2).\]
   On obtient \(n(n+1)\,2^{n-2}\). Pour \(n = 3\), la somme directe vaut \(1 \times 3 + 4 \times 3 + 9 \times 1 = 24\). De son côté, la formule donne \(3 \times 4 \times 2 = 24\).

Corrigé de l’exercice 16 : Formule de Vandermonde

1. L’assemblée compte \(a + b\) personnes. Il y a donc \(\binom\,{a+b}{n}\) délégations de \(n\) personnes. Classons-les maintenant selon le nombre \(k\) de femmes. Une délégation à \(k\) femmes s’obtient en choisissant \(k\) femmes parmi \(a\), puis \(n – k\) hommes parmi \(b\). Il y en a \(\binom\,{a}{k}\binom\,{b}{n-k}\), ce produit étant nul si \(k > a\) ou \(n – k > b\). Les valeurs de \(k\) donnent des cas disjoints. Le principe additif fournit la formule de Vandermonde.
2. Prenons \(a = b = n\). Par symétrie, \(\binom\,{n}{n-k} = \binom\,{n}{k}\). La formule devient \(\sum_{k=0}^{n} \binom\,{n}{k}^2 = \binom\,{2n}{n}\).
3. La ligne \(n = 4\) du triangle de Pascal est \(1, 4, 6, 4, 1\). La somme des carrés vaut \(1 + 16 + 36 + 16 + 1 = 70\). Or la ligne \(n = 8\) donne \(\binom\,{8}{4} = 70\). L’égalité est vérifiée.
4. Un chemin de \((0, 0)\) à \((n, n)\) compte \(2n\) pas. Après exactement \(n\) pas, il se trouve en un point \((k, n – k)\) de la droite \(x + y = n\). Ce point est unique, car \(x + y\) augmente de \(1\) à chaque pas. Il y a \(\binom\,{n}{k}\) chemins de \((0, 0)\) à \((k, n-k)\). De même, il y a \(\binom\,{n}{n-k} = \binom\,{n}{k}\) chemins de \((k, n – k)\) à \((n, n)\). Au total, il y a \(\binom\,{2n}{n}\) chemins. En classant selon \(k\), on retrouve \(\sum_{k=0}^{n}\binom\,{n}{k}^2 = \binom\,{2n}{n}\).

Corrigé de l’exercice 17 : Binôme et trinôme par dénombrement

1. Un mot de longueur \(n\) sur \(\{a, b\}\) à \(k\) lettres \(a\) est déterminé par la position de ces lettres. Il y en a \(\binom\,{n}{k}\). Développons \((a+b)^n\) sans commuter les facteurs. On obtient la somme des \(2^n\) mots de longueur \(n\). Ensuite, par commutativité, un mot à \(k\) lettres \(a\) vaut \(a^k b^{n-k}\). En regroupant selon \(k\), on obtient la formule du binôme. Ainsi, \((a+b)^n = \sum_{k=0}^{n}\binom\,{n}{k}a^k b^{n-k}\).
2. On choisit d’abord les \(i\) positions des lettres \(x\) parmi \(n\) : \(\binom\,{n}{i}\) choix. Ensuite, on choisit les \(j\) positions des lettres \(y\) parmi les \(n – i\) restantes : \(\binom\,{n-i}{j}\) choix. Enfin, les \(k\) positions restantes reçoivent \(z\). Le nombre de mots vaut donc
   \[\binom\,{n}{i}\binom\,{n-i}{j} = \frac{n!}{i!\,(n-i)!} \cdot \frac{(n-i)!}{j!\,k!} = \frac{n!}{i!\,j!\,k!},\]
   car \(n – i – j = k\). C’est le résultat annoncé.
3. Comme à la question 1, le coefficient de \(x^i y^j z^k\) dans \((x+y+z)^n\) est le nombre de mots correspondants. Pour \(n = 6\), \(i = 2\), \(j = 3\) et \(k = 1\), on obtient \(\frac{720}{2 \times 6 \times 1}\). Le coefficient vaut \(60\).
4. Il y a \(3^n\) mots de longueur \(n\) sur un alphabet à trois lettres. Classons-les selon le triplet \((i, j, k)\) de leurs nombres de lettres. Ces classes sont disjointes et la question 2 donne leur cardinal. Donc \(\sum_{i+j+k=n} \frac{n!}{i!\,j!\,k!} = 3^n\). On peut aussi prendre \(x = y = z = 1\) dans le développement.

Corrigé de l’exercice 18 : Formule de la crosse et sommes de puissances

1. Il y a \(\binom\,{n+1}{p+1}\) parties à \(p + 1\) éléments de \([\![1, n+1]\!]\). Le plus grand élément \(m\) d’une telle partie vérifie \(p + 1 \leq\, m \leq\, n + 1\). Si \(m\) est fixé, les \(p\) autres éléments forment une partie de \([\![1, m-1]\!]\). Il y a donc \(\binom\,{m-1}{p}\) parties de plus grand élément \(m\). En posant \(k = m – 1\) et en appliquant le principe additif, on obtient
   \[\binom\,{n+1}{p+1} = \sum_{k=p}^{n}\binom\,{k}{p}.\]
   C’est la formule de la crosse.
2. Pour \(p = 1\), on obtient \(\sum_{k=1}^{n} k = \binom\,{n+1}{2}\). Donc \(\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\).
3. On a \(2\binom\,{k}{2} + \binom\,{k}{1} = k(k-1) + k = k^2\). Cette égalité vaut aussi pour \(k = 0\) et \(k = 1\). Comme \(\binom\,{k}{2} = 0\) pour \(k < 2\), la formule de la crosse donne
   \[\sum_{k=1}^{n} k^2 = 2\binom\,{n+1}{3} + \binom\,{n+1}{2} = \frac{(n+1)n(n-1)}{3} + \frac{n(n+1)}{2}.\]
   En factorisant, on obtient \(\frac{n(n+1)}{6}\big(2(n-1) + 3\big)\). Ainsi, \(\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\).
4. On a \(6\binom\,{k}{3} = k(k-1)(k-2) = k^3 – 3k^2 + 2k\). Donc \(k^3 – 6\binom\,{k}{3} = 3k^2 – 2k\). D’après la question 3, cette quantité vaut \(6\binom\,{k}{2} + 3k – 2k = 6\binom\,{k}{2} + k\). Ainsi, \(\alpha = 6\) et \(\beta = 1\). La formule de la crosse donne alors
   \[\sum_{k=1}^{n} k^3 = 6\binom\,{n+1}{4} + 6\binom\,{n+1}{3} + \binom\,{n+1}{2}.\]
   Ces trois termes valent \(\frac{(n+1)n(n-1)(n-2)}{4}\), \((n+1)n(n-1)\) et \(\frac{(n+1)n}{2}\). En factorisant par \(\frac{n(n+1)}{4}\), il reste \((n-1)(n-2) + 4(n-1) + 2 = n^2 + n\). Donc \(\alpha = 6\), \(\beta = 1\) et \(\sum_{k=1}^{n} k^3 = \frac{n^2(n+1)^2}{4} = \big(\frac{n(n+1)}{2}\big)^2\).

Corrigé de l’exercice 19 : Principe des tiroirs

1. Les \(n\) paires \(\{2i – 1, 2i\}\), pour \(1 \leq\, i \leq\, n\), forment une partition de \([\![1, 2n]\!]\). Associons à chaque élément de \(A\) la paire qui le contient. On obtient une application d’un ensemble à \(n + 1\) éléments vers un ensemble à \(n\) éléments. Elle n’est donc pas injective. Ainsi, deux éléments distincts de \(A\) sont dans la même paire : ce sont deux entiers consécutifs \(m\) et \(m + 1\). Enfin, tout diviseur commun \(d\) de \(m\) et \(m + 1\) divise leur différence \(1\). Donc \(A\) contient deux entiers consécutifs, et ceux-ci sont premiers entre eux.
2. Pour l’existence, on prend pour \(2^r\) la plus grande puissance de \(2\) qui divise \(m\). Alors \(q = m / 2^r\) est impair. Pour l’unicité, supposons \(2^r q = 2^s q^{\prime}\) avec \(q, q^{\prime}\) impairs et \(r < s\). Alors \(q = 2^{s-r}q^{\prime}\) serait pair, ce qui est absurde. Donc \(r = s\), puis \(q = q^{\prime}\). Enfin, \(q\) est un entier impair de \([\![1, 2n]\!]\), car \(q \leq\, m\). Il prend au plus \(n\) valeurs : \(1, 3, \ldots, 2n – 1\).
3. L’application qui associe à \(m \in A\) sa partie impaire \(q\) va d’un ensemble à \(n + 1\) éléments dans un ensemble à \(n\) éléments. Elle n’est donc pas injective. Il existe ainsi \(a \neq b\) dans \(A\) avec \(a = 2^r q\) et \(b = 2^s q\). Comme \(a \neq b\), on a \(r \neq s\). Quitte à échanger \(a\) et \(b\), supposons \(r < s\). Alors \(b = 2^{s-r} a\). Donc \(a\) divise \(b\).
4. La partie \(\{2, 4, \ldots, 2n\}\) a \(n\) éléments, tous pairs. Elle ne contient ni deux entiers consécutifs, ni deux entiers premiers entre eux. Ensuite, considérons \(\{n + 1, \ldots, 2n\}\), qui a aussi \(n\) éléments. Si \(a\) divisait \(b\) avec \(a < b\) dans cette partie, on aurait \(b \geq\, 2a \geq\, 2n + 2\), ce qui est impossible. Le seuil \(n + 1\) est donc optimal pour les deux résultats.

Corrigé de l’exercice 20 : Mots binaires sans deux 1 consécutifs

1. Pour \(n = 1\), les mots \(0\) et \(1\) conviennent. Pour \(n = 2\), on garde \(00\), \(01\) et \(10\). Pour \(n = 3\), on garde \(000\), \(001\), \(010\), \(100\) et \(101\). Donc \(u_1 = 2\), \(u_2 = 3\) et \(u_3 = 5\).
2. Soit un mot admissible de longueur \(n + 2\). S’il commence par \(0\), le reste est un mot admissible quelconque de longueur \(n + 1\). Réciproquement, placer \(0\) devant un mot admissible donne un mot admissible. Cela fournit \(u_{n+1}\) mots. S’il commence par \(1\), la deuxième lettre est forcément \(0\). Le reste est alors un mot admissible de longueur \(n\), et la réciproque est vraie. Cela fournit \(u_n\) mots. Ces deux cas sont disjoints, d’où \(u_{n+2} = u_{n+1} + u_n\). On calcule ensuite \(u_4 = 8\), \(u_5 = 13\), \(u_6 = 21\), \(u_7 = 34\), \(u_8 = 55\) et \(u_9 = 89\). Finalement, \(u_{10} = 144\).
3. Un tel mot contient \(n – k\) zéros. Écrivons d’abord ces zéros. Ils délimitent \(n – k + 1\) emplacements : avant le premier, entre deux zéros consécutifs, après le dernier. Le mot n’a pas deux \(1\) consécutifs si et seulement si chaque emplacement reçoit au plus un \(1\). Un mot admissible correspond donc exactement au choix de \(k\) emplacements parmi \(n – k + 1\). Il y en a \(\binom\,{n-k+1}{k}\), ce nombre étant nul si \(k > n – k + 1\).
4. En classant les mots selon leur nombre \(k\) de \(1\), on obtient \(u_n = \sum_{k=0}^{n}\binom\,{n-k+1}{k}\). Pour \(n = 10\), les termes non nuls correspondent à \(k \leq\, 5\) :
   \[\binom\,{11}{0} + \binom\,{10}{1} + \binom\,{9}{2} + \binom\,{8}{3} + \binom\,{7}{4} + \binom\,{6}{5} = 1 + 10 + 36 + 56 + 35 + 6.\]
   On retrouve bien \(144 = u_{10}\).

Point de méthode : la technique « placer d’abord les objets imposés, puis choisir des emplacements » sert dès qu’une contrainte interdit à deux objets d’être voisins.

Corrigé de l’exercice 21 : Problème : surjections et partitions

1. Si \(p > n\), l’image d’une application définie sur \([\![1, n]\!]\) a au plus \(n < p\) éléments. Donc \(S(n, p) = 0\). Ensuite, il n’existe qu’une application vers un singleton, et elle est surjective : \(S(n, 1) = 1\). Pour \(p = n\), une application entre deux ensembles de même cardinal fini est surjective si et seulement si elle est bijective. Donc \(S(n, n) = n!\). Enfin, parmi les \(2^n\) applications de \([\![1, n]\!]\) dans \(\{1, 2\}\), seules les deux applications constantes ne sont pas surjectives. Ainsi, \(S(n, p) = 0\) si \(p > n\), \(S(n, 1) = 1\), \(S(n, n) = n!\) et \(S(n, 2) = 2^n – 2\).
2. Toute application \(f\) de \([\![1, n]\!]\) dans \([\![1, p]\!]\) a pour image une partie non vide \(J\). De plus, \(f\) est une surjection de \([\![1, n]\!]\) sur \(J\). Réciproquement, une surjection sur \(J\) est une application d’image \(J\). Si \(\operatorname{card}(J) = j\), il y a donc \(S(n, j)\) applications d’image \(J\). Il y a \(\binom\,{p}{j}\) parties \(J\) de cardinal \(j\), et ces cas sont disjoints. On obtient \(p^n = \sum_{j=1}^{p}\binom\,{p}{j}S(n, j)\).
3. Soit \(f\) une surjection de \([\![1, n]\!]\) sur \([\![1, p]\!]\). Posons \(y = f(n)\) : il y a \(p\) choix. Notons \(g\) la restriction de \(f\) à \([\![1, n-1]\!]\). L’image de \(f\) est \(g([\![1, n-1]\!]) \cup \{y\}\). Donc \(f\) est surjective si et seulement si l’image de \(g\) contient \([\![1, p]\!] \setminus \{y\}\). Deux cas disjoints se présentent. Soit l’image de \(g\) est exactement \([\![1, p]\!] \setminus \{y\}\) : \(S(n-1, p-1)\) choix de \(g\). Soit c’est \([\![1, p]\!]\) tout entier : \(S(n-1, p)\) choix. Par conséquent, \(S(n, p) = p\big(S(n-1, p-1) + S(n-1, p)\big)\).
4. On part de \(S(1, 1) = 1\) et l’on applique la relation ligne par ligne, avec \(S(m, p) = 0\) pour \(p > m\). Par exemple, \(S(5, 3) = 3\big(S(4, 2) + S(4, 3)\big) = 3(14 + 36) = 150\).
   \[\begin{array}{c|ccccc} n \backslash p & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 & & & & \\ 2 & 1 & 2 & & & \\ 3 & 1 & 6 & 6 & & \\ 4 & 1 & 14 & 36 & 24 & \\ 5 & 1 & 30 & 150 & 240 & 120 \end{array}\]
   Pour \(n = 4\) et \(p = 3\), on calcule \(3 \times 1 + 3 \times 14 + 1 \times 36 = 3 + 42 + 36 = 81\). On trouve bien \(81 = 3^4\). On retrouve aussi \(S(4, 3) = 36\), comme dans l’exercice 5.
5. Soit \(f\) une surjection de \([\![1, n+1]\!]\) sur \([\![1, n]\!]\). Les \(n\) ensembles d’antécédents sont non vides et leurs cardinaux ont pour somme \(n + 1\). Donc exactement un élément de l’ensemble d’arrivée a deux antécédents, les autres en ont un seul. Pour construire \(f\), on choisit d’abord la paire \(\{a, b\}\) d’éléments qui ont même image : \(\binom\,{n+1}{2}\) choix. Il reste \(n\) « blocs » : cette paire et \(n – 1\) singletons. Ensuite, \(f\) correspond à une bijection de ces blocs sur \([\![1, n]\!]\) : \(n!\) choix. Ainsi,
   \[S(n+1, n) = \frac{(n+1)n}{2}\, n! = \frac{n\,(n+1)!}{2}.\]
   La formule est démontrée. Elle donne \(S(3, 2) = 6\), \(S(4, 3) = 36\) et \(S(5, 4) = 240\), en accord avec la table.
6. Une répartition est une application de l’ensemble des \(5\) boules dans celui des \(3\) boîtes. Il y en a \(3^5 = 243\). Aucune boîte n’est vide si et seulement si l’application est surjective, soit \(S(5, 3) = 150\) cas. La probabilité vaut donc \(\frac{150}{243} = \frac{50}{81} \approx 0{,}617\). Ensuite, une surjection détermine la partition de \([\![1, 5]\!]\) formée de ses trois ensembles d’antécédents. Inversement, une partition en trois parties non vides provient de \(3! = 6\) surjections, selon la boîte attribuée à chaque partie. La probabilité vaut \(\frac{50}{81}\), et il existe \(\frac{150}{6} = 25\) partitions de \([\![1, 5]\!]\) en trois parties.

La figure ci-dessous représente une de ces surjections et la partition associée.

Revenir aux énoncés des exercices

Pour aller plus loin en maths sup

• Le cours : dénombrement, cours de maths sup
• Les énoncés : exercices de maths sup sur dénombrement
• À maîtriser avant : Logique, ensembles, applications et relations, Calculs algébriques : sommes, produits, inégalités
• Chapitre précédent : Familles sommables
• Chapitre suivant : Probabilités sur un univers fini et variables aléatoires
• Tester vos connaissances : QCM de maths sup par chapitre
• Le sommaire : tous les chapitres de maths sup et les chapitres de maths spé