Corrigé du contrôle de maths sup : dénombrement et formules combinatoires

Exercice 1 : Applications, injections et parties (4 points)

1. Numérotons les éléments de \(E\) : \(E = \{x_1, \ldots, x_p\}\). L’application \(\Phi : F^E \to F^p\), \(f \mapsto (f(x_1), \ldots, f(x_p))\), est bijective. En effet, une application est entièrement déterminée par ses valeurs, donc \(\Phi\) est injective ; de plus, toute \(p\)-liste \((y_1, \ldots, y_p)\) est l’image de l’application qui envoie \(x_k\) sur \(y_k\), donc \(\Phi\) est surjective. Par conséquent, \(\operatorname{card} F^E = \operatorname{card} F^p\). Or le cardinal d’un produit cartésien est le produit des cardinaux, d’où \(\operatorname{card} F^p = n^p\). Ainsi, \(\operatorname{card} F^E = n^p\) (avec la convention \(n^0 = 1\) : lorsque \(E = \varnothing\), il existe une seule application, l’application vide).
2. Par la même bijection \(\Phi\), les injections de \(E\) dans \(F\) correspondent exactement aux \(p\)-listes d’éléments deux à deux distincts de \(F\). Dénombrons ces listes par le principe multiplicatif : on choisit \(y_1\) parmi \(n\) éléments, puis \(y_2\) parmi les \(n – 1\) éléments différents de \(y_1\), et ainsi de suite jusqu’à \(y_p\), choisi parmi \(n – p + 1\) éléments. Le nombre de choix ne dépend pas des choix précédents, donc le nombre d’injections vaut \[n(n-1)\cdots(n-p+1) = \frac{n!}{(n-p)!}.\] Il y a donc \(\dfrac{n!}{(n-p)!}\) injections de \(E\) dans \(F\).
3. À toute partie \(A\) de \(E\), associons sa fonction indicatrice \(\mathbf{1}_A : E \to \{0, 1\}\), qui vaut 1 sur \(A\) et 0 ailleurs. L’application \(A \mapsto \mathbf{1}_A\) est injective, car \(A = \{x \in E \mid \mathbf{1}_A(x) = 1\}\) se lit sur l’indicatrice. Elle est aussi surjective : toute application \(g : E \to \{0, 1\}\) est l’indicatrice de \(g^{-1}(\{1\})\). C’est donc une bijection de \(\mathcal{P}(E)\) sur \(\{0, 1\}^E\), et d’après la question a), \(\operatorname{card} \mathcal{P}(E) = 2^p\).

Barème : a) 1,5 point : 1 point pour la bijection avec les \(p\)-listes justifiée, 0,5 point pour la conclusion ; b) 1,5 point : 0,5 point pour la correspondance avec les listes d’éléments distincts, 1 point pour le principe multiplicatif rédigé ; c) 1 point : 0,5 point pour la bijection justifiée, 0,5 point pour le cardinal.

Exercice 2 : Cardinal d’une réunion (4 points)

1. On a \(A \cup B = A \cup (B \setminus A)\), et cette réunion est disjointe. Donc \(\operatorname{card}(A \cup B) = \operatorname{card} A + \operatorname{card}(B \setminus A)\). De même, \(B\) est la réunion disjointe de \(B \cap A\) et de \(B \setminus A\), d’où \(\operatorname{card}(B \setminus A) = \operatorname{card} B – \operatorname{card}(A \cap B)\). En reportant, on obtient \(\operatorname{card}(A \cup B) = \operatorname{card} A + \operatorname{card} B – \operatorname{card}(A \cap B)\).
2. Appliquons a) aux parties \(A \cup B\) et \(C\) :
   \[\operatorname{card}(A \cup B \cup C) = \operatorname{card}(A \cup B) + \operatorname{card} C – \operatorname{card}((A \cup B) \cap C).\]
   Par distributivité, \((A \cup B) \cap C = (A \cap C) \cup (B \cap C)\), et l’intersection de ces deux parties est \(A \cap B \cap C\). Une nouvelle application de a) donne donc
   \[\operatorname{card}((A \cup B) \cap C) = \operatorname{card}(A \cap C) + \operatorname{card}(B \cap C) – \operatorname{card}(A \cap B \cap C).\]
   En remplaçant aussi \(\operatorname{card}(A \cup B)\) par son expression, on obtient
   \[\operatorname{card}(A \cup B \cup C) = \operatorname{card} A + \operatorname{card} B + \operatorname{card} C – \operatorname{card}(A \cap B) – \operatorname{card}(A \cap C) – \operatorname{card}(B \cap C) + \operatorname{card}(A \cap B \cap C).\]
