Contrôle de maths sup : dénombrement et formules combinatoires

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

Calculatrice interdite.

Dans tout l’exercice, \(E\) et \(F\) sont deux ensembles finis, avec \(\operatorname{card} E = p\) et \(\operatorname{card} F = n\), où \(n\) et \(p\) sont des entiers naturels. Chaque résultat doit être justifié par une construction explicite (découpage ou bijection), et non par la seule citation d’une formule.

1. Démontrez que l’ensemble \(F^E\) des applications de \(E\) dans \(F\) a pour cardinal \(n^p\). (1,5 point)
2. On suppose \(p \leq\, n\). Démontrez que le nombre d’injections de \(E\) dans \(F\) est égal à \(\dfrac{n!}{(n-p)!}\). (1,5 point)
3. À l’aide de la fonction indicatrice d’une partie, construisez une bijection de \(\mathcal{P}(E)\) sur \(\{0, 1\}^E\). Déduisez-en le cardinal de \(\mathcal{P}(E)\). (1 point)

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

Soit \(A\), \(B\) et \(C\) trois parties d’un ensemble fini \(E\).

1. En écrivant \(A \cup B\) comme la réunion disjointe de \(A\) et de \(B \setminus A\), démontrez que \(\operatorname{card}(A \cup B) = \operatorname{card} A + \operatorname{card} B – \operatorname{card}(A \cap B)\). (1 point)
2. En appliquant ce résultat à \(A \cup B\) et \(C\), établissez une formule donnant \(\operatorname{card}(A \cup B \cup C)\) en fonction des cardinaux de \(A\), \(B\), \(C\) et de leurs intersections. (1,5 point)
3. Pour \(d \in \mathbb{N}^*\), on note \(A_d\) l’ensemble des entiers de \([\![1, 1000]\!]\) divisibles par \(d\). Déterminez le nombre d’entiers de \([\![1, 1000]\!]\) divisibles par 2, par 3 ou par 5, puis le nombre de ceux qui ne sont divisibles par aucun de ces trois nombres. (1,5 point)

Exercice 3 : Anagrammes et tirages (4 points)

On appelle anagramme d’un mot toute suite de lettres obtenue en permutant ses lettres, qu’elle ait un sens ou non.

1. Combien le mot CONCOURS possède-t-il d’anagrammes ? Justifiez par un choix successif des positions de chaque lettre. (1,5 point)
2. Combien de ces anagrammes contiennent les deux lettres C côte à côte ? (1 point)
3. Une urne contient 10 boules numérotées de 1 à 10. On tire 3 boules. Dénombrez les résultats possibles lorsque le tirage est successif avec remise, successif sans remise, puis simultané, en précisant à chaque fois l’objet mathématique qui modélise un résultat. (1 point)
4. Parmi les tirages simultanés de 3 boules, combien ont pour plus grand numéro 7 ? (0,5 point)

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

On rappelle que, pour tout ensemble \(E\) à \(n\) éléments et tout entier \(p\), le nombre \(\binom\,{n}{p}\) est le nombre de parties de \(E\) à \(p\) éléments. Les démonstrations demandées sont combinatoires : n’utilisez pas l’expression de \(\binom\,{n}{p}\) à l’aide de factorielles.

1. Soit \(E\) un ensemble à \(n + 1\) éléments et \(a\) un élément fixé de \(E\). En séparant les parties à \(p + 1\) éléments de \(E\) selon qu’elles contiennent \(a\) ou non, démontrez que \(\binom\,{n+1}{p+1} = \binom\,{n}{p} + \binom\,{n}{p+1}\). (1,5 point)
2. Soit \(n\), \(m\) et \(p\) des entiers naturels. Démontrez la formule de Vandermonde : \[\sum_{k=0}^{p} \binom\,{n}{k}\binom\,{m}{p-k} = \binom\,{n+m}{p}.\] (1 point)
3. Déduisez-en la valeur de \(\displaystyle\sum_{k=0}^{n} \binom\,{n}{k}^2\). (0,5 point)

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

Soit \(n \geq\, 1\) un entier. On note \(E = [\![1, n+1]\!]\) et \(F = [\![1, n]\!]\), et l’on cherche le nombre \(s_n\) de surjections de \(E\) sur \(F\).

1. Soit \(f\) une surjection de \(E\) sur \(F\). Démontrez qu’il existe un unique élément \(y\) de \(F\) qui possède exactement deux antécédents par \(f\), et que tout autre élément de \(F\) possède exactement un antécédent. (1,5 point)
2. Construisez une bijection entre l’ensemble des surjections de \(E\) sur \(F\) et l’ensemble des couples \((\{i, j\}, \sigma)\), où \(\{i, j\}\) est une paire d’éléments de \(E\) et \(\sigma\) une bijection d’un ensemble à \(n\) éléments, que vous préciserez, sur \(F\). Déduisez-en que \(s_n = \dfrac{n\,(n+1)!}{2}\). (2 points)
3. Vérifiez ce résultat pour \(n = 2\) en dénombrant directement les applications de \([\![1, 3]\!]\) dans \([\![1, 2]\!]\) qui ne sont pas surjectives. (0,5 point)
4. Cinq étudiants sont répartis dans quatre salles de travaux pratiques, aucune salle ne devant rester vide. Combien existe-t-il de répartitions possibles ? Retrouvez ce nombre par un second raisonnement. (1 point)

Réviser avant le contrôle : dénombrement et formules combinatoires

Avant de faire ce contrôle, 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.