Exercice 1 4436

En écriture binaire, combien de fois utilise-t-on le chiffre « 1 » pour énumérer tous les entiers compris entre $1$ et $1 024$ ?

Exercice 2 4445

Soit $ℛ$ une relation d’équivalence sur un ensemble $E$ de cardinal $n$ . On suppose que $ℛ$ possède $p$ classes d’équivalence et l’on note $q$ le nombre de couples $(x, y) \in E^{2}$ vérifiant $x ℛ y$ . Établir $n^{2} \leq p q$ .

Exercice 3 4439

Soit $E$ un ensemble fini à $n$ éléments. Combien existe-t-il

(a)

de relations binaires sur $E$ ?
(b)

de relations binaires réflexives et symétriques¹¹ 1 Le nombre de relations d’équivalence sur $E$ est l’objet du sujet 4443. sur $E$ ?
(c)

de relations binaires réflexives et antisymétriques sur $E$ ?

Exercice 4 1534

(Nombre de surjections)

Soient $E$ et $F$ deux ensembles finis non vides de cardinaux respectifs $p$ et $n$ . On note $S_{p, n}$ le nombre de surjections de $E$ sur $F$ .

(a)

Déterminer $S_{p,1}$ , $S_{n, n}$ et $S_{p, n}$ lorsque $p < n$ .
(b)

On suppose $p > 1$ , $n > 1$ et l’on introduit $a$ un élément arbitraire de $E$ . En étudiant la restriction d’une surjection au départ de $E ∖ {a}$ , établir

$S_{p, n} = n (S_{p - 1, n} + S_{p - 1, n - 1}) .$
(c)

En déduire que pour tout entier $n \geq 1$ et tout entier $p \geq 1$ ,

$S_{p, n} = \sum_{k = 0}^{n} {(- 1)}^{n - k} (\binom{n}{k}) k^{p} .$

Exercice 5 3985 Correction

On note $𝒮_{n}$ l’ensemble des permutations de $⟦ 1; n ⟧$ et $𝒮_{n} (k)$ le sous-ensemble de $𝒮_{n}$ constitué des permutations possédant exactement $k \in ⟦ 0; n ⟧$ points fixes. Enfin, on pose

s_{n} (k) = Card (𝒮_{n} (k)) .

(a)

Calculer

$\sum_{k = 0}^{n} s_{n} (k) .$
(b)

Soient $n, k \geq 1$ . En calculant de deux façons le nombre de couples $(s, x)$ constitués de $s \in 𝒮_{n} (k)$ et $x$ point fixe de $s$ , établir

$k s_{n} (k) = n s_{n - 1} (k - 1) .$
(c)

En déduire

$s_{n} (k) = (\binom{n}{k}) s_{n - k} (0) .$
(d)

Retrouver directement le résultat précédent.

Solution

(a)

La somme étudiée dénombre les permutations de $⟦ 1; n ⟧$ selon leur nombre de points fixes

$\sum_{k = 0}^{n} s_{n} (k) = Card (𝒮_{n}) = n! .$
(b)

Pour chaque permutation de $s$ de $𝒮_{n} (k)$ il y a $k$ points fixes $x$ possibles. Le nombre de couples cherché est donc $k s_{n} (k)$ .
Pour chaque $x \in ⟦ 1; n ⟧$ , une permutation possédant $k$ points fixes (dont $x$ ) est entièrement déterminée par sa restriction à $⟦ 1; n ⟧ ∖ {x}$ qui est une permutation à $k - 1$ points fixes. Ainsi, le nombre de couples cherché est aussi $n s_{n - 1} (k - 1)$ .
(c)

En itérant la formule ci-dessus obtenue

$s_{n} (k) = \frac{n (n - 1) \dots (n - k + 1)}{k (k - 1) \dots 1} s_{n - k} (0) = (\binom{n}{k}) s_{n - k} (0) .$
(d)

Pour déterminer une permutation élément de $𝒮_{n} (k)$ , on choisit l’ensemble de ses $k$ points fixes (il y a $(\binom{n}{k})$ possibilités) et l’on construit ses valeurs sur le complémentaire de l’ensemble des points fixes à partir d’une permutation de $n - k$ éléments sans points fixes (il y a $s_{n - k} (0)$ possibilités). Au total, il y a

$(\binom{n}{k}) s_{n - k} (0)$

applications de la forme voulue.

Exercice 6 4156 CCINP (MP)Correction

On considère une matrice $3 \times 3$ composée de $9$ jetons numérotés de $1$ à $9$ .

