Exercice 1 1527

Soient $A$ , $B$ et $C$ trois parties d’un ensemble fini $E$ . Exprimer $Card (A \cup B \cup C)$ en fonction des cardinaux de $A$ , $B$ , $C$ , $A \cap B$ , $B \cap C$ , $C \cap A$ et $A \cap B \cap C$ .

Exercice 2 1526

Soit $f : E \to F$ une application au départ d’un ensemble fini non vide $E$ et à valeurs dans un ensemble $F$ . Montrer

f est injective \Leftrightarrow Card (f (E)) = Card (E) .

Exercice 3 1528 Correction

Soient $A$ et $B$ deux parties de $E$ et $F$ .
Étant donnée une application $f : E \to F$ , est-il vrai que:

(a)

Si $A$ est une partie finie de $E$ alors $f (A)$ est une partie finie de $F$ .
(b)

Si $f (A)$ est une partie finie de $F$ alors $A$ est une partie finie de $E$ .
(c)

Si $B$ est une partie finie de $F$ alors $f^{- 1} (B)$ est une partie finie de $E$ .
(d)

Si $f^{- 1} (B)$ est une partie finie de $E$ alors $B$ est une partie finie de $F$ ?

Solution

(a)

oui, car si $A = {x_{1}, \dots, x_{n}}$ alors $f (A) = {f (x_{1}), \dots, f (x_{n})}$ est fini.
(b)

non, il suffit de considérer une fonction constante définie sur un ensemble infini.
(c)

non, il suffit de considérer une fonction constante définie sur un ensemble infini.
(d)

non, il suffit de considérer une partie $B$ formée par une infinité de valeurs non prises par $f$ .

Exercice 4 2362 CENTRALE (MP)

Soit $E$ un ensemble fini de cardinal $n \in ℕ$ . Calculer:

(a)

$\sum_{X \subset E} Card (X)$
(b)

$\sum_{X, Y \subset E} Card (X \cap Y)$
(c)

$\sum_{X, Y \subset E} Card (X \cup Y)$ .

Exercice 5 4441

Soit $E$ un ensemble à $n$ éléments avec $n \geq 2$ . Combien existe-t-il de paires ${X, Y}$ constituées de parties de $E$ non vides et disjointes?

Exercice 6 3044 X (MP)

Montrer qu’un ensemble $E$ est infini si, et seulement si, pour toute application $f : E \to E$ , il existe une partie $A$ non vide et distincte de $E$ telle que $f (A) \subset A$ .

Exercice 7 5698 Correction

(Distance de Jaccard)

Soit $Ω$ un ensemble fini et non vide. On note $𝒫^{*}$ l’ensemble des parties non vides de $Ω$ et l’on pose, pour $A, B \in 𝒫^{*}$ ,

d (A, B) = 1 - \frac{Card (A \cap B)}{Card (A \cup B)} .

(a)

Vérifier

$\forall A, B \in 𝒫^{*}, d (A, B) = 0 \Leftrightarrow A = B .$
(b)

Justifier

$\forall A, B, C \in 𝒫^{*}, d (A, B) ⩽ d (A, C) + d (C, B) .$

On pourra commencer par le cas $C \subset A \cup B$ .

Solution

(a)

Soient $A, B \in 𝒫^{*}$ .

$(⟸)$ Si $A = B$ alors $A \cap B = A \cup B$ et donc $d (A, B) = 1 - 1 = 0$ .

$(⟹)$ Si $d (A, B) = 0$ alors $Card (A \cap B) = Card (A \cup B)$ . Or $A \cap B \subset A \cup B$ . Par inclusion et égalité des cardinaux, il vient $A \cap B = A \cup B$ . On en déduit $A = B$ assez immédiatement.
(b)

Soient $A, B, C \in 𝒫^{*}$ .

Cas: $C \subset A \cup B$ .

On a $A \cup C \subset A \cup B$ donc $Card (A \cup C) ⩽ Card (A \cup B)$ et alors

