Dénombrement : exercices de maths sup corrigés en PDF.

Exercice 1 : Codes à quatre chiffres

Un code secret est une suite de quatre chiffres pris dans \(\{0, 1, \ldots, 9\}\), par exemple \(0\,7\,7\,3\).

1. Combien existe-t-il de codes ?
2. Combien de codes ont leurs quatre chiffres deux à deux distincts ?
3. En déduire le nombre de codes qui comportent au moins deux chiffres égaux.
4. Combien de codes ont des chiffres rangés dans l’ordre strictement croissant (comme \(1\,4\,5\,8\)) ?
5. Combien de codes contiennent exactement deux fois le chiffre \(7\) ?

Exercice 2 : Langues vivantes dans une classe

Une classe compte \(40\) étudiants. Parmi eux, \(25\) suivent l’option anglais renforcé, \(18\) suivent l’option espagnol et \(7\) suivent les deux options. On note \(A\) et \(S\) les ensembles d’étudiants inscrits respectivement en anglais et en espagnol. La figure ci-dessous représente la situation.

1. Combien d’étudiants suivent au moins une des deux options ?
2. Combien n’en suivent aucune ?
3. Combien suivent exactement une option ?
4. On forme un binôme composé d’un étudiant qui suit seulement l’anglais et d’un étudiant qui suit seulement l’espagnol. Combien de binômes sont possibles ?

Exercice 3 : Anagrammes du mot BANANE

On appelle anagramme du mot \(\text{BANANE}\) tout mot de six lettres, ayant un sens ou non, formé avec exactement les mêmes lettres.

1. Combien le mot \(\text{BANANE}\) possède-t-il d’anagrammes ?
2. Combien d’anagrammes commencent par la lettre B ?
3. Combien d’anagrammes contiennent les deux lettres N côte à côte ?
4. En déduire le nombre d’anagrammes où les deux N ne sont pas voisins.

Exercice 4 : Mains de cinq cartes

Un jeu de \(32\) cartes comporte quatre couleurs (pique, cœur, carreau, trèfle) et, dans chaque couleur, huit hauteurs : \(7, 8, 9, 10\), valet, dame, roi, as. Une main est un ensemble de \(5\) cartes du jeu.

1. Combien existe-t-il de mains ?
2. Combien de mains contiennent exactement deux as ?
3. Combien de mains contiennent au moins un cœur ?
4. Combien de mains sont formées de cinq cartes de la même couleur ?

Exercice 5 : Applications entre deux petits ensembles

On pose \(E = \{1, 2, 3\}\) et \(F = \{a, b, c, d\}\).

1. Combien existe-t-il d’applications de \(E\) dans \(F\) ? Combien sont injectives ?
2. Existe-t-il une surjection de \(E\) sur \(F\) ? Justifier.
3. Combien existe-t-il d’applications de \(F\) dans \(E\) ? Combien sont injectives ?
4. Démontrer qu’une application de \(F\) dans \(E\) est surjective si et seulement si exactement un élément de \(E\) possède deux antécédents, les deux autres en ayant un seul. En déduire le nombre de surjections de \(F\) sur \(E\).

Exercice 6 : Lancers de trois dés

On lance trois dés à six faces, un rouge, un vert et un bleu. Un résultat est le triplet \((r, v, b)\) des faces obtenues.

1. Combien y a-t-il de résultats possibles ?
2. Combien de résultats ont trois faces deux à deux distinctes ? Exactement deux faces égales ? Trois faces égales ?
3. Combien de résultats comportent au moins un six ?
4. Combien de résultats ont une somme égale à \(10\) ? On pourra poser \(x = r – 1\), \(y = v – 1\), \(z = b – 1\).

Exercice 7 : Injectivité et surjectivité en cardinal fini