3. Pour \(d \in [\![1, 1000]\!]\), les multiples de \(d\) dans \([\![1, 1000]\!]\) sont \(d, 2d, \ldots, qd\) avec \(q = \lfloor \dfrac{1000}{d} \rfloor\). Donc \(\operatorname{card} A_d = \lfloor \dfrac{1000}{d} \rfloor\). De plus, comme 2, 3 et 5 sont premiers entre eux deux à deux, un entier est divisible par 2 et par 3 si et seulement s’il est divisible par 6. Ainsi \(A_2 \cap A_3 = A_6\), et de même \(A_2 \cap A_5 = A_{10}\), \(A_3 \cap A_5 = A_{15}\), \(A_2 \cap A_3 \cap A_5 = A_{30}\). On trouve :

   \(\operatorname{card} A_2 = 500\), \(\operatorname{card} A_3 = 333\), \(\operatorname{card} A_5 = 200\) ;

   \(\operatorname{card} A_6 = 166\), \(\operatorname{card} A_{10} = 100\), \(\operatorname{card} A_{15} = 66\), \(\operatorname{card} A_{30} = 33\).

   D’après b) :
   \[\operatorname{card}(A_2 \cup A_3 \cup A_5) = 500 + 333 + 200 – 166 – 100 – 66 + 33 = 734.\]
   Il y a donc 734 entiers divisibles par 2, par 3 ou par 5, et par passage au complémentaire \(1000 – 734 = 266\) entiers divisibles par aucun des trois. Le diagramme ci-dessous donne l’effectif de chaque zone ; leur somme redonne bien 734.

   

Erreur fréquente : oublier de rajouter \(\operatorname{card}(A \cap B \cap C)\), que l’on a retiré trois fois après l’avoir compté trois fois.

Barème : a) 1 point : 0,5 point pour la réunion disjointe, 0,5 point pour le calcul de \(\operatorname{card}(B \setminus A)\) ; b) 1,5 point : 0,5 point pour la distributivité, 1 point pour la formule finale ; c) 1,5 point : 0,5 point pour les intersections \(A_6\), \(A_{10}\), \(A_{15}\), \(A_{30}\) justifiées, 0,5 point pour les sept cardinaux, 0,5 point pour 734 et 266.

Exercice 3 : Anagrammes et tirages (4 points)

1. Le mot CONCOURS compte 8 lettres : deux C, deux O, puis N, U, R et S. Une anagramme est déterminée par le choix des positions de chaque lettre. On choisit d’abord les 2 positions des C parmi 8, soit \(\binom\,{8}{2} = 28\) choix. Ensuite, on choisit les 2 positions des O parmi les 6 restantes, soit \(\binom\,{6}{2} = 15\) choix. Enfin, on place N, U, R et S, qui sont distinctes, sur les 4 positions restantes, soit \(4! = 24\) façons. Par le principe multiplicatif, le nombre d’anagrammes est \(28 \times 15 \times 24 = 10\,080\). Le mot CONCOURS possède donc 10 080 anagrammes, ce que l’on retrouve par \(\dfrac{8!}{2!\,2!} = \dfrac{40\,320}{4}\).
2. Collons les deux C en un seul bloc « CC ». Les anagrammes cherchées sont alors en bijection avec les arrangements de 7 objets : le bloc, deux O, N, U, R et S. On choisit la position du bloc parmi 7, puis les 2 positions des O parmi les 6 restantes, puis on place les 4 lettres distinctes : \(7 \times \binom\,{6}{2} \times 4! = 7 \times 15 \times 24 = 2\,520\). Il y a donc 2 520 anagrammes où les deux C sont côte à côte.
3. Avec remise, un résultat est une 3-liste d’éléments de \([\![1, 10]\!]\) : il y en a \(10^3 = 1\,000\). Sans remise, un résultat est une 3-liste d’éléments distincts, c’est-à-dire un arrangement : il y en a \(10 \times 9 \times 8 = 720\). Enfin, lors d’un tirage simultané, un résultat est une partie à 3 éléments : il y en a \(\binom\,{10}{3} = 120\).
4. Une partie à 3 éléments de plus grand élément 7 s’écrit \(\{7\} \cup B\), où \(B\) est une partie à 2 éléments de \([\![1, 6]\!]\), et cette écriture est unique. Il y a donc \(\binom\,{6}{2} = 15\) tirages de plus grand numéro 7.