$d (A, C)$ $= 1 - \frac{Card (A \cap C)}{Card (A \cup C)} = \frac{Card (A \cup C) - Card (A \cap C)}{Card (A \cup C)}$

$⩾ \frac{Card (A \cup C) - Card (A \cap C)}{Card (A \cup B)} .$

De même,

$d (C, B) ⩾ \frac{Card (B \cup C) - Card (B \cap C)}{Card (A \cup B)}$

et donc

$d (A, C) + d (C, B) ⩾ \frac{Card (A \cup C) + Card (B \cup C) - Card (A \cap C) - Card (B \cap C)}{Card (A \cup B)} .$

Pour obtenir l’inégalité voulue, il suffit alors de vérifier

$Card (A \cup C) + Card (B \cup C)$ $- Card (A \cap C) - Card (B \cap C)$ ( $*$ )

$⩾ Card (A \cup B) - Card (A \cap B) .$

Pour cela on introduit

$a$ $= Card (A ∖ (B \cup C)),$ $b$ $= Card (B ∖ (A \cup C)),$ $c$ $= Card (A \cap B \cap C)$

$α$ $= Card (C ∖ A),$ $β$ $= Card (C ∖ B),$ $γ$ $= Card (C ∖ (A \cap B))$

On a

$Card (A \cup C)$ $= a + α + β + γ + c$ $Card (A \cap C)$ $= β + c$

$Card (B \cup C)$ $= b + α + β + γ + c$ $Card (B \cap C)$ $= α + c$

$Card (A \cup B)$ $= a + α + β + γ + c + b$ $Card (A \cap B)$ $= γ + c$

et l’inégalité ( $*$ ‣ (b)) se relit

$(a + α + β + γ + c) + (b + α + β + γ + c)$ $- (β + c) - (α + c)$

$⩾ (a + α + β + γ + c + b) - (γ + c) .$

Après simplification, cela revient à $2 γ ⩾ 0$ ce qui est vraie.

Ainsi, l’inégalité $d (A, B) ⩽ d (A, C) + d (C, B)$ est établie lorsque $C \subset A \cup B$ .

Cas général:

Posons $D = (A \cup B) \cap C$ de sorte que $D \subset A \cup B$ . On sait alors

$d (A, B) ⩽ d (A, D) + d (D, B) .$

Or $A \cap D = A \cap C$ et $A \cup D \subset A \cup C$ donc

$d (A, D) = 1 - \frac{Card (A \cap D)}{Card (A \cup D)} = 1 - \frac{Card (A \cap C)}{Card (A \cup D)} ⩽ 1 - \frac{Card (A \cap C)}{Card (A \cup C)} = d (A, C) .$

De la même façon, $d (D, B) ⩽ d (C, B)$ et l’on obtient donc $d (A, B) ⩽ d (A, C) + d (C, B)$ .

[<] Ensemble fini[>] Dénombrements élémentaires

Exercice 8 1529 Correction

Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $n$ et $p$ .
Combien y a-t-il d’injections de $E$ dans $F$ ?

Solution

Si $n > p$ , il n’y a pas d’injections possibles.
Si $n = 0$ , il y a une injection: l’application vide.
Si $0 < n \leq p$ alors on peut écrire $E = {x_{1}, \dots, x_{n}}$ avec les $x_{i}$ deux à deux distincts.
Pour former une injection de $E$ dans $F$ :
On choisit $f (x_{1})$ dans $F$ : $p$ choix.
On choisit $f (x_{2})$ dans $F ∖ {f (x_{1})}$ : $p - 1$ choix.
…
On choisit $f (x_{n})$ dans $F ∖ {f (x_{1}), \dots, f (x_{n - 1})}$ : $p - n + 1$ choix.
Au total, il y a $p \times (p - 1) \times \dots \times (p - n + 1) = \frac{p!}{(p - n)!}$ choix.

