Chapitres Maths en MPSI, PCSI, MP2I, PTSI

Exercices corrigés sur dénombrement en Maths Sup

Name: Groupe Réussite: Cours particuliers, stages intensifs de révision
Brand: Groupe Réussite
SKU: Cours Particuliers
Rating: 4.9 (1012 reviews)

Résumé de cours Exercices et corrigés

Cours en ligne de Maths en Maths Sup

Plan des exercices de dénombrements

1. Application directe des résultats de cours
2. Un peu plus élaborés, mais pas trop
3. Sans urne et sans carte
4. Des couples de parties de $E$
5. Des formules obtenues par dénombrement
6. Équations entières et suites croissantes
7. Mots de $n$ lettres à partir de $a$ et $b$
8. Un exercice sur les surjections
9. Dénombrement des involutions
10. Mots de Dyck

Dans tous les exercices ne vous contentez pas d’une valeur numérique. Il faut justifier vos résultats.

COURS DE MATHS

Les meilleurs professeurs particuliers

Pour progresser et réussir

Avis Google France ★★★★★ 4,9 sur 5

1. Des dénombrements simples

1. Quel est le nombre de codes d’un antivol à 4 chiffres choisis entre 1 et 5 ?
Même question si les chiffres doivent être distincts .

Correction :

$\ast$ Le nombre de codes d’un antivol à 4 chiffres est le nombre d’applications de $[[1 , 4]]$ dans l’ensemble $[[1 , 5]]$ donc est égal à $5^4 =625$ .

$\ast$ Dans le deuxième cas, c’est le nombre de 4-listes sans répétition des 6 chiffres de 1 à 5 soit $\quad \quad \displaystyle \frac {5!} {(5 - 4)!}= 5\times 4 \times 3 \times 2 = 120$

2. Quel est le nombre de mots de passe de 4 lettres formés uniquement de consonnes ?
Même question si les consonnes doivent être distinctes.

Correction :

$\ast$ Le nombre de mots de passe de 4 lettres est le nombre d’applications de $[[1 , 4]]$ dans l’ensemble des 20 consonnes donc est égal à $\quad _quad \quad 20^ 4 =160\, 000$ .

$\ast$ Dans le deuxième cas, c’est le nombre de 4-listes sans répétition des 20 consonnes soit $\displaystyle \frac {20!} {(20 - 4)!}= 20\times 19 \times 18 \times 17 = 116\,280$ .

3. Quel est le nombre de tiercés (dans l’ordre) que l’on peut jouer dans une course de 20 chevaux ?

Correction : Le nombre de tiercés (dans l’ordre) que l’on peut jouer dans une course de 20 chevaux est le nombre de 3-listes sans répétition des 20 chevaux soit $\quad \quad \quad \quad 20 . 19 . 18 = 6 \, 840$ .

4. Quel est le nombre de façons de choisir un groupes de $k$ élèves dans une classe de $n$ élèves pour faire un exposé ?
a) $\displaystyle \frac {n!} {(n - k)!}$ b) $\displaystyle \frac {n!} {k!}$ c) $\displaystyle \binom {n} {k}$

Correction : Le nombre de façons de choisir un groupe de $k$ élèves dans une classe de $n$ élèves pour faire un exposé est le nombre de parties à $k$ éléments parmi $n$ soit $\displaystyle {\binom {n} {k}}$ .

5. Quel est le nombre de grilles au loto (5 numéros de 1 à 49 et 1 numéro chance de 1 à 10) ?

6. Quel est le nombre de façons de ranger les $n$ éléments d’un ensemble $E\, ?$

7. Quel est le nombre de façons de ranger les $n$ éléments de $[\![1 , n]\!]$ de façon à ce que les éléments 1 à $k$ soient côte à côte.

8. Quel est le nombre d’entiers de $n \geq 3$ chiffres contenant un seul $0$ et un seul $1$ ?

9. Quel est le nombre d’anagrammes du mot « ENTENTE »

10. Combien de mots peut on écrire avec le mot « TOULOUSE » si les consonnes doivent être placées en 1-ère, 4-ème et 7-ème position ?

11. Il y a $n!$ façons de placer $n$ personnes autour d’une table ronde

12. Il y a $\displaystyle \frac {(n!)^2} 2$ manières de placer $n$ couples autour d’une table ronde en alternant un homme et une femme

13. Quel est le nombre $d$ de dominos (2 chiffres de $0$ à $6$ qui peuvent être répétés) ?
Quel est le nombre $t$ de triominos (3 chiffres de $0$ à $5$ qui peuvent être répétés aux sommets d’un triangle équilatéral) ?

2. D’autres dénombrements

Exercice 1
Dans cet exercice, on effectue 3 tirages successifs et sans remise dans un ensemble contenant $b$ boules blanches, $r$ rouges et $v$ vertes.
a) Quel est le nombre de tirages tricolores ?

Correction : Le nombre de façons d’obtenir une boule blanche puis une rouge puis une verte est égal à $b . r . v$ .
Le nombre de façons d’obtenir un tirage tricolore est égal à $T = 3!\, b \,r\, v$ (car on a $3 !$ façons de choisir l’ordre de tirage des trois couleurs).

b) Quel est le nombre de tirages bicolores ?

Correction : $\ast$ Le nombre $M$ de tirages monocolores est égal au nombre de tirages blancs plus le nombre de tirages rouges plus le nombre de tirages verts soit $M = b(b - 1) (b - 2) + r(r - 1)(r - 2)$
$+\, n(n - 1) (n - 2)$ .
$\ast$ Le nombre $S$ de tirages est égal à $S = N (N - 1) (N - 2)$ où $N = b + n + r$ .

$\ast$ On rappelle que le nombre $T$ de tirages tricolores est $T = 6\, b\, r\, v$ .
$\ast$ Le nombre $B$ de tirages bicolores est égal à $B = S - T - M$ .

Exercice 2
On tire 5 cartes d’un jeu de 32 cartes. Quel est le nombre de mains contenant 2 as ?