Barème : a) 1,5 point : 1 point pour le choix successif des positions, 0,5 point pour 10 080 ; b) 1 point : 0,5 point pour le bloc, 0,5 point pour 2 520 ; c) 1 point : 0,5 point pour les trois modèles (listes, arrangements, parties), 0,5 point pour les trois nombres ; d) 0,5 point pour la bijection et 15.

Exercice 4 : Formules de Pascal et de Vandermonde (3 points)

1. Notons \(\mathcal{P}_{p+1}(E)\) l’ensemble des parties de \(E\) à \(p + 1\) éléments. On le partage en deux ensembles disjoints : \(\mathcal{A}\), formé des parties qui contiennent \(a\), et \(\mathcal{B}\), formé des autres. D’une part, l’application \(X \mapsto X \setminus \{a\}\) est une bijection de \(\mathcal{A}\) sur l’ensemble des parties à \(p\) éléments de \(E \setminus \{a\}\) ; sa réciproque est \(Y \mapsto Y \cup \{a\}\). Comme \(E \setminus \{a\}\) a \(n\) éléments, \(\operatorname{card} \mathcal{A} = \binom\,{n}{p}\). D’autre part, \(\mathcal{B}\) est exactement l’ensemble des parties à \(p + 1\) éléments de \(E \setminus \{a\}\), donc \(\operatorname{card} \mathcal{B} = \binom\,{n}{p+1}\). Par le principe additif, on conclut : \(\binom\,{n+1}{p+1} = \binom\,{n}{p} + \binom\,{n}{p+1}\).
2. Soit \(E\) et \(F\) deux ensembles disjoints de cardinaux \(n\) et \(m\) ; alors \(E \cup F\) a \(n + m\) éléments. Pour \(k \in [\![0, p]\!]\), notons \(\mathcal{C}_k\) l’ensemble des parties \(X\) de \(E \cup F\) à \(p\) éléments telles que \(\operatorname{card}(X \cap E) = k\). Les \(\mathcal{C}_k\) sont deux à deux disjointes et recouvrent l’ensemble des parties à \(p\) éléments. De plus, l’application \(X \mapsto (X \cap E, X \cap F)\) est une bijection de \(\mathcal{C}_k\) sur l’ensemble des couples formés d’une partie à \(k\) éléments de \(E\) et d’une partie à \(p – k\) éléments de \(F\) ; sa réciproque est \((Y, Z) \mapsto Y \cup Z\). Donc \(\operatorname{card} \mathcal{C}_k = \binom\,{n}{k}\binom\,{m}{p-k}\) (ce produit est nul si \(k > n\) ou \(p – k > m\)). En sommant, \(\displaystyle\sum_{k=0}^{p} \binom\,{n}{k}\binom\,{m}{p-k} = \binom\,{n+m}{p}\).
3. Prenons \(m = n\) et \(p = n\) dans la formule de Vandermonde. Par symétrie, \(\binom\,{n}{n-k} = \binom\,{n}{k}\), d’où \(\displaystyle\sum_{k=0}^{n} \binom\,{n}{k}^2 = \binom\,{2n}{n}\).

Barème : a) 1,5 point : 0,5 point pour le partage, 0,5 point pour la bijection sur \(\mathcal{A}\), 0,5 point pour \(\mathcal{B}\) et la conclusion ; b) 1 point : 0,5 point pour la partition selon \(\operatorname{card}(X \cap E)\), 0,5 point pour la bijection et le cardinal ; c) 0,5 point.

Exercice 5 : Surjections d’un ensemble à n + 1 éléments (5 points)