Exercice 9 1531 Correction

Combien existe-t-il de relation d’ordre total sur un ensemble $E$ à $n$ éléments?

Solution

Une relation d’ordre total sur $E$ permet de définir par numérotation des éléments, une bijection de ${1, \dots, n}$ vers $E$ et inversement.

Par suite, il y a exactement $n!$ relations d’ordre total possibles.

Exercice 10 1530 Correction

Soient $E = {1, \dots, n}$ et $F = {1, \dots, p}$ avec $n, p \in ℕ ∖ {0,1}$ .

(a)

Combien y a-t-il d’applications constantes de $E$ vers $F$ ?
(b)

Combien y a-t-il d’applications strictement croissantes de $E$ vers $F$ ?
(c)

Combien y a-t-il d’applications strictement monotones de $E$ vers $F$ ?
(d)

Combien y a-t-il d’applications croissantes de $E$ vers $F$ ?
(e)

Combien y a-t-il d’applications monotones de $E$ vers $F$ ?

Solution

(a)

Une application constante de $E$ vers $F$ est entièrement déterminée par le choix de la valeur de sa constante dans $F$ . Il y a $p$ choix possibles et donc $p$ applications constantes de $E$ vers $F$ .
(b)

Une application $f : E \to F$ strictement croissante est entièrement déterminée par son image qui est une partie formée de $n$ éléments de $F$ : il suffit d’ordonner les $n$ éléments qui constituent cette image pour définir l’application strictement croissante associée.

Si $p \geq n$ : il y a $(\binom{p}{n})$ parties à $n$ éléments dans $F$ et donc autant d’applications strictement croissantes de $E$ vers $F$ .

Si $p < n$ : il n’y a pas de parties à $n$ éléments dans $F$ et donc pas d’applications strictement croissantes de $E$ vers $F$ . Cela correspond encore à la valeur de $(\binom{p}{n})$ .
(c)

Par le même raisonnement, il y autant d’applications strictement décroissantes que d’applications strictement croissantes. De plus, les applications strictement croissantes sont distinctes des applications strictement décroissantes. Au total, il y a $2 (\binom{n}{p})$ applications strictement monotones de $E$ vers $F$ .
(d)

À une application $f : E \to F$ , on associe $g : E \to G$ définie par

$\forall k \in ⟦ 1; n ⟧, g (k) = f (k) + k - 1 avec G = {1, \dots, p + n - 1}$

Par cette association, on fait se correspondre de façon bijective les applications croissantes de $E$ vers $F$ et les applications strictement croissantes de $E$ vers $G$ . Il y a donc $(\binom{n + p - 1}{n})$ applications croissantes de $E$ vers $F$ .
(e)

En composant une application à valeurs dans $F$ avec l’application $h : F \to F$ donnée par $h (k) = p + 1 - k$ , on fait se correspondre de façon bijective les applications croissantes de $E$ vers $F$ et les applications décroissantes de $E$ vers $F$ . Il y a donc exactement $(\binom{n + p - 1}{n})$ applications décroissantes de $E$ vers $F$ . Aussi, les applications à la fois croissantes et décroissantes de $E$ vers $F$ sont les applications constantes, il y en a $p$ . Au final, il y a

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

applications monotones de $E$ vers $F$ .

Exercice 11 4437

Soient $n \in ℕ$ , $p \in ℕ^{*}$ et $E = ⟦ 1; n ⟧$ .

(a)

Dénombrer les familles strictement croissantes $(x_{1}, \dots, x_{p})$ d’éléments de $E$ .
(b)

Dénombrer les familles croissantes $(x_{1}, \dots, x_{p})$ d’éléments de $E$ .

Exercice 12 3933 Correction

(a)

Quel est le coefficient de $a^{2} b^{5} c^{3}$ dans le développement de ${(a + b + c)}^{10}$ ?
(b)