Correction : On choisit 2 as parmi 4 de $\displaystyle \binom {4} {2} = 6$ façons.
Puis on choisit 3 cartes parmi les $32 - 4 = 28$ cartes sans as de $\displaystyle \binom {28} {3} = 3\, 276$ façons.
Le nombre de mains contenant deux as est égal à $6\, . \, 3276 = 19\, 656$ .

Exercice 3
Quel est le nombre de mains de 4 cartes d’un jeu de 32 cartes contenant 2 rois ou 3 dames ?

Correction :

On ne peut pas avoir deux rois et trois dames en même temps dans une main de 4 cartes.
On note $R$ l’ensemble des mains contenant 2 Rois et $D$ l’ensemble des mains contenant 3 dames.

$\ast$ $\# R = 6 . 14 . 27$
car on choisit 2 rois parmi 4 de $\displaystyle \binom {4} {2} = 6$ façons puis 2 cartes parmi les 28 qui restent de $\displaystyle \binom {28} {2} = 14 . 27$ façons.

$\ast$ $\# D = 4 . 28$
car on choisit 3 dames parmi 4 de $\displaystyle \binom {4} {3} = 4$ façons puis 1 carte parmi les 28 qui restent de $28$ façons.

$\# (R \cup D) = \#R + \#D = 2 \, 380$ car $R \cap D = \varnothing$ .

Aviez -vous pensé à écrire que les deux ensembles sont disjoints ?

Exercice 4
Quel est le nombre de mains de 4 cartes issues d’un jeu de 32 cartes contenant 2 rois ou 3 trèfles ?

Correction :

On peut obtenir une main contenant le roi de trèfle.
Soit $R$ l’ensemble des mains de 4 cartes contenant $2$ rois et $T$ l’ensemble des mains de 4 cartes contenant $3$ trèfles.

$\ast$ $\# R = 6 . 14 . 27$
car on choisit $2$ rois parmi $4$ de $\displaystyle \binom {4} {2} = 6$ façons puis $2$ cartes parmi les $28$ qui restent de $\displaystyle \binom {28} {2} = 14 . 27$ façons.

$\ast$ $\# T = 56 . 24$
car on choisit $3$ trèfles parmi $8$ de $\displaystyle \binom {8} {3} = 56$ façons puis $1$ carte parmi les $24$ qui restent de $24$ façons.

$\ast$ $\# R \cap T = 3 . 21$
C’est l’ensemble des mains contenant le roi de trèfle, un autre roi et $2$ autres trèfles.
On choisit un roi qui n’est pas de trèfle ( $3$ choix), deux trèfles différents du roi de $\displaystyle \binom {7} {2} = 21$ façons.

$\# (R \cup T) = \# R + \# T - \# (R \cap T)$
$\#R = 6 . 14 . 27 + 56 . 24 - 3 . 21 = 3 \,549$ .

Aviez-vous vu que les ensembles ne sont pas disjoints ?

Exercice 5
Quel est le nombre de mains de 5 cartes issues d’un jeu de 32 cartes contenant au moins un as ?

Exercice 6
Quel est le nombre de mains de 5 cartes d’un jeu de 32 contenant au moins 2 trèfles ?

Exercice 7
Quel est le nombre de mains de 5 cartes d’un jeu de 32 cartes contenant 1 roi et au moins un pique.

Exercice 8
On souhaite ranger sur une étagère 4 livres de mathématiques (distincts), 6 livres de physique, et 3 de chimie.
Question 1
De combien de façons peut-on effectuer ce rangement, si les livres doivent être groupés par matières ?

Question 2
De combien de façons peut-on effectuer ce rangement, si seuls les livres de mathématiques doivent être groupés ?

Exercice 9
Quel est le nombre de matrices symétriques d’ordre $n \geq 2$ dont tous les éléments sont dans $[\![1 ,\, p]\!]$ ?

Exercice 10
On dispose de 2 jeux de jetons numérotés de 1 à $n$ , l’un blanc, l’autre noir, on les place dans une urne.

Question 1
On prend au hasard $2\, r$ ( $2 r \leq n$ ) jetons en même temps.
Nombre de tirages donnant des jetons ayant des numéros tous distincts.

Question 2
Avec les hypothèses de la question 1, nombre de façons d’avoir obtenu deux jetons portant le même numéro.

Question 3
On tire maintenant les jetons 2 par 2 sans remise. Nombre de tirages possibles.

Question 4
Dans cette question, on tire les $2\,n$ jetons l’un après l’autre.
Quel est le nombre de tirages donnant une alternance de couleurs ?

3. Sans urne et sans carte

Exercice 1
Soit $n \in \mathbb{N}$ .
Le nombre de solutions dans $\mathbb{N}$ de l’équation $x + y = n$ est égal à ?

Correction : C’est l’ensemble $\quad \quad \quad \{ (k , n - k) \, / \, k\in [[0,\, n]] \}$ .
Il a $n + 1$ éléments.

Question 2
Le nombre de solutions dans $\mathbb{N}$ de l’équation $x + y + z = n$ est égal à $\displaystyle \frac {n(n + 1)} 2$ . Vrai ou Faux ?

Correction : On note $\mathcal{S}$ l’ensemble des solutions entières de cette équation
et si $k \in [[0 , \, n]], \, \mathcal{S}_k$ l’ensemble des solutions entières telles que $z = k$ .
On écrit $\mathcal{S}= \displaystyle \bigcup _{k = 0} ^n \mathcal{S}_k\,$ .
Les ensembles $\mathcal{S}_k$ sont2 à 2 disjoints.

$\mathcal{S}_k$ est en bijection avec $\quad \{ (x , y) \in \mathbb{N}^2 \, / \, x + y = n - k \}$
$\# \mathcal{S}_ k = n - k + 1$ par la question 1.

On écrit $\# \mathcal{S}= \displaystyle \sum_{k = 0} ^n \# \mathcal{S}_k =\sum_{k = 0} ^n ( n - k + 1)$
en posant $p = n - k + 1$ ,
$\# \mathcal{S}= \displaystyle \sum_{p = 1} ^n p = \displaystyle \frac {n(n + 1)} 2$ .

Exercice 2.
Soit $n \geq 3$ .
Question 1
Quel est le nombre de façons de régler au café une somme de $n$ euros en n’utilisant que des pièces de 1 et 2 euros ?

