Dénombrement

Cours complet · mathématiques (PTSI), chapitre 15 · CPGE PTSI (1re année)

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

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>15.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 (coefficients binomiaux du chapitre 2, formule du binôme) 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).

15.2 Cardinal d'un ensemble fini

Définition 15.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 15.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 15.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 11) : même énoncé, les cardinaux remplaçant les dimensions.

◆Théorème 15.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 15.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}$ ).

15.3 Listes et combinaisons

◆Théorème 15.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$ (c'est-à-dire de bijections de $E$ sur lui-même) est $n!$ .
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 15.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 15.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 15.9Formule du binôme, démonstration combinatoire

Pour $a, b$ réels ou complexes (ou deux matrices qui commutent, chapitre 7) 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)$ .

Continuer sur Adloun : animation, QCM, fiches, exercices