Même question avec $a_{1}^{k_{1}} a_{2}^{k_{2}} \dots a_{p}^{k_{p}}$ dans ${(a_{1} + a_{2} + \dots + a_{p})}^{n}$ .

Solution

(a)

Dans le développement de

${(a + b + c)}^{10} = (a + b + c) (a + b + c) \dots (a + b + c)$

on obtient un terme $a^{2} b^{5} c^{3}$ en choisissant deux $a$ , cinq $b$ et trois $c$ .
Il y a $(\binom{10}{2})$ choix possibles pour les facteurs dont seront issus les $a$ .
Une fois ceux-ci choisis, il y a $(\binom{8}{5})$ choix possibles pour les facteurs fournissant les $b$ .
Une fois ces choix faits, les trois facteurs restant fournissent les $c$ .
Au total, il y a

$(\binom{10}{2}) (\binom{8}{5}) = \frac{10!}{2! 5! 3!} = 2520$

termes $a^{2} b^{5} c^{3}$ apparaissant lors du développement de ${(a + b + c)}^{10}$ .
(b)

On reprend le même protocole, pour obtenir

$\frac{n!}{k_{1}! k_{2}! \dots k_{p}!}$

si $k_{1} + k_{2} + \dots + k_{p} = n$ et 0 sinon.

Exercice 13 4438

(Anagrammes)

Un mot $M$ long de $n$ lettres est constitué de $r$ lettres différentes. La $j$ -ème lettre apparaît $p_{j}$ fois dans le mot $M$ et donc $p_{1} + \dots + p_{r} = n$ .

(a)

Combien d’anagrammes différentes du mot $M$ peut-on écrire?
(b)

Dans le développement de ${(a_{1} + a_{2} + \dots + a_{r})}^{n}$ , quel est le coefficient du terme $a_{1}^{p_{1}} a_{2}^{p_{2}} \dots a_{r}^{p_{r}}$ ?

Exercice 14 4440

(Nombres de combinaisons avec répétition)

On appelle combinaison avec répétition de longueur $p$ formée d’éléments d’un ensemble $E$ , le choix non ordonné de $p$ éléments dans $E$ avec possibilité de répétitions de ceux-ci¹¹ 1 Par exemple, les choix de $1,1,2$ ou de $1,2,1$ définissent la même combinaison avec répétition de longueur $3$ formée d’éléments de ${1,2,3,4}$ .. Combien peut-on former de combinaisons avec répétition de longueur $p$ sur un ensemble à $n \geq 1$ éléments?

Exercice 15 1536 Correction

Soit $E$ un ensemble à $n$ éléments.

(a)

Soit $X$ une partie à $p$ éléments de $E$ .
Combien y a-t-il de parties $Y$ de $E$ disjointes de $X$ ?
(b)

Combien y a-t-il de couples $(X, Y)$ formés de parties disjointes de $E$ ?

Solution

(a)

Autant que de parties de $E ∖ X$ : $2^{n - p}$
(b)

$\sum_{p = 0}^{n} (\binom{n}{p}) 2^{n - p} = {(1 + 2)}^{n} = 3^{n}$ .

Exercice 16 1538 Correction

Soit $A$ une partie d’un ensemble $E$ à $n$ éléments. On pose $p = Card (A)$ .

(a)

Combien y a-t-il de parties $X$ de $E$ contenant $A$ ?
(b)

Combien y a-t-il de parties $X$ de $E$ à $m \in {p, \dots, n}$ éléments contenant $A$ ?
(c)

Combien y a-t-il de couples $(X, Y)$ de parties de $E$ tels que $X \cap Y = A$ ?

Solution

(a)

Il y en a autant que de parties de $E ∖ A$ : $2^{n - p}$
(b)

Il y en a autant que de parties de $E ∖ A$ à $m - p$ éléments: $(\binom{n - p}{m - p})$ .
(c)

Une fois $X$ à $m$ éléments contenant $A$ déterminé, il y a $2^{n - m}$ choix de $Y$ possibles. On obtient un total de couples de:

$\sum_{m = p}^{n} (\binom{n - p}{m - p}) 2^{n - m} = \sum_{k = 0}^{n - p} (\binom{n - p}{k}) 2^{n - p - k} = {(1 + 2)}^{n - p} = 3^{n - p} .$

Exercice 17 1537

Soit $E$ un ensemble à $n \in ℕ$ éléments. Combien existe-t-il de couples $(X, Y)$ constitués de parties de $E$ vérifiant $X \subset Y$ ?

Exercice 18 1532 Correction

On trace dans un plan $n$ droites en position générale (c’est-à-dire deux d’entre elles ne sont jamais parallèles ni trois d’entre elles concourantes). Combien forme-t-on ainsi de triangles?

Solution

Notons $t_{n}$ le nombre de triangles formés.

t_{0} = t_{1} = t_{2} = 0 .

Pour $n \geq 3$ , former un triangle revient à choisir les trois droites définissant ses côtés:

il y a (\binom{n}{3}) possibilités.

Chacune de ses possibilités définit un véritable triangle (car il y a ni concourance, ni parallélisme) et les triangles obtenus sont deux à deux distincts.

Finalement,

t_{n} = (\binom{n}{3}) .

Exercice 19 1540 Correction

Combien y a-t-il de $p$ -cycles dans le groupe $(𝒮_{n}, \circ)$ ?

Solution

Une injection $f$ de $ℕ_{p}$ dans $ℕ_{n}$ permet de définir le $p$ -cycle $(f (1) \dots f (p))$ .
Inversement, un $p$ -cycle de $ℕ_{n}$ peut être définis par exactement $p$ injections différentes.
En vertu du principe des bergers, il y a exactement $\frac{n!}{p (n - p)!}$ $p$ -cycles dans $𝒮_{n}$ .

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

Exercice 20 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 21 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 22 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 23 4431

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

Exercice 24 5728 Correction

Soit $n \in ℕ$ avec $n \geq 2$ .

(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, \dots, n}$ ?
(c)

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

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

On suppose $n \geq 3$ .

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)

Une surjection de ${1, \dots, n}$ vers ${1, \dots, n}$ est une bijection et inversement. Il y a donc autant de surjections de ${1, \dots, n}$ vers ${1, \dots, n}$ que de permutation de ${1, \dots, n}$ , à savoir $n!$ .
(c)

Une surjection au départ de ${1, \dots, n}$ prend au plus $n$ valeurs distinctes. Il n’existe pas de surjections de ${1, \dots, n}$ sur ${1, \dots, n + 1}$ .
(d)

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}$ .
(e)

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 25 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 26 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!} .

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

Exercice 27 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 28 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 29 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 30 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 31 3985 Correction

Soit $n \in ℕ$ avec $n \geq 2$ . On note $𝒮_{n}$ l’ensemble des permutations de $⟦ 1; n ⟧$ .

On dit que $i \in ⟦ 1; n ⟧$ est un point fixe d’une permutation $σ \in 𝒮_{n}$ lorsque $σ (i) = i$ .

(a)

Combien existe-t-il d’éléments dans $𝒮_{n}$ ?

Combien existe-t-il d’éléments dans $𝒮_{n}$ dont $n$ est point fixe?

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

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

(b)

Calculer

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

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) .$
(d)

En déduire

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

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

Solution

(a)

On sait par le cours qu’il y a exactement $n!$ permutations sur un ensemble à $n$ éléments: $Card (𝒮_{n}) = n!$ .

Une permutation de $⟦ 1; n ⟧$ dont $n$ est point fixe s’identifie avec une permutation de $⟦ 1; n - 1 ⟧$ . Il y en a exactement $(n - 1)!$ .
(b)

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! .$
(c)

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)$ .
(d)

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) .$
(e)

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 32 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 33 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 ⩽ 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 34 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 35 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 36 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 37 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 38 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 ⩽ p ⩽ 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 avancés[>] Démonstrations combinatoires