1. Montrer que \(f : n \mapsto n + 1\) est une injection non surjective de \(\mathbb{N}\) dans \(\mathbb{N}\), et que \(g : n \mapsto \lfloor n/2 \rfloor\) est une surjection non injective de \(\mathbb{N}\) dans \(\mathbb{N}\). Pourquoi cela ne contredit-il pas le cours ?
2. Soit \(n \geq\, 2\) et \(a\) un entier premier avec \(n\). Pour \(x \in [\![0, n-1]\!]\), on note \(\varphi(x)\) le reste de la division euclidienne de \(ax\) par \(n\). Montrer que \(\varphi\) est une bijection de \([\![0, n-1]\!]\) sur lui-même. En déduire qu’il existe un entier \(u\) tel que \(au \equiv 1 \pmod n\).
3. Déterminer un tel entier \(u\) lorsque \(n = 7\) et \(a = 3\), en dressant la table de \(\varphi\).
4. Soit \(E\) un ensemble fini et \(f, g : E \to E\) telles que \(g \circ f = \mathrm{id}_E\). Montrer que \(f\) et \(g\) sont bijectives et que \(f \circ g = \mathrm{id}_E\).

Exercice 8 : Couples de parties d’un ensemble

Soit \(E\) un ensemble fini à \(n\) éléments.

1. Combien existe-t-il de couples \((A, B)\) de parties de \(E\) ?
2. Combien existe-t-il de couples \((A, B)\) de parties de \(E\) tels que \(A \subset B\) ? On pourra associer à chaque tel couple une application de \(E\) dans un ensemble à trois éléments.
3. Combien existe-t-il de couples \((A, B)\) tels que \(A \cap B = \varnothing\) ? tels que \(A \cap B = \varnothing\) et \(A \cup B = E\) ?
4. En comptant autrement les couples de la question 2, selon le cardinal \(k\) de \(B\), démontrer que \(\displaystyle\sum_{k=0}^{n} \binom\,{n}{k} 2^k = 3^n\).

Exercice 9 : Chemins dans un quadrillage

Dans le plan muni d’un repère, on se déplace de point entier en point entier par pas unitaires, soit vers la droite (\(D\)), soit vers le haut (\(H\)). On considère les points \(O(0, 0)\), \(C(2, 1)\) et \(B(5, 3)\), représentés ci-dessous.

1. Justifier qu’un chemin de \(O\) à \(B\) est un mot de \(8\) lettres contenant \(5\) fois \(D\) et \(3\) fois \(H\). Combien existe-t-il de chemins de \(O\) à \(B\) ?
2. Combien de chemins de \(O\) à \(B\) passent par \(C\) ?
3. Combien de chemins de \(O\) à \(B\) évitent le point \(C\) ?
4. Plus généralement, pour \(p, q \in \mathbb{N}\), combien existe-t-il de chemins de \(O\) à \((p, q)\) ? En classant ces chemins selon leur dernier pas, retrouver la formule de Pascal lorsque \(p, q \geq\, 1\).

Exercice 10 : Diagonales et triangles d’un polygone

Soit \(n \geq\, 6\) et \(\mathcal{P}\) un polygone convexe à \(n\) sommets. Un triangle de \(\mathcal{P}\) est un triangle dont les trois sommets sont des sommets de \(\mathcal{P}\). La figure montre le cas \(n = 8\).

1. Combien de segments joignent deux sommets de \(\mathcal{P}\) ? En déduire le nombre de diagonales de \(\mathcal{P}\).
2. Combien \(\mathcal{P}\) a-t-il de triangles ?
3. Combien de triangles ont exactement deux côtés qui sont des côtés de \(\mathcal{P}\) ? Exactement un ?
4. En déduire que le nombre de triangles dont aucun côté n’est un côté de \(\mathcal{P}\) vaut \(\dfrac{n(n-4)(n-5)}{6}\). Donner sa valeur pour \(n = 8\).

Exercice 11 : Mois de naissance

