Dénombrement

Cours complet · mathématiques MPSI, chapitre 18 · MPSI (classe préparatoire scientifique)

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>18.1 Introduction et motivation

Compter sans énumérer : tel est l'art du dénombrement. Cette section est introduite essentiellement en vue de son utilisation en probabilités (le chapitre suivant : probabilités sur un univers fini, où tout calcul de probabilité uniforme est un quotient de deux dénombrements) ; rattachée aux mathématiques discrètes, elle interagit aussi avec l'algèbre (permutations du chapitre 14, coefficients binomiaux du chapitre 2) et l'informatique (complexité des algorithmes, structures de données).

L'esprit du programme : toute formalisation excessive est exclue. Les propriétés les plus intuitives du cardinal sont admises sans démonstration, et l'utilisation systématique de bijections n'est pas un attendu — on raisonne par principes de comptage (addition, multiplication) et par modèles (listes, tirages, comités).

18.2 Cardinal d'un ensemble fini

Définition 18.1Cardinal

Un ensemble $E$ est fini s'il a un nombre fini d'éléments ; ce nombre est son cardinal, noté $∣ E ∣$ ou $Card (E)$ (et $∣ \emptyset ∣ = 0$ ). Tout fondement théorique des notions d'entier naturel et de cardinal est hors programme : on s'appuie sur l'intuition du « nombre d'éléments ».

Proposition 18.2Parties d'un ensemble fini

Si $A \subset E$ avec $E$ fini, alors $A$ est fini et $∣ A ∣ \leq ∣ E ∣$ , avec égalité si et seulement si $A = E$ .

◆Théorème 18.3Injectif, surjectif, bijectif : le cas équicardinal

Soient $E, F$ finis de même cardinal et $f : E \to F$ . Alors :

$f bijective ⟺ f injective ⟺ f surjective .$

iRemarqueLe principe des tiroirs

Version contraposée, dite des tiroirs (ou de Dirichlet) : si l'on range $n + 1$ chaussettes dans $n$ tiroirs, un tiroir contient au moins deux chaussettes — toute application d'un ensemble de cardinal $> n$ vers un ensemble de cardinal $n$ est non injective. Simple et redoutable (exercice 5). On notera l'analogie parfaite avec la dimension finie (chapitre 12) : même énoncé, les cardinaux remplaçant les dimensions.

◆Théorème 18.4Opérations sur les cardinaux

Soient $A, B$ des parties d'un ensemble fini $E$ .

Union disjointe : si $A \cap B = \emptyset$ , alors $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ (principe d'addition : on découpe en cas incompatibles) ; plus généralement, pour une partition $E = A_{1} ⊔ \dots ⊔ A_{k}$ : $∣ E ∣ = \sum ∣ A_{i} ∣$ .
Union quelconque : $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ (les éléments de $A \cap B$ étaient comptés deux fois ; la formule du crible générale à $k$ ensembles est hors programme).
Complémentaire : $A = ∣ E ∣ - ∣ A ∣$ ; différence : $∣ A ∖ B ∣ = ∣ A ∣ - ∣ A \cap B ∣$ .
Produit cartésien : $∣ A \times B ∣ = ∣ A ∣ \times ∣ B ∣$ (principe de multiplication : choix successifs indépendants).

◆Théorème 18.5Applications et parties

Soient $E$ et $F$ finis, $∣ E ∣ = p$ , $∣ F ∣ = n$ .

Le nombre d'applications de $E$ dans $F$ est $F^{E} = n^{p}$ (pour chacun des $p$ éléments de $E$ , $n$ choix indépendants d'image).
Le nombre de parties de $E$ est $∣ P (E) ∣ = 2^{p}$ (pour chaque élément : dedans ou dehors — une partie, c'est une application de $E$ dans ${0, 1}$ ).

18.3 Listes et combinaisons

◆Théorème 18.6Listes d'éléments distincts, permutations, injections

Soit $E$ de cardinal $n$ .

Le nombre de $p$ -listes (ou $p$ -uplets) d'éléments distincts de $E$ (l'ordre compte, pas de répétition) est :

$n (n - 1) (n - 2) \dots (n - p + 1) = \frac{n !}{( n - p )!} (0 \leq p \leq n)$

( $n$ choix pour le premier, $n - 1$ pour le deuxième, etc.).