1. Les ensembles \(f^{-1}(\{y\})\), pour \(y \in F\), sont deux à deux disjoints et leur réunion est \(E\). Donc \[\sum_{y \in F} \operatorname{card} f^{-1}(\{y\}) = n + 1.\] Comme \(f\) est surjective, chacun de ces \(n\) entiers vaut au moins 1. Écrivons \(\operatorname{card} f^{-1}(\{y\}) = 1 + e_y\) avec \(e_y \geq\, 0\). Alors \(\sum_{y \in F} e_y = 1\), donc un seul des \(e_y\) vaut 1 et tous les autres sont nuls. Ainsi, un unique élément \(y_0\) de \(F\) a exactement deux antécédents, et les autres en ont exactement un.
2. Soit \(f\) une surjection et \(\{i, j\} = f^{-1}(\{y_0\})\) la paire donnée par a). Notons \(E_{i,j}\) l’ensemble à \(n\) éléments obtenu à partir de \(E\) en remplaçant \(i\) et \(j\) par le seul élément \(\{i, j\}\) : ses éléments sont la paire \(\{i, j\}\) et les \(n – 1\) singletons \(\{x\}\), \(x \notin \{i, j\}\). L’application \(\sigma : E_{i,j} \to F\), qui envoie chaque bloc sur la valeur commune de \(f\) sur ce bloc, est bien définie. Elle est surjective car \(f\) l’est, donc bijective puisque les deux ensembles ont \(n\) éléments. On associe ainsi à \(f\) le couple \((\{i, j\}, \sigma)\).

   Réciproquement, un couple \((\{i, j\}, \sigma)\) définit une application \(f\) en posant \(f(x) = \sigma(\text{bloc contenant } x)\). Elle est surjective, et la paire des deux antécédents de même image est exactement \(\{i, j\}\). Les deux constructions sont réciproques l’une de l’autre, ce qui donne la bijection annoncée.

   Il y a \(\binom\,{n+1}{2}\) paires dans \(E\) et, pour chacune, \(n!\) bijections de \(E_{i,j}\) sur \(F\). Par conséquent, \[s_n = \binom\,{n+1}{2}\, n! = \frac{(n+1)n}{2}\, n! = \frac{n\,(n+1)!}{2}.\] On obtient bien \(s_n = \dfrac{n\,(n+1)!}{2}\).

3. Pour \(n = 2\), il y a \(2^3 = 8\) applications de \([\![1, 3]\!]\) dans \([\![1, 2]\!]\). Les seules qui ne sont pas surjectives sont les deux applications constantes. Il reste donc \(8 – 2 = 6\) surjections. La formule donne \(s_2 = \dfrac{2 \times 3!}{2} = 6\) : le résultat est vérifié.
4. Une répartition est une surjection de l’ensemble des 5 étudiants sur l’ensemble des 4 salles, d’où, avec \(n = 4\) : \(s_4 = \dfrac{4 \times 5!}{2} = \dfrac{4 \times 120}{2} = 240\). Second raisonnement : on choisit d’abord les deux étudiants qui partagent une salle, soit \(\binom\,{5}{2} = 10\) choix ; ensuite, on attribue une salle différente à chacun des 4 groupes, soit \(4! = 24\) façons. On retrouve \(10 \times 24 = 240\). Il existe donc 240 répartitions.

Erreur fréquente : placer d’abord un étudiant dans chaque salle (\(5 \times 4 \times 3 \times 2 = 120\) façons), puis le cinquième dans l’une des 4 salles, ce qui donne 480 : chaque répartition est alors comptée deux fois, selon lequel des deux étudiants du binôme a été placé en premier.

Barème : a) 1,5 point : 0,5 point pour la partition de \(E\) en fibres, 1 point pour l’argument de somme ; b) 2 points : 1 point pour la construction de la bijection et de sa réciproque, 0,5 point pour le dénombrement des couples, 0,5 point pour la formule ; c) 0,5 point ; d) 1 point : 0,5 point pour 240, 0,5 point pour le second raisonnement.

Revenir à l’énoncé du contrôle

Après le corrigé du contrôle : dénombrement et formules combinatoires

Pour consolider ce que le corrigé vous a appris, relisez le cours « Dénombrement » en maths sup puis entraînez-vous avec les exercices corrigés dénombrement.

Retrouvez tous les contrôles de maths sup classés par chapitre, ou choisissez un autre niveau sur la page contrôles de maths du CP au post-bac.