Exercice 1 3956 Correction

Cinq cartes d’un jeu de cinquante-deux cartes sont servies à un joueur de Poker.

(a)

Combien y a-t-il de mains possibles?
(b)

Combien de ces mains comportent exactement un As?
(c)

Combien de ces mains ne comportent aucun As?
(d)

Combien comportent au moins un As?

Solution

(a)

Une main se comprend comme une partie à 5 éléments d’un ensemble à 52 éléments.

$(\binom{52}{5}) .$
(b)

On choisit l’As et les cartes le complétant

$(\binom{4}{1}) \times (\binom{48}{4}) .$
(c)

On choisit uniquement des cartes qui ne sont pas des As

$(\binom{48}{5}) .$
(d)

Par complément

$(\binom{52}{5}) - (\binom{48}{5}) .$

Exercice 2 4433

Cinq cartes d’un jeu de trente-deux cartes constituent la main d’un joueur.

(a)

Combien de mains comportent un as ?
(b)

Combien de mains comportent au moins un as ?
(c)

Combien de mains comportent un as et un cœur ?
(d)

Combien de mains comportent un as ou un cœur ?
(e)

Combien de mains comportent au moins un as et au moins un cœur ?

Exercice 3 4432

Une urne contient $n$ jetons numérotés de $1$ à $n$ (avec $n \geq 2$ ).

(a)

On tire successivement et avec remise $2$ jetons dans l’urne. Combien de tirages sont possibles? Pour combien d’entre eux le second jeton est-il d’une valeur au moins égale au premier?
(b)

Mêmes questions pour un tirage sans remise.
(c)

On tire simultanément $2$ jetons dans l’urne. Combien de tirages sont possibles? Pour combien d’entre eux la somme des valeurs vaut $n$ ?

Exercice 4 4431

Soient $n, p \in ℕ$ . Combien existe-t-il de couples $(x, y) \in {⟦ - p; n ⟧}^{2}$ vérifiant $x y \geq 0$ ?

Exercice 5 5728 Correction

Soit $n \in ℕ^{*}$ .

(a)

Combien existe-t-il de surjections de ${1, \dots, n}$ sur ${1}$ ?
(b)

Combien existe-t-il de surjections de ${1, \dots, n}$ sur ${1,2}$ ?
(c)

Combien existe-t-il de surjections de ${1, \dots, n}$ sur ${1,2,3}$ ?

Solution

(a)

Il existe une seule application de ${1, \dots, n}$ sur ${1}$ , c’est l’application constante égale à $1$ et celle-ci est surjective. Il existe donc une surjection de ${1, \dots, n}$ sur ${1}$ .
(b)

Il existe $2^{n}$ applications de ${1, \dots, n}$ sur ${1,2}$ . Parmi, celles-ci, il y a deux applications constantes et les autres sont toutes surjectives. Il y a donc $2^{n} - 2$ surjections de ${1, \dots, n}$ sur ${1,2}$ .
(c)

Il existe $3^{n}$ applications de ${1, \dots, n}$ sur ${1,2,3}$ . Parmi celles-ci, il y a trois applications constantes qui ne sont pas surjectives. Dénombrons les applications qui prennent exactement $2$ valeurs dans ${1,2,3}$ . On commence par déterminer ces valeurs: cela fait $(\binom{2}{3}) = 3$ choix. Une fois celles-ci déterminée, on dénombre les surjections de ${1, \dots, n}$ sur ces deux valeurs: cela fait $2^{n} - 2$ choix. Il y a donc $3 \cdot (2^{n} - 2)$ applications qui prennent exactement $2$ valeurs. Parmi les applications de ${1, \dots, n}$ vers ${1,2,3}$ , toutes les autres sont surjectives. Au final, il y a

$3^{n} - 3 \cdot (2^{n} - 2) - 3 = 3^{n} - 3 \cdot 2^{n} + 3$

applications surjectives de ${1, \dots, n}$ sur ${1,2,3}$ .

Exercice 6 5727 Correction

Soit $n \in ℕ^{*}$ .

(a)

Combien existe-t-il de surjections de ${1, \dots, n}$ sur lui-même?