On admet que les mois de naissance de \(k\) personnes forment une \(k\)-liste d’éléments de l’ensemble des \(12\) mois, toutes les listes étant équiprobables. La probabilité d’un événement est alors le nombre de listes favorables divisé par \(12^k\).

1. On prend \(k = 5\). Combien de listes sont formées de mois deux à deux distincts ?
2. En déduire la probabilité que deux personnes au moins, parmi cinq, soient nées le même mois. On donnera une fraction irréductible et une valeur approchée.
3. Pour \(k \in [\![1, 13]\!]\), on note \(q_k\) la probabilité que les \(k\) mois soient deux à deux distincts. Exprimer \(q_k\) à l’aide d’une factorielle. Que vaut \(q_{13}\) ?
4. Déterminer le plus petit \(k\) pour lequel la probabilité d’une coïncidence dépasse \(\frac{1}{2}\).

Exercice 12 : Solutions entières d’une équation

Soient \(n \in \mathbb{N}\) et \(p \geq\, 1\). On cherche le nombre de \(p\)-uplets \((x_1, \ldots, x_p) \in \mathbb{N}^p\) tels que \(x_1 + \cdots + x_p = n\).

1. À un tel \(p\)-uplet, on associe le mot formé de \(x_1\) étoiles, une barre, \(x_2\) étoiles, une barre, …, une barre, puis \(x_p\) étoiles. Justifier que l’on obtient une bijection vers l’ensemble des mots de \(n + p – 1\) caractères comportant exactement \(p – 1\) barres.
2. En déduire le nombre de solutions dans \(\mathbb{N}^p\).
3. Combien l’équation \(x + y + z = 10\) a-t-elle de solutions dans \(\mathbb{N}^3\) ? dans \((\mathbb{N}^*)^3\) ?
4. De combien de façons peut-on répartir \(10\) pièces de un euro identiques entre trois enfants, chacun recevant au moins une pièce ?

Exercice 13 : Applications croissantes

Soient \(p, n \geq\, 1\). On note \(I_p = [\![1, p]\!]\) et \(I_n = [\![1, n]\!]\).

1. Montrer que l’application \(f \mapsto f(I_p)\) est une bijection de l’ensemble des applications strictement croissantes de \(I_p\) dans \(I_n\) sur l’ensemble des parties à \(p\) éléments de \(I_n\). Combien existe-t-il d’applications strictement croissantes de \(I_p\) dans \(I_n\) ?
2. Soit \(f : I_p \to I_n\) croissante au sens large. On pose \(g(i) = f(i) + i – 1\). Montrer que \(g\) est strictement croissante de \(I_p\) dans \(I_{n+p-1}\), et que \(f \mapsto g\) est une bijection.
3. En déduire le nombre d’applications croissantes au sens large de \(I_p\) dans \(I_n\).
4. Application numérique : \(p = 3\) et \(n = 5\).

Exercice 14 : Formule de Pascal et parties de cardinal pair

Soit \(E\) un ensemble à \(n \geq\, 1\) éléments et \(a\) un élément fixé de \(E\).

1. En distinguant les parties qui contiennent \(a\) et celles qui ne le contiennent pas, démontrer la formule de Pascal \(\binom\,{n}{k} = \binom\,{n-1}{k-1} + \binom\,{n-1}{k}\) pour \(1 \leq\, k \leq\, n\).
2. Pour \(A \subset E\), on pose \(\sigma(A) = A \setminus \{a\}\) si \(a \in A\), et \(\sigma(A) = A \cup \{a\}\) sinon. Montrer que \(\sigma \circ \sigma = \mathrm{id}\), et que \(\sigma\) échange les parties de cardinal pair et celles de cardinal impair.
3. En déduire que \(E\) possède exactement \(2^{n-1}\) parties de cardinal pair, puis que \(\displaystyle\sum_{k=0}^{n} (-1)^k \binom\,{n}{k} = 0\).
4. Combien l’ensemble \([\![1, 10]\!]\) possède-t-il de parties de cardinal pair ? de parties non vides de cardinal pair ?