On cherche à déterminer la probabilité $p$ pour que le déterminant de la matrice soit un entier impair.

(a)

Soit $A = (a_{i, j}) \in ℳ_{n} (ℤ)$ . Montrer que la classe de congruence du déterminant de $A$ modulo $2$ est égale à la classe du déterminant de la matrice dont les coefficients sont les restes $r_{i, j}$ de la division euclidienne de $a_{i, j}$ par $2$ .
(b)

On note $ℳ$ l’ensemble des matrices carrées d’ordre $3$ composées des $9$ jetons. Déterminer $Card (ℳ)$ .

On définit $Ω = {M \in ℳ | \det (M) impair}$ et $Δ$ l’ensemble des matrices carrées d’ordre $3$ dont cinq coefficients sont égaux à $1$ , quatre sont nuls et de déterminant impair.

(c)

Donner une relation entre $Card (Ω)$ et $Card (Δ)$ .
(d)

On considère une matrice de $Δ$ dont une colonne possède trois coefficients égaux à $1$ .

Donner le nombre $K_{1}$ de ces matrices.

On considère une matrice de $Δ$ dont deux colonnes possèdent exactement un coefficient nul.

Déterminer le nombre $K_{2}$ de ces matrices.
(e)

Calculer $Card (Δ)$ et en déduire $Card (Ω)$ .
(f)

Déterminer la probabilité $p$ .

Solution

(a)

Le déterminant de $A$ se calcule par une formule compatible avec le calcul en congruence modulo 2.
(b)

Répartir les jetons dans la matrice revient à déterminer une bijection de $⟦ 1; 9 ⟧$ vers lui-même. On en déduit $Card (ℳ) = 9! = 362 880$ .
(c)

À chaque matrice de $Ω$ on fait correspondre une matrice de $Δ$ par calcul des restes $r_{i, j}$ des divisions euclidiennes modulo $2$ . Pour une matrice de $Ω$ , si l’on permute les jetons impairs d’une part, et les jetons pairs d’autre part, la matrice de $Δ$ obtenue à la fin est la même. On en déduit

$Card (Ω) = 5! 4! Card (Δ) .$
(d)

Formons une matrice de $Δ$ dont une colonne possède trois coefficients égaux à $1$ . On choisit cette colonne et il reste deux $1$ à positionner. Ceux-ci ne peuvent figurer sur la même colonne car on obtient sinon un déterminant nul. Ils ne peuvent figurer sur la même ligne pour la même raison. S’ils ne figurent ni sur la même ligne, ni sur la même colonne, la matrice est convenable. On en déduit

$K_{1} = 3 \times 3 \times 2 .$

On choisit la colonne comportant un $1$ et deux $0$ , les deux autres colonnes comportant un $0$ et deux $1$ , puis on positionne le $1$ dans la première colonne et les deux zéros dans les deux autres. Pour que la matrice obtenue soit de déterminant impair, il faut et il suffit que ces deux derniers zéros ne soient pas choisis sur la même ligne. On en déduit

$K_{2} = 3 \times 3 \times 3 \times 2 .$
(e)

Si une matrice de $Δ$ possède une colonne dont trois coefficients sont égaux à $1$ , elle ne possède pas deux colonnes possédant exactement un coefficient nul. Aussi, si une matrice de $Δ$ ne possède pas de colonne dont trois coefficients sont égaux à $1$ , elle possède deux colonnes possédant exactement un coefficient nul.

$Card (Δ) = K_{1} + K_{2} = 72 et Card (Ω) = 207 360 .$
(f)

$p = 4 / 7$ .

Exercice 7 4442

(Nombres de Catalan)

Soient $n$ et $p$ deux entiers naturels non nuls.

On appelle chemin monotone, tout déplacement sur une grille de coordonnées entières obtenu en partant de la case $(0,0)$ et en se déplaçant successivement d’une unité vers la droite ou d’une unité vers le haut.

(a)

Combien existe-t-il de chemins monotones rejoignant la case $(n, p)$ ?

On s’intéresse désormais aux chemins monotones rejoignant la case $(n, n)$ . On dit qu’un tel chemin est sous-diagonal si les cases $(x, y)$ qu’il emprunte vérifient la condition $y \leq x$ .

(b)

On considère un chemin qui n’est pas sous-diagonal et on lui associe un nouveau chemin déterminé en changeant les mouvements vers la droite par des mouvements vers le haut, et inversement, dès son premier franchissement¹¹ 1 Ce premier franchissement est nécessairement dirigé vers le haut et peut éventuellement avoir lieu dès le premier déplacement. de la diagonale.