Cas $p = n$ : le nombre de permutations de $E$ est $n!$ — on retrouve $∣ S_{n} ∣ = n!$ (chapitre 14).
Le nombre d'applications injectives d'un ensemble de cardinal $p$ dans un ensemble de cardinal $n$ est ce même nombre $\frac{n !}{( n - p )!}$ : une injection, c'est la $p$ -liste (sans répétition) de ses valeurs.

◆Théorème 18.7Combinaisons

Le nombre de parties à $p$ éléments (ou $p$ -combinaisons) d'un ensemble de cardinal $n$ est :

$(p n) = \frac{n !}{p ! ( n - p )!} = \frac{n ( n - 1 ) \dots ( n - p + 1 )}{p !} .$

Démonstration

Comptons les $p$ -listes d'éléments distincts de deux façons. Directement : $\frac{n !}{( n - p )!}$ . Ou bien : on choisit d'abord la partie des $p$ éléments utilisés ( $(p n)$ façons), puis on les ordonne ( $p!$ façons). D'où $\frac{n !}{( n - p )!} = (p n) p!$ , ce qui donne la formule. (Moralité : l'ordre coûte un facteur $p!$ — diviser par $p!$ fait passer des listes aux parties.)

◆Théorème 18.8Formule de Pascal, démonstration combinatoire

$(p n) = (p - 1 n - 1) + (p n - 1) (1 \leq p \leq n - 1) .$

Démonstration

Fixons un élément $x$ de $E$ ( $∣ E ∣ = n$ ) et trions les parties à $p$ éléments selon qu'elles contiennent $x$ ou non — deux cas incompatibles qui recouvrent tout (principe d'addition) :

celles qui contiennent $x$ : il reste à choisir $p - 1$ éléments parmi les $n - 1$ autres, soit $(p - 1 n - 1)$ ;
celles qui ne contiennent pas $x$ : on choisit les $p$ éléments parmi les $n - 1$ autres, soit $(p n - 1)$ .

C'est la démonstration combinatoire du triangle de Pascal (chapitre 2 le prouvait par le calcul).

◆Théorème 18.9Formule du binôme, démonstration combinatoire

Pour $a, b$ dans un anneau commutatif (chapitre 8) et $n \in N$ :

$(a + b)^{n} = k = 0 \sum n (k n) a^{k} b^{n - k} .$

Démonstration

Développons $(a + b)^{n} = (a + b) (a + b) \dots (a + b)$ sans regrouper : chaque terme du développement s'obtient en choisissant, dans chacun des $n$ facteurs, soit $a$ soit $b$ . Le terme $a^{k} b^{n - k}$ apparaît donc autant de fois qu'il y a de façons de choisir l'ensemble des $k$ facteurs fournissant un $a$ : exactement $(k n)$ fois.

ImportantQuel modèle pour quel comptage ?

Le réflexe à acquérir : identifier l'ordre et la répétition.

	avec répétition	sans répétition