Correction :

On détermine $S = \{(x , \, y) \in \mathbb{N}^2\; /\; 2 \, x + y = n\}$
Si $p = \displaystyle \left \lfloor \frac {n} 2 \right \rfloor$ ,
$S = \{(x , n - 2 \, x ) \, /\,x \in [[0 ,\, p]]\}$
donc $\# S = p + 1 = \displaystyle \left \lfloor \frac {n} 2 \right \rfloor + 1$ .

Question 2
Nombre de façons de payer dans un distributeur une somme de $n$ euros en n’utilisant que des pièces de 1 et 2 euros

Correction : On note $D$ l’ensemble des paiements dans le distributeur pour une somme de $n$ euros.
Soit $p = \displaystyle \left \lfloor \frac {n} 2 \right \rfloor$ . Si $x \in [[0 , \, p]]$ , on introduit $D_x$ l’ensemble des paiements au distributeur où l’on a rentré $x$ pièces de 2 euros et $n - 2 \, x$ pièces de 1 euro.

$D = \displaystyle \bigcup _{x = 0} ^p D_x\,$ .
Ces ensembles étant deux à deux disjoints, $\# D = \displaystyle \sum _{x = 0} ^p \# D_x\,$ .

$\# D_x = \displaystyle \binom {n - x} {x}$
car on choisit les $x$ moments parmi $x + n - 2 \, x = n - x$ où l’on rentre les pièces de $2$ euros.

donc $\# D = \displaystyle \sum _{x = 0} ^{p} \binom {n - x} {x}$ .

Exercice 3
Soit $E$ un ensemble de cardinal $n > 0$ .
La somme des cardinaux des parties de $E$ est égale à

Correction :

Si $k \in [[1,\, n]]$ , on note $\mathcal{P}_k(E)$ l’ensemble des parties de $E$ ayant $k$ éléments.

$\mathcal{P}(E) = \displaystyle \bigcup _{k = 0} ^n \mathcal{P}_k(E)$ .
On a introduit une partition, donc
$N = \displaystyle \sum _ {X \in \mathcal{P}(E)} \# X = \sum _ {k= 0} ^n \sum _{X\in \mathcal{P}_k(E)} \# X$
$N = \displaystyle \sum _ {k= 0} ^n k \times \# \mathcal{P}_k(E) =\sum _ {k= 0} ^n k \, \binom {n} {k}$
$N = \displaystyle \sum _ {k= 1} ^n k \, \binom {n} {k}$ .

Puis $(1 + x) ^n = \displaystyle \sum _ {k = 0} ^n \binom n k \, x ^k$
et par dérivation,
$n (1 + x) ^{n - 1} = \displaystyle \sum _ {k = 1} ^n k \, \binom n k \, x ^{k - 1}$
Si $x = 1$ , $N = n \, 2 ^{n - 1}$ .

Exercice 4
Soit $E$ un ensemble de cardinal $n > 1$ .
Le nombre de partitions de $E$ en 2 parties est égal à

Correction : On remarque que la donnée d’une partie $A$ non vide et différente de $E$ définit une partition $\varphi(A) = \{ A , \overline {A} \}$
et que $\varphi(\overline{A}) = \varphi(A)$ .
Il y a $2 ^{n} - 2$ parties de $E$ non vides et différentes de $E$ .
La même partition étant obtenue 2 fois, le nombre de partitions est égal à $2 ^{n - 1} - 1$ .

4. Couples de parties de $E$

Soit $E$ un ensemble de cardinal $n > 0$ .
Question 1
Le nombre de couples $(X ,\, Y)$ de parties de $E$ est égal à

Correction : C’est $\# \mathcal{P}(E) ^ 2 = \left ( \# \mathcal{P}(E) \right ) ^2 = \left (2 ^n \right ) ^2 = 4 ^n$ .

Question 2
Le nombre de couples $(X ,\, Y)$ de parties de $E$ telles que $X \subset Y$ est égal à ?