On souhaite déterminer le nombre de surjections de ${1, \dots, n + 1}$ sur ${1, \dots, n}$ .

(b)

Justifier qu’une application de ${1, \dots, n + 1}$ vers ${1, \dots, n}$ est surjective si, et seulement si, il existe un et un seul élément de ${1, \dots, n}$ qui possède deux antécédents alors que les autres possèdent tous un antécédent et un seul.
(c)

En déduire le nombre de surjections de ${1, \dots, n + 1}$ sur ${1, \dots, n}$ .
(d)

Combien y a-t-il de surjections de ${1, \dots, n + 2}$ sur ${1, \dots, n}$ ?

Solution

(a)

Les surjections de $⟦ 1; n ⟧$ sur lui-même se confondent avec les permutations de ${1, \dots, n}$ . Il y en a exactement $n!$ .
(b)

Soit $f$ une application de ${1, \dots, n + 1}$ vers ${1, \dots, n}$ . Pour $k = 1, \dots, n$ , notons $x_{k}$ le nombre d’antécédents de $k$ par $f$ . On a $x_{1} + \dots x_{n} = n + 1$ avec $x_{1}, \dots, x_{n} \in ℕ$ .

Si l’application $f$ est surjective, chaque élément de ${1, \dots, n}$ possède au moins un antécédent et donc $x_{k} \geq 1$ pour tout $k = 1, \dots, n$ . Dans la somme $x_{1} + \dots x_{n}$ il y a alors une fois la valeur $2$ et $n - 1$ fois la valeur $1$ .

Inversement, s’il existe un élément de ${1, \dots, n}$ qui possède deux antécédents et que les autres possèdent tous un antécédent, alors chaque élément de ${1, \dots, n}$ possède au moins un antécédent et l’application $f$ est surjective.
(c)

Pour construire une surjection ${1, \dots, n + 1}$ sur ${1, \dots, n}$ , on choisit l’élément $y$ de ${1, \dots, n}$ possédant deux antécédents ( $n$ choix), on détermine ses deux antécédents $x_{1}$ et $x_{2}$ ( $(\binom{n + 1}{2})$ choix) et enfin on construit une bijection de l’ensemble ${1, \dots, n + 1} ∖ {x_{1}, x_{2}}$ vers ${1, \dots, n} ∖ {y}$ ( $(n - 1)!$ choix). Au total, il y a

$n (\binom{n + 1}{2}) (n - 1)! = \frac{n (n + 1)!}{2}$

surjections de ${1, \dots, n + 1}$ sur ${1, \dots, n}$ .
(d)

Pour une surjection de ${1, \dots, n + 2}$ sur ${1, \dots, n}$ , il peut y avoir $1$ élément de ${1, \dots, n}$ possédant $3$ antécédents ou $2$ éléments possédant chacun $2$ antécédents. En suivant ce principe, on dénombre

$n (\binom{n + 2}{3}) (n - 1)! + (\binom{n}{2}) (\binom{n + 2}{2}) (\binom{n}{2}) (n - 2)! = \frac{n (3 n + 1) (n + 2)!}{24}$

surjections de ${1, \dots, n + 2}$ sur ${1, \dots, n}$ .

Exercice 7 5731 Correction

Soit $n \in ℕ^{*}$ .

De combien de façons peut-on regrouper $2 n$ individus par paires?

Solution

Notons $m_{n}$ le nombre recherché.

Considérons $2 n$ individus que l’on numérote de $1$ à $2 n$ . On choisit avec qui on apparie l’individu numéro $1$ : il y a $2 n - 1$ choix possibles. Une fois ce choix effectué, il reste $2 n - 2$ individus à apparier, il y a $m_{n - 1}$ choix possibles. On en déduit la relation de récurrence

m_{n} = (2 n - 1) m_{n - 1} .

Sachant $m_{1} = 1$ , on conclut

m_{n} = (2 n - 1) \times (2 n - 3) \times \dots \times 1 = \frac{(2 n)!}{2^{n} n!} .

[<] Listes et combinaisons [>] Dénombrements avancés

Édité le 29-08-2023

Dénombrements élémentaires