Exercice 39 3961

(Calcul par anagramme)

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

(a)

Un mot est constitué de $p$ fois le caractère A et $q$ fois le caractère B. Combien peut-on constituer d’anagrammes de ce mot?
(b)

On suppose $p \geq 1$ . En considérant les symboles \og $1$ \fg et \og $+$ \fg, combien existe-t-il de familles $(x_{1}, \dots, x_{p}) \in ℕ^{p}$ vérifiant $x_{1} + \dots + x_{p} = n$ ?
(c)

Même question avec $(x_{1}, \dots, x_{p}) \in {(ℕ^{*})}^{p}$ .

Exercice 40 3960 Correction

(a)

Combien existe-t-il de suites strictement croissante de $p$ entiers choisis dans ${1, \dots, n}$ ?
(b)

Application : Combien existe-t-il de suite $(x_{1}, \dots, x_{p})$ avec

$x_{1} + \dots + x_{p} \leq n et x_{1}, \dots, x_{p} \in ℕ^{*} .$
(c)

Même question avec

$x_{1} + \dots + x_{p} = n et x_{1}, \dots, x_{p} \in ℕ^{*} .$

Solution

(a)

Une suite strictement croissante de $p$ entiers dans ${1, \dots, n}$ est entièrement déterminée par le choix de ses éléments qu’il suffit alors d’ordonner. Il y en a donc

$(\binom{n}{p}) .$
(b)

À chaque suite $(x_{1}, \dots, x_{p})$ vérifiant $x_{1} + \dots + x_{p} \leq n$ et $x_{1}, \dots, x_{p} \in ℕ^{*}$ on peut associer une suite strictement croissante $(y_{1}, \dots, y_{p})$ d’éléments de ${1, \dots, n}$ en posant

$y_{k} = x_{1} + \dots + x_{k} .$

Inversement, à une suite $(y_{1}, \dots, y_{p})$ comme au dessus correspond une unique suite $(x_{1}, \dots, x_{p})$ comme voulue avec

$x_{1} = y_{1}, x_{k} = y_{k} - y_{k - 1} pour k \geq 2 .$

Il y a donc autant de suites $(x_{1}, \dots, x_{p})$ vérifiant $x_{1} + \dots + x_{p} \leq n$ et $x_{1}, \dots, x_{p} \in ℕ^{*}$ que de suite strictement croissantes de $p$ éléments dans ${1, \dots, n}$ , soit

$(\binom{n}{p}) .$
(c)

La condition $x_{1} + \dots + x_{p} = n$ est remplie quand $x_{1} + \dots + x_{p} \leq n$ mais pas $x_{1} + \dots + x_{p} \leq n - 1$ . Le nombre de suite cherché est donc

$(\binom{n}{p}) - (\binom{n - 1}{p}) = (\binom{n - 1}{p - 1}) .$

Exercice 41 3930

(Calcul par les familles croissantes)

Soient $n \in ℕ$ et $p \in ℕ^{*}$ .

Il existe ¹¹ 1 Voir le sujet 4437 où l’on a simplement opéré un glissement sur l’ensemble des valeurs en considérant $⟦ 0; n ⟧$ au lieu de $⟦ 1; n + 1 ⟧$ . $(\binom{n + p}{p})$ familles croissantes de longueur $p$ constituées d’éléments de $⟦ 0; n ⟧$ .

(a)

Combien existe-t-il de familles $(x_{1}, \dots, x_{p}) \in ℕ^{p}$ vérifiant $x_{1} + \dots + x_{p} \leq n$ ?
(b)

Même question avec la condition $x_{1} + \dots + x_{p} = n$ .

Exercice 42 1535

(Calcul par récurrence)