Exercice 15 : Comité et président

Un club compte \(n \geq\, 2\) membres. On forme des comités, c’est-à-dire des parties non vides du club.

1. En comptant de deux façons les comités de \(k\) membres munis d’un président choisi parmi eux, démontrer que \(k\binom\,{n}{k} = n\binom\,{n-1}{k-1}\) pour \(1 \leq\, k \leq\, n\).
2. En déduire que \(\displaystyle\sum_{k=1}^{n} k\binom\,{n}{k} = n\,2^{n-1}\).
3. De même, en ajoutant un secrétaire distinct du président, démontrer que \(k(k-1)\binom\,{n}{k} = n(n-1)\binom\,{n-2}{k-2}\) pour \(2 \leq\, k \leq\, n\), puis calculer \(\displaystyle\sum_{k=2}^{n} k(k-1)\binom\,{n}{k}\).
4. En déduire une expression factorisée de \(\displaystyle\sum_{k=0}^{n} k^2\binom\,{n}{k}\), et la vérifier pour \(n = 3\).

Exercice 16 : Formule de Vandermonde

Soient \(a, b, n\) des entiers naturels.

1. Une assemblée compte \(a\) femmes et \(b\) hommes. En comptant de deux façons les délégations de \(n\) personnes, démontrer que

\[\sum_{k=0}^{n} \binom\,{a}{k}\binom\,{b}{n-k} = \binom\,{a+b}{n}.\]

2. En déduire que \(\displaystyle\sum_{k=0}^{n} \binom\,{n}{k}^2 = \binom\,{2n}{n}\).
3. Vérifier cette égalité pour \(n = 4\) à l’aide du triangle de Pascal.
4. Retrouver le résultat de la question 2 en comptant les chemins de \((0, 0)\) à \((n, n)\), classés selon le point où ils coupent la droite d’équation \(x + y = n\).

Exercice 17 : Binôme et trinôme par dénombrement

Soit \(n \in \mathbb{N}\).

1. Combien existe-t-il de mots de longueur \(n\) sur l’alphabet \(\{a, b\}\) contenant exactement \(k\) lettres \(a\) ? En développant le produit \((a+b)^n\) sans utiliser la commutativité, retrouver la formule du binôme.
2. Soient \(i, j, k \in \mathbb{N}\) tels que \(i + j + k = n\). Montrer que le nombre de mots de longueur \(n\) sur l’alphabet \(\{x, y, z\}\) contenant exactement \(i\) lettres \(x\), \(j\) lettres \(y\) et \(k\) lettres \(z\) vaut \(\dfrac{n!}{i!\,j!\,k!}\).
3. En déduire le coefficient de \(x^2 y^3 z\) dans le développement de \((x + y + z)^6\).
4. Démontrer que \(\displaystyle\sum_{i+j+k=n} \frac{n!}{i!\,j!\,k!} = 3^n\), la somme portant sur les triplets d’entiers naturels de somme \(n\).

Exercice 18 : Formule de la crosse et sommes de puissances

Soient \(p \leq\, n\) deux entiers naturels.

1. En classant les parties à \(p + 1\) éléments de \([\![1, n+1]\!]\) selon leur plus grand élément, démontrer que

\[\sum_{k=p}^{n} \binom\,{k}{p} = \binom\,{n+1}{p+1}.\]

2. Retrouver la valeur de \(\displaystyle\sum_{k=1}^{n} k\).
3. Vérifier que \(k^2 = 2\binom\,{k}{2} + \binom\,{k}{1}\) pour tout \(k \in \mathbb{N}\). En déduire \(\displaystyle\sum_{k=1}^{n} k^2\).
4. Déterminer des entiers \(\alpha, \beta\) tels que \(k^3 = 6\binom\,{k}{3} + \alpha\binom\,{k}{2} + \beta\binom\,{k}{1}\) pour tout \(k\). En déduire que \(\displaystyle\sum_{k=1}^{n} k^3 = \Big(\frac{n(n+1)}{2}\Big)^2\).