Quelle nouvelle case rejoint ce chemin?
(c)

Combien existe-t-il de chemins sous-diagonaux rejoignant la case $(n, n)$ ?

Exercice 8 4443

(Nombres de Bell)

On appelle partition d’un ensemble $E$ , tout ensemble constitué de parties deux à deux disjointes, non vides et de réunion égale à $E$ . On note $B_{n}$ le nombre de partitions¹¹ 1 Une relation d’équivalence est caractérisée pas ses classes d’équivalences qui constituent une partition de l’ensemble: $B_{n}$ détermine le nombre de relations d’équivalence sur un ensemble à $n$ éléments. d’un ensemble fini à $n \in ℕ^{*}$ éléments et l’on pose $B_{0} = 1$ . Établir que pour tout entier naturel $n$ ,

B_{n + 1} = \sum_{k = 0}^{n} (\binom{n}{k}) B_{k} .

Exercice 9 4444

(Nombre de dérangements)

Un dérangement sur un ensemble $E$ est une permutation $σ$ de $E$ vérifiant $σ (x) \neq x$ pour tout $x \in E$ . On note $D_{n}$ le nombre de dérangements existant sur un ensemble à $n \in ℕ^{*}$ éléments.

(a)

Établir $D_{n + 1} = n (D_{n} + D_{n - 1})$ pour tout $n \geq 2$ .
(b)

En déduire $D_{n} = n D_{n - 1} + {(- 1)}^{n}$ pour tout $n \geq 2$ .
(c)

Conclure

$D_{n} = n! \sum_{k = 0}^{n} \frac{{(- 1)}^{k}}{k!} pour tout n \geq 1 .$

Exercice 10 5418 MINES (MP)Correction

Soit $n \in ℕ^{*}$ . Déterminer le nombre moyen de points fixes d’une permutation de l’ensemble $⟦ 1; n ⟧$ .

Solution

Notons $𝒮_{n}$ l’ensemble des permutations de $⟦ 1; n ⟧$ . On sait

Card 𝒮_{n} = n! .

Pour $σ \in 𝒮_{n}$ , notons $N (σ)$ le nombre de points fixes de $σ$

N (σ) = Card {i \in ⟦ 1; n ⟧ | σ (i) = i} .

Le nombre moyen de points fixes d’une permutation de $⟦ 1; n ⟧$ est

M = \frac{1}{n!} \sum_{σ \in 𝒮_{n}} N (σ) .

Réorganisons le calcul de cette somme en introduisant les couples $(σ, i)$ formés par $σ \in 𝒮_{n}$ et $i \in ⟦ 1; n ⟧$ . Pour un tel couple, posons