Soient $n \in ℕ$ et $p \in ℕ^{*}$ . On note $C_{n}^{p}$ le nombre de familles $(x_{1}, \dots, x_{p}) \in ℕ^{p}$ vérifiant la condition $x_{1} + \dots + x_{p} = n$ .

(a)

Établir

$C_{n}^{p + 1} = \sum_{k = 0}^{n} C_{k}^{p} .$
(b)

En déduire

$C_{n}^{p} = (\binom{n + p - 1}{n}) .$

[<] Composition d'un entier

Exercice 43 4434

Soient $n$ et $p \in ℕ$ . Proposer des preuves combinatoires¹¹ 1 Une preuve combinatoire est une justification réalisée par dénombrement. Par exemple, en calculant de deux façons différentes le cardinal d’un même ensemble. des formules:

(a)

$\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$
(b)

$(\binom{n}{n - p}) = (\binom{n}{p})$
(c)

$(\binom{n}{p}) + (\binom{n}{p + 1}) = (\binom{n + 1}{p + 1})$ .

Exercice 44 1533 Correction

(Formule de Chu-Vandermonde)

Soient $p, q \in ℕ$ et $n \in ⟦ 0; p + q ⟧$ . Proposer une démonstration par dénombrement de l’égalité

(\binom{p + q}{n}) = \sum_{k = 0}^{n} (\binom{p}{k}) (\binom{q}{n - k}) .

Solution

Soit $E$ un ensemble à $p + q$ éléments séparé en deux parties disjointes $E^{'}$ et $E^{''}$ de cardinaux $p$ et $q$ .
Il y a exactement $(\binom{p + q}{n})$ parties à $n$ éléments dans $E$ .
Or pour former une partie à $n$ élément de $E$ , on peut pour chaque $k \in ⟦ 0; n ⟧$ commencer par choisir $k$ éléments dans $E^{'}$ avant d’en choisir $n - k$ dans $E^{''}$ . Il y a $(\binom{p}{k}) (\binom{q}{n - k})$ possibilités pour chaque $k \in ⟦ 0; n ⟧$ puis au total $\sum_{k = 0}^{n} (\binom{p}{k}) (\binom{q}{n - k})$ possibilités d’où l’identité.

Exercice 45 4435

Soient $E$ un ensemble à $n$ éléments et $p$ un entier avec $1 \leq p \leq n$ . En dénombrant les couples $(A, x)$ constitués d’une partie $A$ de $E$ à $p$ éléments et d’un élément $x$ de $A$ , établir l’identité

(\binom{n}{p}) = \frac{n}{p} (\binom{n - 1}{p - 1}) .

Édité le 29-11-2025

	$d (A, C)$	$= 1 - \frac{Card (A \cap C)}{Card (A \cup C)} = \frac{Card (A \cup C) - Card (A \cap C)}{Card (A \cup C)}$
		$⩾ \frac{Card (A \cup C) - Card (A \cap C)}{Card (A \cup B)} .$

	$Card (A \cup C) + Card (B \cup C)$	$- Card (A \cap C) - Card (B \cap C)$		( $*$ )
		$⩾ Card (A \cup B) - Card (A \cap B) .$

	$a$	$= Card (A ∖ (B \cup C)),$	$b$	$= Card (B ∖ (A \cup C)),$	$c$	$= Card (A \cap B \cap C)$
	$α$	$= Card (C ∖ A),$	$β$	$= Card (C ∖ B),$	$γ$	$= Card (C ∖ (A \cap B))$

$Card (A \cup C)$	$= a + α + β + γ + c$	$Card (A \cap C)$	$= β + c$
$Card (B \cup C)$	$= b + α + β + γ + c$	$Card (B \cap C)$	$= α + c$
$Card (A \cup B)$	$= a + α + β + γ + c + b$	$Card (A \cap B)$	$= γ + c$

	$(a + α + β + γ + c) + (b + α + β + γ + c)$	$- (β + c) - (α + c)$
		$⩾ (a + α + β + γ + c + b) - (γ + c) .$