ordre compte (listes)	$n^{p}$ ( $p$ -listes)	$\frac{n !}{( n - p )!}$ (listes d'élts distincts)
[2mm] ordre indifférent (parties)	(hors programme)	$(p n)$ (combinaisons)

Tirages successifs avec remise $\to n^{p}$ ; sans remise $\to \frac{n !}{( n - p )!}$ ; tirage simultané (une poignée) $\to (p n)$ .

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>18.4 Exercices résolus

Niveau $⋆$ (Application directe du cours)

Exercice 1 : Principe de multiplication

Combien de plaques d'immatriculation formées de $2$ lettres suivies de $3$ chiffres ? Combien de menus composés d'une entrée parmi $3$ , d'un plat parmi $4$ et d'un dessert parmi $2$ ?

Démonstration (Solution)

Choix successifs indépendants (produit cartésien) :

$26 \times 26 \times 10 \times 10 \times 10 = 2 6^{2} \times 1 0^{3} = 676000 plaques, 3 \times 4 \times 2 = 24 menus .$

Exercice 2 : Listes avec ou sans répétition

Combien d'anagrammes (mots, sensés ou non) du mot MATHS ? Combien de codes à $4$ chiffres deux à deux distincts ?

Démonstration (Solution)

MATHS a $5$ lettres toutes distinctes : une anagramme est une permutation, soit $5! = 120$ mots.

Un code à chiffres distincts est une $4$ -liste d'éléments distincts de ${0, \dots, 9}$ :

$10 \times 9 \times 8 \times 7 = \frac{10 !}{6 !} = 5040$

(à comparer aux $1 0^{4} = 10000$ codes avec répétitions autorisées : l'interdiction de répéter en élimine près de la moitié).

Exercice 3 : Combinaisons

Combien de mains de $5$ cartes peut-on former à partir d'un jeu de $32$ cartes ?

Démonstration (Solution)

Une main est un tirage simultané : l'ordre est indifférent, pas de répétition — une $5$ -combinaison :

$(5 32) = \frac{32 \times 31 \times 30 \times 29 \times 28}{5 !} = \frac{24 165 120}{120} = 201 376.$

(Si l'on distribuait les cartes une à une en notant l'ordre, il y en aurait $32 \times 31 \times 30 \times 29 \times 28$ — chaque main y est comptée $5! = 120$ fois.)

Niveau $⋆ ⋆$ (Application avec raisonnement intermédiaire)

Exercice 4 : Union et complémentaire

Dans une promotion de $100$ étudiants, $60$ étudient l'anglais, $45$ l'espagnol et $25$ les deux. Combien étudient au moins une des deux langues ? aucune des deux ?

Démonstration (Solution)

Par la formule de l'union (les $25$ bilingues sont comptés deux fois dans $60 + 45$ ) :

$∣ A \cup E ∣ = 60 + 45 - 25 = 80, A \cup E = 100 - 80 = 20.$

$80$ étudiants pratiquent au moins une langue, $20$ aucune.

Exercice 5 : Le principe des tiroirs

Montrer que dans un groupe de $367$ personnes, deux au moins ont le même jour d'anniversaire. Montrer que dans toute réunion de $n \geq 2$ personnes, deux personnes connaissent exactement le même nombre de participants.

Démonstration (Solution)

Anniversaires : l'application « personne $\mapsto$ jour d'anniversaire » va d'un ensemble de cardinal $367$ vers un ensemble de cardinal au plus $366$ : elle ne peut être injective.

Connaissances : chaque personne connaît entre $0$ et $n - 1$ participants, soit $n$ valeurs possibles pour $n$ personnes — les tiroirs semblent suffire ! Mais les valeurs $0$ (quelqu'un ne connaît personne) et $n - 1$ (quelqu'un connaît tout le monde) sont incompatibles : au plus $n - 1$ valeurs sont effectivement prises, pour $n$ personnes. Le principe des tiroirs conclut : deux personnes ont le même nombre de connaissances.

Exercice 6 : Comités sous contrainte

Un club compte $7$ femmes et $5$ hommes. Combien de comités de $4$ personnes contenant au moins deux femmes ?

Démonstration (Solution)

Par le complémentaire : sur les $(4 12) = 495$ comités possibles, on retire ceux qui ont $0$ femme ( $(4 5) = 5$ ) ou $1$ femme ( $(1 7) (3 5) = 7 \times 10 = 70$ ) :

$495 - 5 - 70 = 420.$

Contrôle par addition directe (cas incompatibles selon le nombre de femmes) :

$(2 7) (2 5) + (3 7) (1 5) + (4 7) (0 5) = 21 \times 10 + 35 \times 5 + 35 = 210 + 175 + 35 = 420. ✓$

(Deux stratégies royales du dénombrement : passer au complémentaire quand la contrainte est « au moins », découper en cas incompatibles sinon.)

Exercice 7 : Parties de cardinal pair

Soit $E$ de cardinal $n \geq 1$ . Montrer que le nombre de parties de $E$ de cardinal pair vaut $2^{n - 1}$ — autant que de parties de cardinal impair.

Démonstration (Solution)

Notons $P$ et $I$ les nombres de parties de cardinal pair et impair. En triant les $2^{n}$ parties par cardinal :

$P + I = k \sum (k n) = 2^{n}, P - I = k \sum (- 1)^{k} (k n) = (1 - 1)^{n} = 0$

(formule du binôme avec $a = - 1$ , $b = 1$ ; ici $n \geq 1$ ). D'où $P = I = 2^{n - 1}$ .

Niveau $⋆ ⋆ ⋆$ (Raisonnement subtil ou plusieurs étapes)

Exercice 8 : Compter de deux façons

Démontrer combinatoirement l'identité $k = 0 \sum n k (k n) = n 2^{n - 1}$ .

Démonstration (Solution)

Comptons les couples (équipe, capitaine) — une équipe de taille quelconque choisie parmi $n$ personnes, avec un capitaine dans l'équipe — de deux façons :

équipe d'abord : pour chaque taille $k$ , $(k n)$ équipes puis $k$ choix de capitaine : total $\sum_{k} k (k n)$ ;
capitaine d'abord : $n$ choix de capitaine, puis chacune des $n - 1$ autres personnes est dans l'équipe ou non : $n \times 2^{n - 1}$ .

Les deux comptages dénombrent le même ensemble : l'identité est prouvée. (Vérification analytique : dériver $(1 + x)^{n} = \sum (k n) x^{k}$ et évaluer en $x = 1$ — le chapitre 10 confirme le chapitre 18.)

Exercice 9 : Chemins sur une grille

Combien de chemins mènent de $(0, 0)$ à $(p, q)$ en ne faisant que des pas vers la droite (D) ou vers le haut (H) ?

Démonstration (Solution)

Un tel chemin comporte exactement $p$ pas D et $q$ pas H, soit $p + q$ pas en tout : il est entièrement déterminé par le choix des positions des pas D dans la suite des $p + q$ pas — une partie à $p$ éléments de ${1, \dots, p + q}$ :

$(p p + q) chemins.$

Exemple : de $(0, 0)$ à $(4, 3)$ , $(4 7) = 35$ chemins.

(Compter des chemins en comptant des mots : l'encodage est l'arme secrète du dénombrement — et le chemin dessiné correspond au mot indiqué.)

Exercice 10 : La formule de Vandermonde

Démontrer combinatoirement que $(p m + n) = k = 0 \sum p (k m) (p - k n)$ , et en déduire $k = 0 \sum n (k n)^{2} = (n 2 n)$ .

Démonstration (Solution)

Une assemblée compte $m$ femmes et $n$ hommes ; comptons les délégations de $p$ personnes. Directement : $(p m + n)$ . En triant selon le nombre $k$ de femmes (cas incompatibles) : $(k m)$ choix de femmes et $(p - k n)$ choix d'hommes, d'où $\sum_{k} (k m) (p - k n)$ . Les deux comptages coïncident.

Avec $m = n = p$ et la symétrie $(n - k n) = (k n)$ :

$(n 2 n) = k = 0 \sum n (k n) (n - k n) = k = 0 \sum n (k n)^{2} .$

(On retrouve le coefficient binomial central, dont Stirling donnait l'équivalent $\frac{4 ^{n}}{π n}$ au chapitre 11 — trois chapitres, un même objet.)

Synthèse du chapitre (à retenir)

Cardinal : $∣ A ∣ \leq ∣ E ∣$ avec égalité ssi $A = E$ ; entre ensembles de même cardinal fini : injectif $⟺$ surjectif $⟺$ bijectif (principe des tiroirs en contraposée ; analogie avec la dimension finie).
Opérations : union disjointe $\to$ addition (découpage en cas) ; $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ (crible général hors programme) ; complémentaire $∣ E ∣ - ∣ A ∣$ (réflexe « au moins ») ; produit cartésien $\to$ multiplication (choix successifs).
$F^{E} = n^{p}$ (applications) ; $∣ P (E) ∣ = 2^{n}$ (chaque élément : dedans/dehors).
Listes vs parties : $p$ -listes quelconques $n^{p}$ (tirage avec remise) ; $p$ -listes d'éléments distincts $\frac{n !}{( n - p )!}$ (sans remise, $=$ nombre d'injections) ; permutations $n!$ ( $= ∣ S_{n} ∣$ ) ; combinaisons $(p n) = \frac{n !}{p ! ( n - p )!}$ (tirage simultané) — l'ordre coûte un facteur $p!$ .
Démonstrations combinatoires : Pascal $(p n) = (p - 1 n - 1) + (p n - 1)$ (contient $x$ ou non) ; binôme $(a + b)^{n} = \sum (k n) a^{k} b^{n - k}$ (choisir les facteurs donnant $a$ ).
Méthodes : identifier ordre/répétition (tableau) ; complémentaire pour « au moins » ; cas incompatibles ; compter de deux façons ( $\sum k (k n) = n 2^{n - 1}$ , Vandermonde) ; encoder (chemins $=$ mots : $(p p + q)$ ).

Continuer sur Adloun : animation, QCM, fiches, exercices

Dénombrement

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>18.1 Introduction et motivation

18.2 Cardinal d'un ensemble fini

18.3 Listes et combinaisons

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>18.4 Exercices résolus

Niveau ⋆ (Application directe du cours)

Niveau ⋆⋆ (Application avec raisonnement intermédiaire)

Niveau ⋆⋆⋆ (Raisonnement subtil ou plusieurs étapes)

Niveau $⋆$ (Application directe du cours)

Niveau $⋆ ⋆$ (Application avec raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (Raisonnement subtil ou plusieurs étapes)