Correction : Soit $\mathcal {S} = \{ (X ,\, Y) \, / \, X \subset Y \subset E \}$
et $\forall\, k \in [[0 , \, n]],$
$\mathcal {S}_k = \{ (X ,\, Y) \, / \, X \subset Y \subset E , \# Y = k \}$
$\mathcal{S} = \displaystyle \bigcup _{k = 0} ^n \mathcal {S}_k \,$ , les ensembles étant 2 à 2 disjoints, $\#\, \mathcal{S} = \displaystyle \sum _{k = 0} ^n \# \, \mathcal {S}_k \,$ .

Pour déterminer $\# \, \mathcal {S}_k\,$ ,
$\ast$ On choisit une partie $Y$ de $E$ ayant $k$ éléments de $\displaystyle \binom n k$ façons.
$\ast$ On choisit $X \in \mathcal{P}(Y)$ : il y a $2 ^k$ façons de le faire.
Donc $\# \, \mathcal {S}_k = \displaystyle \binom n k \, 2 ^k$ .

$\#\, \mathcal{S} = \displaystyle \sum _{k = 0} ^n \binom n k \, 2 ^k = (2 + 1)^n$
par le binôme de Newton.

Question 3
Le nombre de couples $(X ,\, Y)$ de parties de $E$ telles que $X \subset Y$ et $X \neq Y$ est égal à $3 ^n - 2 ^n$ Vrai ou Faux ?

Correction : C’est le nombre $N$ de couples $(X ,\, Y)$ de $E$ tels que $X \subset Y$ diminué du nombre de couples $(X ,\, X)$ de $E$ qui est égal à $\# \mathcal{P}(E)$ .

On obtient donc $N - \displaystyle \# \mathcal{P}(E) = 3 ^n - 2 ^n$

Question 4
Le nombre de couples $(X ,\, Y)$ de parties de $E$ telles que $X \cap Y = \varnothing$ est égal à $2 ^n$ Vrai ou Faux ?

Correction : On note $\mathcal{S} '$ cet ensemble et si $k \in [[0,\, n]]\,$ , $\mathcal{S}'_k$ l’ensemble des couples $(X , Y)$ tels que $X \cap Y = \varnothing$ et $\# X = k$ .
alors $\mathcal{S}' = \displaystyle \bigcup _{k = 0} ^n \mathcal {S}'_k\,$ , les ensembles étant 2 à 2 disjoints, $\#\, \mathcal{S}' = \displaystyle \sum _{k = 0} ^n \# \, \mathcal {S}'_k$

Pour déterminer $\# \, \mathcal {S}'_k \,$ ,
$\ast$ on choisit une partie $X$ ayant $k$ éléments de $\displaystyle \binom n k$ façons.
$\ast$ on choisit $Y \in \mathcal{P}(\overline {X} )$ : il y a $2 ^{n - k}$ façons de le faire
donc $\# \, \mathcal {S}'_k = \displaystyle \binom n k \, 2 ^{n - k}$ .

$\#\, \mathcal{S}' = \displaystyle \sum _{k = 0} ^n \binom n k \, 2 ^{n - k} = (2 + 1)^n$
par le binôme de Newton.

à ne pas confondre avec le nombre de couples de parties $(X ,\, Y)$ de $E$ telles que $X \cap Y = \varnothing$ et $X \cup Y = E$ qui est égal à $2 ^n$ car c’est le nombre de couples $(X ,\, \overline{X})$ où $X \in \mathcal{P}(E)$ .

Question 5
Le nombre de couples $(X ,\, Y)$ de parties de $E$ telles que $\# (X \cap Y) = 1$ est égal à ?

Correction : On note $\mathcal{U}$ cet ensemble et si $k \in [[1 ,\, n]]$ , $\mathcal{U}_k$ l’ensemble des couples $(X , Y)$ tels que $\# (X \cap Y) =1$ et $\# X = k$ .
alors $\mathcal{U} = \displaystyle \bigcup _{k = 1} ^n \mathcal {U}_k \,$ , les ensembles étant 2 à 2 disjoints, $\#\;\mathcal{U} = \displaystyle \sum _{k = 0} ^n \#\, \mathcal {U}_k \,$ .

Pour déterminer $\#\,{U}_k \,$ ,
$\ast$ On choisit l’élément $a$ commun à $X$ et $Y$ : $n$ choix
$\ast$ On choisit les $k - 1$ autres éléments de $X$ de $\displaystyle \binom {n - 1} {k - 1}$ façons.
$\ast$ On choisit $Y \setminus \{a \} \in \mathcal{P}(\overline {X} )$ : il y a $2 ^{n - k}$ façons de le faire.
Donc $\#\, \mathcal {U}_k = \displaystyle n \binom {n - 1} {k - 1} \; 2 ^{n - k}$ .

$\#\, \mathcal{U} = \displaystyle \sum _{k = 1} ^n n \,\binom {n - 1} {k - 1}\; 2 ^{n - k}$
en posant $p = k - 1$
$\#\,\mathcal{U} = \displaystyle n \, \sum _{p = 0} ^{n - 1} \binom {n - 1} p \, 2 ^{n - 1 - p}$ .

Par le binôme de Newton,
$\quad \quad \quad \#\,\mathcal{U} = {n} \, (1 + 2) ^{n - 1 }$ .

COURS PARTICULIERS EN LIGNE

Nous avons sélectionné pour vous les meilleurs professeurs particuliers.

POUR ACCÉLÉRER MA PROGRESSION

Avis Google France ★★★★★ 4,9 sur 5

5. Des formules obtenues par des dénombrements

Exercice 1
Si $p \in [\![0,\, n]\!]$ , démontrer que
$\quad \quad \displaystyle \sum _ {k = p} ^n \binom {k} {p} = \binom {n + 1 } {p+ 1}$ .
par un raisonnement de dénombrement

Correction : On note $\mathcal{P}_{p + 1} (n + 1)$ l’ensemble des parties de $[[1 , \, n + 1 ]]$ formées de $p + 1$ éléments.
$\ast$ Pour tout $k \in \mathbb{N}$ , on note $A_k$ l’ensemble des parties de $[[1 , \, n + 1 ]]$ à $p + 1$ éléments dont le maximum est égal à $k$ .
$A_k \neq \varnothing$ ssi $p + 1 \leq k \leq n + 1$ .
$\ast$ L’ensemble des $(A_k)_{p + 1 \, \leq k \, \leq n + 1}$ forme une partition de $\mathcal{P}_{p + 1} (n + 1)$ .
Se donner un élément de $A_k$ revient à choisir une partie de $p$ éléments dans $[[1 ,\, k - 1 ]]$ ce qui se fait de $\displaystyle \binom {k - 1} {p}$ façons et à lui ajouter $k$ .

$\ast$ $\displaystyle \# \mathcal{P}_{p + 1} (n + 1) = \sum _ {k = p + 1} ^ {n + 1} \# A_k\,$ .
$\displaystyle \binom {n+1} {p + 1} = \sum_{k = p + 1} ^ { n + 1} \binom {k -1 }{p } = \sum_{j = p} ^ { n } \binom {j }{p }$
avec $j = k - 1$ .

On peut aussi démontrer cette relation ainsi :
$\displaystyle S_n = \sum _{k = p} ^ n \binom {k}{p}$
Par la formule du triangle de Pascal (valable si $k > p$ ),
$\displaystyle S_n = \binom {p}{p} + \sum _{k = p+1} ^{n} \left ( \binom {k + 1 }{p+ 1 } - \binom {k}{p+ 1 } \right )$
$\displaystyle = 1 + \sum_{k =p+1}^ {n}\binom {k+ 1 }{p+ 1 } - \sum _{ k =p+1}^{n}\binom {k }{p+ 1 }$
avec $i = k + 1$ ,
$\displaystyle = 1+ \sum_{i =p+2}^{ n +1} \binom {i }{p+ 1 } - \sum _{ k =p+1}^{n}\binom {k }{p+ 1 }$
$\displaystyle S_n = 1+ \binom {n + 1 }{p+ 1 } -\binom {p + 1 }{p+ 1 } = \binom {n + 1} {p + 1}$ .

Exercice 2
Soient $a,\, b$ et $n$ trois entiers naturels non nuls avec $n \leq a + b$ .
En utilisant un raisonnement de dénombrement, démontrer la formule de Vandermonde :
$\displaystyle \binom {a+b} {n} = \sum_{ k = \max(0 , n - b)}^{\min(a , \,n)}\binom {a} {k} \, \binom {b} {n- k}$ .

Correction :

Soient $A = [[1 ,\, a]]$ et $B = [[ a + 1 , \, b + a]]$ .
$A$ et $B$ sont disjoints et ont respective- ment $a$ et $b$ éléments. $E = A \cup B = [[1 , \, a + b]]$ .
$\bullet$ On note $\mathcal{P}_n(E)$ l’ensemble des parties de $E$ ayant $n$ éléments. $\quad \quad \quad \displaystyle \# \mathcal{P}_n(E) = \binom {a + b} {n}$ .

$\bullet$ On note $E_k$ l’ensemble des parties de $E$ formées de $k$ éléments dans $A$ et $n - k$ dans $B$ .
L’ensemble $E_k$ est non vide
ssi $0 \leq k \leq a$ et $0 \leq n - k \leq b$
ssi $k \geq 0 \textrm{ et } k \geq n - b , \; k \leq a \textrm{ et } k \leq n$ .
Les ensembles $\quad \left ( E_k \right ) _{\max(0 , \, n - b) \leq k \leq \min(a , \, n)}$
forment une partition de $\mathcal{P}_n(E)$ .
$\#E_k = \displaystyle \binom {a} {k} \, \binom {b} {n - k}$ car on doit choisir $k$ éléments parmi $a$ et $n - k$ éléments parmi $b$ .

$\bullet$ $\displaystyle \# \mathcal{P}_n(E) = \sum _ {k = \max(0 , n - b)} ^{\min(a , n)} \# \,E_k$
soit $\displaystyle \binom {a+b} {n} = \sum_{ k = \max(0 , n -b)}^{\min(a , n)}\binom {a} {k} \, \binom {b} {n- k}$ .

L’utilisation la plus fréquente est dans le cas $a = b = n$ et on obtient
$\quad \quad \quad \displaystyle \binom {2\, n } {n} = \sum_{ k = 0}^{n}\binom {n} {k} ^2$
car $\displaystyle \binom {n} {n - k} = \binom {n} {k}$ .

Exercice 3
Soit $(n ,\, p) \in \mathbb{N}^{*2}$ .

Question 1
Soit $p \in [\![1 , \, n ]\!]$ .
Déterminer le nombre d’applications strictement croissantes de $[\![1 , \, p ]\!]$ dans $[\![1 , \, n ]\!]$ .

Correction : On note $\mathcal {S} _p^n$ l’ensemble des applications strictement croissantes de $[[1 , \, p ]]$ dans $[[1 , \, n ]]$ .
Se donner une application strictement croissante de $[[1 , \, p ]]$ dans $[[1 , \, n ]]$ revient à choisir une partie de $[[1 , \, n ]]$ à $p$ éléments et à la ranger par ordre strictement croissant.
Il y a donc $\displaystyle \binom n p$ applications strictement croissantes de $[[1 , \, p ]]$ dans $[[1 , \, n ]]$ .

Exercice 3 (suite)
Question 2
Déterminer le nombre d’applications strictement croissantes de $[\![1 , \, p ]\!]$ dans $[\![1 , \, n ]\!]$ telles que $f(p) = n$ .

Correction : Pour se donner une telle application, on définit une application strictement croissante de $[[1 , \, p - 1]]$ dans $[[1 ,\, n- 1]]$ , il y a $\displaystyle \binom {n - 1} {p - 1}$ applications de ce type et on impose $f(p) = n$ .

Question 3
Si $i \in [\![1 , \, p ]\!]$ et $k \in [\![1 , \, n ]\!]$ , déterminer le nombre d’applications strictement croissantes de $[\![1 , \, n ]\!]$ dans $[\![1 , \, n ]\!]$ telles que $f(i) = k$

Correction : On note $S_{i ,k}$ l’ensemble des applica- tions vérifiant les conditions de l’énoncé.
Une telle application est entièrement définie par sa restriction à $[[1 ,\, i]]$ et sa restriction à $[[i + 1 , \, n]]$ .

$\ast$ On détermine d’abord le nombre d’applications strictement croissantes de $[[1 , \, i ]]$ dans $[[1 , \, k ]]$ telles que $f(i) = k$ lorsque $i \leq k$ .
En utilisant la question 2, il y en a $\quad \quad \quad \quad \displaystyle \binom {k - 1} {i - 1 }$ .

$\ast$ Puis on détermine le nombre d’applications strictement croissantes de $[[ i + 1, \, p]]$ dans $[[k + 1 , \, n]]$ .
Le problème a une solution ssi l’on peut choisir les $p - i$ images dans un ensemble de $n - k$ éléments donc ssi $p - i \leq n - k$ ssi $i \geq p + k - n$ .
Il y en a $\displaystyle \binom {n - k} {p - i}$ .

Donc si $p + k - n \leq i \leq k$ , $\quad \quad \displaystyle \# S_{i ,k} = \binom {k - 1} {i - 1 } \, \binom {n - k} {p - i}$ .

Question 4
Si $i$ est dans $[\![1 , \, n ]\!]$ , en déduire la valeur de
$\quad \quad \displaystyle \sum _ {k = i}^{n - p + i} \binom {k - 1} {i - 1} \; \binom {n - k} {p - i}$ .

Correction : On écrit $\mathcal {S} _p^n = \displaystyle \bigcup _{i = k - 1} ^{n - p + i} S(i,k)$ .
On a une réunion d’ensembles 2 à 2 disjoints, donc
$\# \mathcal {S} _p^n = \displaystyle \sum _{i = k - 1} ^{n - p + i} \# S(i,k)$
soit $\displaystyle \binom n p = \sum _{i = k - 1} ^{n - p + i} \binom {k - 1} {i - 1} \; \binom {n - k} {p - i}$ .

6. Équations entières et suites croissantes

Exercice 1
Soit $(n , p) \in \mathbb{N}^* \times \mathbb{N}$ .
Question 1
Le nombre de solutions entières de l’équation $x_1 + x_2 + \cdots + x_n = p$ est égal à $\displaystyle \Gamma_n^p = {\binom {n + p - 1} {p}}$ . Vrai ou faux ?

Correction : On peut démontrer ce résultat en considérant le nombre de façons de répartir $p$ objets identiques dans $n$ tiroirs ( $x_k$ est alors le nombre d’objets dans le tiroir $k$ ).
On note les $p$ objets par un $\ast$ et les $n - 1$ séparations entre les différents tiroirs par un | .
Il s’agit donc de placer les $n - 1$ séparations sur $n + p - 1$ places, ce qui se fait en choisissant $n - 1$ places parmi $n + p - 1$ donc il y a $\displaystyle {\binom {n + p - 1} {n-1}}$ choix.
On termine en utilisant :
$\displaystyle {\binom {n + p - 1} {n-1}} = {\binom {n + p - 1} {p}}$ .

Question 2
Le nombre de solutions entières de l’inéquation $\quad \quad \quad x_1 + x_2 + \cdots + x_n \leq p$
est égal à $\displaystyle \binom {n + p } n$ . Vrai ou Faux ?

Correction : $\bullet$ On note $\mathcal{S}_{p}$ l’ensemble des solutions entières de $x_1 + x_2 + \cdots + x_n = p$
et $\mathcal{S}'_{p}$ l’ensemble des solutions entières de $x_1 + x_2 + \cdots + x_n \leq p$ .
Si $p \geq 1$ , il est évident que
$\quad \quad \quad \mathcal{S}'_{p - 1 } \cup \mathcal{S}_{p} = \mathcal{S}'_{p}$
et que les 2 ensembles sont disjoints.
$\quad \quad \quad \# \mathcal{S}'_{p - 1 } + \# \mathcal{S}_{p} = \# \mathcal{S}'_{p}$
si $u _p = \# \mathcal{S}'_{p}\,$ , $u _ p - u_{p - 1} = \# \mathcal{S}_{p}$
par la première question,
$u_p - u_{p - 1} = \displaystyle {\binom {n + p - 1} {p}}$
$\displaystyle u_p - u_{p - 1} = \binom {n + p - 1} {n - 1} \; \; (\ast)$
et $u_ 0 = 1$ .

$\bullet$ Première méthode : par télescopage
$u_ p = \displaystyle \sum _{k = 1} ^p (u_k - u_{k - 1} ) + u_0$
$u_p = \displaystyle \sum _{k = 1} ^p \binom {n + k - 1} {k} + 1$
$u_p = \displaystyle \sum _{k = 0} ^p \binom {n + k - 1} {k}$
$u_p = \displaystyle \sum _{k = 0} ^p \binom {n + k - 1} {n - 1}$

En posant $i = n + k - 1$ ,
$u_p = \displaystyle \sum _{i = n - 1 } ^{n - 1 + p} \binom {i} {n - 1}$
Par application de l’exercice 1 du § I
$u_p = \displaystyle \binom {n - 1 + p + 1 } {n - 1+ 1 } = \binom {n + p} n$ .

$\bullet$ Deuxième méthode.
Si $n \in \mathbb{N}$ est fixé, on note
$\quad \quad \forall\, p \in \mathbb{N}$ , $H_p :\displaystyle u_{p } = \displaystyle \binom {n + p } n$ .

$\ast$ $u_0 = 1 = \displaystyle \binom {n + 0 } n$ .
On a prouvé $H_0\,$ .

$\ast$ On suppose que $H_p$ est vraie.
Par la formule $(\ast)$
$u _ {p + 1} = u_{p } + \displaystyle {\binom {n + p } {p + 1 }}$
$u _ {p + 1} = u_{p } + \displaystyle \binom {n + p} {n - 1}$
Par $H_p$ :
$u_{p + 1} = \displaystyle \binom {n + p } n + \binom {n + p} {n- 1}$
par le triangle de Pascal :
$\displaystyle u_{p+ 1 } = \displaystyle \binom {n + p +1 } n$
ce qui prouve $H_{p + 1}\,$ .

La propriété est démontrée par récurrence.

Exercice 2
Soit $(n , p) \in \mathbb{N}^* \times \mathbb{N}$ ,
$\displaystyle \Gamma_n^p = {\binom {n + p - 1} {p}}$ est le nombre de listes croissantes de $p$ éléments de $[\![1 , n]\!]$ .

Vrai ou Faux ?

Correction : Soit $\mathcal {C} = \left \{(i_1 ,\, \cdots \, , \, i_p) \in\mathbb{N}^{*p} \, / \, \right.$ $\quad \quad \quad \quad \quad \quad \quad \left. i_1 \leq \, \cdots \, \leq i_p \leq n \right \}$ .

$\bullet$ 1ère méthode :
On note $\displaystyle \mathcal{S}' = \left \{ ( x_1\, , \, \cdots\, ,\,x_{n }) \in \mathbb{N} ^n \; / \; \sum _ {i = 1} ^n x_i = p \right \}$ .
Soit $\varphi : \mathcal{S} ' \to \mathcal{C}$
où si $x = ( x_1\, , \, \cdots\, ,\,x_{n }) \in \mathcal{S}'$ , $\varphi(x)$ est le $p$ -uplet tel que les $x_1$ premiers éléments soient des $1$ , les $x_2$ suivants soient des $2$ , … , et les $x_n$ derniers soient des $n$
( $\varphi(x)$ est une suite croissante de $p$ entiers compris entre $1$ et $n$ ).
$\varphi$ est une bijection de $\mathcal{S}'$ sur $\mathcal{C}$ , l’antécédent de $y$ de $\mathcal{C}$ est le $n$ -uplet égal à $( x_1 , \, \cdots\, , \,x_{n })$ où $x_k$ est le nombre de $k$ dans $y$ , avec $x_1 +\, \cdots\, + \,x_{n} = p$ .
Alors $\# \mathcal{C} = \# \mathcal{S}'$ , il suffit d’utiliser le résultat de la question 1 de l’exercice 1, $\# \mathcal{C} = \displaystyle {\binom {n + p - 1} {p}}$ .

$\bullet$ 2ème méthode : On note $\mathcal{S}$ l’ensemble des $(x_1 ,\, \cdots \, \, , \,x_{p + 1}) \in \mathbb{N} ^{p + 1\, }$ tels que $\displaystyle \, \sum _{i = 1} ^{p + 1} x_i = n - 1$ .
Si $i = (i_1 ,\, \cdots \, , \, i_p) \in \mathcal{C}$ , on définit
$\varphi (i) =$ $(i_1 - 1 ,\,i_ 2 - i_1 \, , \cdots \, , \, i_p - i_{p - 1} \, ,$ $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \, n - i_p )$
$\varphi(i) = (x_1 ,\, \cdots \, , \, x_p \, , \,x_{p + 1}) \in \mathbb{N} ^{p + 1}$ avec par télescopage : $\quad \displaystyle \sum _ {i = 1} ^{p + 1} x_i = - 1 + i_p + n - i_p = n - 1$ .
Donc $\varphi(i) \in \mathcal{S}$ .

$\ast$ Il est simple de prouver que $\varphi$ est injective.
$\ast$ Soit $y = (x_1 ,\, \cdots \, , \, x_p \, , \,x_{p + 1}) \in \mathcal{S}$ .
On définit le $p$ -uplet $x$ égal à
$\left (x_1 + 1 ,\, x_1 + x_2 + 1 , \, \cdots \, , \displaystyle \sum _{i = 1} ^p x_i + 1 \right )$
$s$ est une famille croissante de $p$ entiers strictement positifs vérifiant :
$\quad \displaystyle \sum_{k = 1}^{p} x_k + 1 = n - 1 - x_{p + 1} + 1 \leq n$ ,
donc $x \in \mathcal{S}$ et $y = \varphi(x)$ .
L’application $\varphi$ est surjective.

$\varphi$ étant bijective :
$\# \mathcal{C} = \# \mathcal{S} = \displaystyle {\binom {n - 1 + p + 1 - 1} {n - 1}}$
$\# \mathcal{C} = \displaystyle \binom {n + p - 1} {n - 1} = {\binom {n + p - 1} {p} }$ d’après l’exercice 1.

7. Mots de $n$ lettres

Si $n \in \mathbb{N}$ , soit $E_n\,$ l’ensemble des mots formés de $n$ lettres ne contenant que les lettres $a$ et $b$ et tels qu’il n’y ait pas deux $a$ consécutifs.
On note $u_n =\# E_n\,$ .
Question 1.
Déterminer $u_1 \, , \, u_2 \, , \, u_3\,$ .

Correction : $E_1 = \{ a , b \}$
$E_2 = \{ a b \, , \, b b \, , \, b a \}$
et $E_3= \{ a bb \,, \, a b a \, , \, b a b \, , \, bb a \, , \, bb b \}$ ,

donc $u_1 = 2 \, , \, u_2 = 3 \, , \, u_3 = 5$ .

Question 2
Si $n \in \mathbb{N}^*, \, u_{n + 2} = u_{n + 1} + u_n\,$ .

Vrai ou faux ?

Correction : On note $\mathcal{A}$ l’ensemble des éléments de $E_{n + 2}$ qui se terminent par $a$ donc qui se terminent par $b \,a$ et $\mathcal{B}$ l’ensemble des éléments de $E_{n + 2}$ qui se terminent par $b$ .
$E_{n + 2} = \mathcal{A}\cup \mathcal{B}$ , on a ainsi écrit une partition de $E_{n + 2}$ donc
$\quad \quad \quad \# E_{n + 2} =\# \mathcal{A}+ \# \mathcal{B}$ .

$\bullet$ $\varphi : E_n \to \mathcal{A}$ , $\quad \quad x_1 \, x_2 \, \cdots \, x_n \mapsto x_1 \, x_2 \, \cdots \, x_n \, b \, a$
Il est évident que $\varphi$ est une bijection donc $\# \mathcal{A} = \# E_{n} = u_n\,$ .

$\bullet$ $\psi : E_{n + 1} \to \mathcal{B}$ , $\quad \quad x_1 \, x_2 \, \cdots \, x_{n + 1} \mapsto x_1 \, x_2 \, \cdots \, x_{n + 1}\, b$
Il est évident que $\psi$ est une bijection donc $\# \mathcal{B} = \# E_{n+1} = u_{n + 1}\,$ .

On a donc prouvé que $\quad \quad \forall\, n \in \mathbb{N}^*, \; u_{n + 2} = u_{n + 1} + u_n\,$ .

Question 3
Calculer $u_n\,$ .

Correction : On a une suite récurrente linéaire d’ordre 2 d’équation caractéristique :
$x ^2 - x - 1 = (x - r)(x - r') = 0$ avec $r = \displaystyle \frac 1 2 \left ( 1 + \sqrt{5} \right)$ et $r ' = \displaystyle \frac 1 2 \left ( 1 - \sqrt{5} \right)$ .

Il existe donc deux réels $\lambda$ et $\mu$ tels que si $n \in \mathbb{N}^* \, , \, u_n = \lambda \, r ^{n - 1} + \mu \, {r'}^{n - 1}$
: il est plus simple d’utiliser des puissances $n - 1$ que des puissances $n$ dans les calculs qui suivent car on utilise $u_1$ et $u_2$ pour déterminer $\lambda$ et $\mu$ .

On résout donc le système
$\left \{ \begin{matrix} \lambda+ \mu = 2 \\ \lambda \, r + \mu\, r' = 3\end{matrix}\right.$
$\Leftrightarrow$ $\left \{ \begin{matrix} \lambda + \mu = 2 \\ (\lambda+ \mu) + \sqrt{5} \, (\lambda \, - \mu) = 6 \end{matrix} \right.$
$\Leftrightarrow$ $\left \{ \begin{matrix} \lambda + \mu = 2 \\ \sqrt{5} \, (\lambda \, - \mu) = 4 \end{matrix} \right.$
$\Leftrightarrow$ $\lambda = \displaystyle 1 + \frac {2 } { \sqrt{5}}$ et $\mu = \displaystyle 1 - \frac {2} { \sqrt{5}}$ .

Donc $u_n$ est égal à $\displaystyle \left ( 1 + \frac {2 } { \sqrt{5}} \right ) r ^{n - 1} + \left ( 1 - \frac {2 } { \sqrt{5}} \right ) {r'} ^{n - 1}$ .

8. Sur les surjections

Si $N \in \mathbb{N}^*$ , on note $E_N = [\![1 , \, N]\!]$ .
Soient $n$ et $p$ deux entiers naturels non nuls. On note $S(n , \, p)$ le nombre de surjections de $E_n$ dans $E_p\,$ .

Question 1
Donner les valeurs de $S(n,\, n)$ et de $S(n ,\, p)$ si $n < p$ .

Question 2
Calculer $S(n , \, 2)$ .

Question 3
Calculer $S(n , \, 3)$ .

Question 4
Calculer $S(n + 1 , \, n)$ .

Question 5
Si $p \geq 1$ ,
$S(n ,\, p) =$ $\quad \quad p(S(n - 1 ,\, p) + S(n - 1 ,\, p - 1))$ .

Question 6
Montrer que $p ^n =\displaystyle \sum _{k = 1} ^ p \binom {p} {k} S(n ,\, k)$

Question 7
Si $q\leq k \leq p$ ,
$\displaystyle \binom {p} {k} \, \binom {k} {q}$ est égal à $\displaystyle \binom {p} {q} \, \binom {p - q} {k - q}$ .

Question 8
Si $1\leq p \leq n$ ,
$\displaystyle S(n,\, p) = (-1) ^p \sum _ {k = 1} ^p ( - 1) ^k \, \binom {p} {k} \, k ^n$ .

Question 9
Soit $E$ un ensemble de $n\, p$ éléments. Déterminer le nombre de partitions de $E$ en $p$ parties.

9. Dénombrement des involutions

On dit que $f$ est une involution de $E$ lorsque $f \in E ^E$ vérifie $f \circ f = \textrm{Id}_{E}\,$ .
Si $n \in \mathbb{N}^*$ , on note $E_n = [\![1, \, n]\!]$ , $\textrm{Inv}(n)$ l’ensemble des involutions de $E_n$ et $I_n = \# \textrm{Inv}(n)\,$ .
Question 1
Toute involution est une bijection.

Question 2
Déterminer $I_1\, ,\, I_2\, , \, I_3$ et donner la réponse sous la forme x,y,z.

Question 3
Si $n > 0$ , exprimer $I_{n + 2}$ en fonction de $I_{n + 1}$ et $I_{n}$ .

Question 4
La relation de la question 3 est encore vraie si l’on convient que $I_0 = 1$ .

Question 5
Montrer que pour tout $n \in \mathbb{N}$ ,
$\quad \quad I_{2n} =\displaystyle \sum _{k = 0} ^{n } \frac {(2\,n)!} {2 ^{k}\, k! } \binom {2\, n} {2\, k}$
$\quad$ et $I_{2n +1 } =\displaystyle \sum _{k = 0} ^{n } \frac {(2\,k) !} {2 ^{k}\, k! } \binom {2\, n + 1 } {2\, k}$ .

10. Mots de Dyck

On appelle » mot de Dyck » une chaîne de $2 n$ caractères, $n \in \mathbb{N}^*$ , formée de $n$ lettres $A$ et $n$ lettres $B$ , telle que, lorsque l’on dénombre les lettres de gauche à droite, en s’arrêtant à une lettre du mot, le nombre de $A$ soit toujours supérieur ou égal au nombre de $B$ . Ainsi, le seul mot de Dyck de longueur $2$ est : $AB$ . Les mots de Dyck de longueur 4 sont : $AABB$ et $ABAB$ .
$ABAABB$ et $AAABBB$ sont des mots de Dyck, alors que $BA$ et $AABBBA$ n’en sont pas.
Pour tout entier $n \geq 1$ , on désigne par $C_n$ le nombre de mots de Dyck de $2 n$ lettres.

Question 1
Calculer $C_1\, , \, C_2\, , \, C_3 \, , \, C_4\,$ .

Question 2
Montrer que $C_{n} = \displaystyle \frac 1 {n + 1} \, \binom {2 n} {n}$ .

$C_n$ est appelé le $n$ -ième nombre de Catalan.
Question 3 : Une application
Une particule se déplace sur une droite graduée en partant de l’origine et en se déplaçant à chaque minute d’une unité vers la droite ou vers la gauche.
Le nombre de façons de revenir pour la première fois à l’instant $2 n + 2$ en $O$ est égal à $a \, C_{n}\,$

Les questions suivantes sont plus compliquées
Question 4.
Soit $n \in \mathbb{N}^*$ et $\mathcal{D}_{n,n}$ l’ensemble des mots de Dyck des mots de Dyck de longueur $2\,n$ tels que l’on obtienne autant de $A$ que de $B$ pour la première fois au rang $2\, n$ .
Montrer que $\# \, \mathcal{D}_{n , n} = C_{n - 1}\,$ .

Question 5
On pose : $C_0 = 1$ . Montrer que, pour tout entier $n > 1, \displaystyle C_n = \sum _{k = 1 } ^{n - 1} C_{k - 1} \, C_{n - k }$ .

Utilisez ces cours en ligne de mathématiques au programme de MPSI, PCSI et PTSI pour vos révisions et vos entraînements. Chaque cours reprend les notions et les méthodes à connaître parfaitement pour progresser efficacement. Vous pouvez d’ores et déjà avancer dans le programme en révisant les chapitres de fin d’année :

Exercices corrigés sur dénombrement en Maths Sup

Plan des exercices de dénombrements

COURS DE MATHS

Les meilleurs professeurs particuliers

Pour progresser et réussir

1. Des dénombrements simples

2. D’autres dénombrements

3. Sans urne et sans carte

4. Couples de parties de $E$

COURS PARTICULIERS EN LIGNE

Nous avons sélectionné pour vous les meilleurs professeurs particuliers.

POUR ACCÉLÉRER MA PROGRESSION

5. Des formules obtenues par des dénombrements

6. Équations entières et suites croissantes

7. Mots de $n$ lettres

8. Sur les surjections

9. Dénombrement des involutions

10. Mots de Dyck

Contact

Qui sommes-nous ?

Nous rejoindre

Copyright @ GROUPE REUSSITE - Mentions légales