Exercice 19 : Principe des tiroirs

Soit \(n \geq\, 1\) et \(A\) une partie de \([\![1, 2n]\!]\) à \(n + 1\) éléments.

1. En considérant les \(n\) paires \(\{2i – 1, 2i\}\), montrer que \(A\) contient deux entiers consécutifs. En déduire que \(A\) contient deux entiers premiers entre eux.
2. Montrer que tout \(m \in [\![1, 2n]\!]\) s’écrit de façon unique \(m = 2^{r} q\) avec \(r \in \mathbb{N}\) et \(q\) impair. Combien de valeurs peut prendre \(q\) ?
3. En déduire que \(A\) contient deux entiers distincts dont l’un divise l’autre.
4. Montrer que ces deux résultats deviennent faux pour certaines parties à \(n\) éléments.

Exercice 20 : Mots binaires sans deux 1 consécutifs

Pour \(n \geq\, 1\), on note \(u_n\) le nombre de mots de longueur \(n\) sur l’alphabet \(\{0, 1\}\) qui ne contiennent pas deux \(1\) consécutifs.

1. Calculer \(u_1\), \(u_2\) et \(u_3\) en listant les mots.
2. En distinguant selon la première lettre, montrer que \(u_{n+2} = u_{n+1} + u_n\) pour tout \(n \geq\, 1\). En déduire \(u_{10}\).
3. Soit \(k \in \mathbb{N}\). Montrer que le nombre de mots de longueur \(n\) sans deux \(1\) consécutifs et comportant exactement \(k\) lettres \(1\) vaut \(\binom\,{n-k+1}{k}\). On pourra placer d’abord les \(n – k\) zéros.
4. En déduire une expression de \(u_n\) comme somme de coefficients binomiaux, et la vérifier pour \(n = 10\).

Exercice 21 : Problème : surjections et partitions

Pour \(n, p \geq\, 1\), on note \(S(n, p)\) le nombre de surjections de \([\![1, n]\!]\) sur \([\![1, p]\!]\). Ce nombre ne change pas si l’on remplace ces ensembles par des ensembles quelconques à \(n\) et \(p\) éléments.

1. Calculer \(S(n, p)\) lorsque \(p > n\), puis \(S(n, 1)\), \(S(n, n)\) et \(S(n, 2)\).
2. En classant les applications de \([\![1, n]\!]\) dans \([\![1, p]\!]\) selon leur image, démontrer que \(\displaystyle p^n = \sum_{j=1}^{p} \binom\,{p}{j} S(n, j)\).
3. Soient \(n \geq\, 2\) et \(p \geq\, 2\). En étudiant la valeur \(f(n)\) et la restriction de \(f\) à \([\![1, n-1]\!]\), démontrer que \(S(n, p) = p\big(S(n-1, p-1) + S(n-1, p)\big)\).
4. Dresser la table des \(S(n, p)\) pour \(1 \leq\, p \leq\, n \leq\, 5\). Vérifier la formule de la question 2 pour \(n = 4\) et \(p = 3\).
5. Démontrer directement que \(S(n+1, n) = \dfrac{n\,(n+1)!}{2}\), et contrôler avec la table.
6. On range \(5\) boules numérotées dans \(3\) boîtes numérotées, toutes les répartitions étant équiprobables. Quelle est la probabilité qu’aucune boîte ne soit vide ? Combien existe-t-il de partitions de \([\![1, 5]\!]\) en trois parties non vides ?

Le corrigé des exercices

Chaque exercice est corrigé en détail, question par question, sur la page suivante.

Pour aller plus loin en maths sup

• Le cours : dénombrement, cours de maths sup
• À 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é