δ (σ, i) = {\begin{matrix} 1 & si σ (i) = i \\ 0 & si σ (i) \neq i . \end{matrix}

On remarque

N (σ) = \sum_{i = 1}^{n} δ (σ, i)

et alors

\sum_{σ \in 𝒮_{n}} N (σ) = \sum_{σ \in 𝒮_{n}} (\sum_{i = 1}^{n} δ (σ, i)) .

On réorganise le calcul de la somme

\sum_{σ \in 𝒮_{n}} N (σ) = \sum_{i = 1}^{n} (\sum_{σ \in 𝒮_{n}} δ (σ, i))

avec

\sum_{σ \in 𝒮_{n}} δ (σ, i) = Card {σ \in 𝒮_{n} | σ (i) = i} .

Or, pour $i \in ⟦ 1; n ⟧$ , une permutation $σ$ qui fixe $i$ peut s’identifier à une permutation de $⟦ 1; n ⟧ ∖ {i}$ , il y en a exactement $(n - 1)!$ . On peut alors achever le calcul

N (σ) = \sum_{i = 1}^{n} (n - 1)! = n \cdot (n - 1)! = n!

puis

M = 1 .

Exercice 11 4446

(Formule d’inversion de Pascal)

Soient $n$ et $p$ des entiers naturels.

(a)

Pour $k, ℓ \in ℕ$ tels que $ℓ \leq k \leq n$ , comparer $(\binom{n}{k}) (\binom{k}{ℓ})$ et $(\binom{n}{ℓ}) (\binom{n - ℓ}{k - ℓ})$ .
(b)

Soient ${(u_{n})}_{n \in ℕ}$ une suite de nombres réels et ${(v_{k})}_{k \in ℕ}$ la suite déterminée par

$v_{k} = \sum_{ℓ = 0}^{k} (\binom{k}{ℓ}) u_{ℓ} pour tout k \in ℕ .$

Établir la formule d’inversion

$u_{n} = \sum_{k = 0}^{n} {(- 1)}^{n - k} (\binom{n}{k}) v_{k} pour tout n \in ℕ .$
(c)

Application : On note $S_{p, n}$ le nombre de surjections d’un ensemble $E$ à $p$ éléments sur un ensemble $F$ à $n$ éléments. Déterminer une expression de $S_{p, n}$ en observant

$n^{p} = \sum_{k = 0}^{n} (\binom{n}{k}) S_{p, k} .$
(d)

Application : On note $D_{n}$ le nombre de dérangements¹¹ 1 Voir le sujet 4444. sur un ensemble à $n$ éléments. Déterminer une expression de $D_{n}$ en commençant par observer

$n! = \sum_{k = 0}^{n} (\binom{n}{k}) D_{k} .$

Exercice 12 3934 Correction

Soit $n \in ℕ^{*}$ . On note $X$ l’ensemble de suites $(x_{1}, \dots, x_{n})$ avec

\forall k \in {1, \dots, n}, x_{k} = 1 ou - 1 .

À chaque suite $x = (x_{1}, \dots, x_{n})$ élément de $X$ on associe la suite $(s_{0}, s_{1}, \dots, s_{n})$ avec

s_{0} \in ℤ et s_{k} = s_{k - 1} + x_{k} pour k \in {1, \dots, n} .

Celle-ci détermine une ligne brisée déterminée par les points de coordonnées $(k, s_{k})$ comme illustrée ci-dessous

Cette ligne brisée définit un chemin joignant $(0, s_{0})$ à $(n, s_{n})$ .

(a)

On note $p$ le nombre de 1 dans la suite $x = (x_{1}, \dots, x_{n}) \in X$ . Exprimer en fonction de $n$ , $p$ et $s_{0}$ la valeur de $s_{n}$ .
(b)

Étant donnée $m \in ℕ$ , combien existe-t-il de chemin $s_{n} = m$ ?
(c)

On suppose $s_{0} \in ℕ$ . En exploitant la figure ci-dessous

expliquer pourquoi il y a autant de chemins joignant $(0, - s_{0})$ à $(n, m)$ que de chemins joignant $(0, s_{0})$ à $(n, m)$ et coupant l’axe des abscisses.
(d)

En déduire le nombre de chemins joignant $(0,1)$ à $(n, m)$ dont tous les points sont d’ordonnées strictement positives.

Solution

(a)

Le nombre de $- 1$ est de $n - p$ et donc $s_{n} = s_{0} + p - (n - p) = s_{0} + 2 p - n$ .
(b)

Si $m - (s_{0} + n)$ n’est pas un nombre pair, il n’y a pas de chemin solutions.
Sinon, on introduit $p \in ℤ$ pour lequel $m - s_{0} + n = 2 p$ .
Si $p < 0$ ou $p > n$ , on ne pourra trouver de chemin solutions.
Si $0 \leq p \leq n$ , chemins solutions correspondent aux suites $x$ pour lesquels on positionne $p$ termes 1 et les autres égaux à $- 1$ . Il y a $(\binom{n}{p})$ positions possibles pour les termes 1 et autant de chemins solutions.
(c)

Tout chemin joignant $(0, s_{0})$ à $(n, m)$ et coupant l’axe des abscisses peut être associé de façon bijective à un chemin joignant $(0, - s_{0})$ à $(n, m)$ , il suffit pour cela de passer à l’opposer les termes $x_{1}, x_{2}, \dots$ jusqu’au premier pour lequel $s_{0} + x_{1} + \dots + x_{k} = 0$ et ne pas modifier les autres comme dans la figure proposé (ce résultat est connu sous le nom de principe de réflexion).
(d)

Si $m - 1 + n$ est impair, il n’y a aucun chemins possible d’aucune sorte.
Sinon, on peut écrire $m - 1 + n = 2 p$ avec $p \in ℤ$ et il y a alors $(\binom{n}{p})$ chemins possibles (ce nombre étant nul lorsque $p < 0$ ou $p > n$ ).
Parmi ceux-ci, on retire ceux coupant l’axe abscisse qui par l’étude au dessus sont au nombre de $(\binom{n}{p + 1})$ .
Finalement, il y a

$(\binom{n}{p}) - (\binom{n}{p + 1})$

chemins solutions

[<] Dénombrements élémentaires [>] Composition d'un entier

Édité le 29-08-2023

Dénombrements avancés