Éducation Nationale Française · BCPST

Dénombrement

⌚ ~75 min ▢ 9 blocs ✓ 44 exercices ➣ Prérequis : Logique, ensembles et raisonnement, Dénombrement

Dénombrer un ensemble fini, c'est déterminer son nombre d'éléments, appelé son cardinal. Ce chapitre construit la petite boîte à outils qui répond à « combien ? » dans les situations rencontrées toute l'année : combien de façons de remplir une grille, d'aligner des objets, de former une équipe, de lister les sous-ensembles d'un ensemble. Tout repose sur deux idées — le principe d'addition (séparer en cas disjoints et additionner) et le principe multiplicatif (faire des choix successifs indépendants et multiplier) — et sur une seule question de classement : le tirage est-il ordonné ou non, avec ou sans répétition ? Les réponses donnent les dénombrements classiques : $p$-uplets et arrangements (ordonnés, avec ou sans répétition), permutations (le cas particulier où l'ensemble entier est ordonné) et combinaisons (non ordonnées, sans répétition). On ne travaille qu'avec des ensembles finis et on justifie chaque formule par un argument court et intuitif plutôt que par une démonstration formelle. Les ensembles de nombres $\mathbb{N}$ (qui contient $0$) et les notations ensemblistes du premier chapitre sont supposés connus.

Signaler une erreur

I Ensembles finis et cardinal

I.1 Cardinal et dénombrement par cas

Un ensemble fini possède un nombre déterminé d'éléments. Le compter directement est facile lorsque l'ensemble se sépare en morceaux qui ne se recouvrent pas : on compte chaque morceau et on additionne.

Signaler une erreur

Définition — Ensemble fini et cardinal

Un ensemble $E$ est fini lorsqu'il possède un nombre fini d'éléments ; ce nombre est le cardinal de $E$, noté $|E|$ (aussi noté $\mathrm{card}(E)$). L'ensemble vide a pour cardinal $|\emptyset| = 0$. Un ensemble qui n'est pas fini est infini (comme $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{R}$) ; cette année on ne dénombre que des ensembles finis.

Exemple

$E = \{a, b, c, d\}$ a pour cardinal $|E| = 4$.
L'ensemble des faces d'un dé usuel est $\{1, 2, 3, 4, 5, 6\}$, de cardinal $6$.
L'ensemble des entiers pairs entre $1$ et $10$ est $\{2, 4, 6, 8, 10\}$, de cardinal $5$.

Définition — Ensembles disjoints

Deux ensembles finis $A$ et $B$ sont disjoints lorsque $A \cap B = \emptyset$ (aucun élément commun). Plus généralement, des ensembles finis $A_1, \dots, A_k$ sont deux à deux disjoints lorsque $A_i \cap A_j = \emptyset$ pour tous $i \ne j$.

Exemple

$\{1, 2, 3\}$ et $\{4, 5\}$ sont disjoints ; leur réunion a $3 + 2 = 5$ éléments.
$\{1, 2, 3\}$ et $\{3, 4\}$ ne sont pas disjoints : ils partagent l'élément $3$.

Proposition — Principe d'addition

Si les ensembles finis $A_1, \dots, A_k$ sont deux à deux disjoints, alors $$|A_1 \cup \dots \cup A_k| = |A_1| + \dots + |A_k|.$$ En particulier, pour deux ensembles disjoints $|A \cup B| = |A| + |B|$.

Preuve

En listant les éléments de $A_1$, puis ceux de $A_2$, et ainsi de suite, on liste chaque élément de la réunion exactement une fois, car les ensembles ne partagent aucun élément. Compter ces listes l'une après l'autre additionne donc les cardinaux. C'est la justification intuitive que l'on adopte ; aucun élément n'est compté deux fois précisément parce que les ensembles sont disjoints.

Exemple

Dans un groupe de $30$ étudiants, $12$ étudient seulement la biologie et $18$ seulement la géologie (personne ne fait les deux). Le nombre étudiant au moins l'une des deux est $|A \cup B| = 12 + 18 = 30$, car les deux ensembles sont disjoints.

Proposition — Cardinal d'une réunion de deux ensembles

Pour deux ensembles finis quelconques $A$ et $B$ : $$|A \cup B| = |A| + |B| - |A \cap B|.$$

Preuve

Additionner $|A|$ et $|B|$ compte chaque élément de $A \cap B$ deux fois : une fois comme élément de $A$, une fois comme élément de $B$. Soustraire $|A \cap B|$ retire ce surplus, de sorte que chaque élément de la réunion est compté exactement une fois.

Exemple

Parmi $100$ échantillons, $40$ contiennent du fer, $30$ du cuivre et $12$ les deux. Le nombre en contenant du fer ou du cuivre est $$|A \cup B| = 40 + 30 - 12 = 58.$$

Méthode — Dénombrer par cas

Pour dénombrer un ensemble qui n'est pas un simple tirage, le séparer en cas :

si les cas sont disjoints (sans recouvrement), additionner leurs cardinaux (principe d'addition) ;
s'ils peuvent se recouvrir, utiliser $|A \cup B| = |A| + |B| - |A \cap B|$ pour retirer la partie comptée deux fois.

Toujours vérifier d'abord si les cas se recouvrent.

Compétences à pratiquer

Calculer des cardinaux de réunions

II Principe multiplicatif et p-uplets

II.1 Le principe multiplicatif

Lorsqu'un objet se construit par une suite de choix successifs — où le nombre de possibilités à chaque étape ne dépend pas des choix précédents — le nombre total d'objets est le produit des nombres de choix. C'est l'outil de dénombrement le plus puissant.

Signaler une erreur

Définition — Cardinal d'un produit cartésien

Pour des ensembles finis $A$ et $B$, le produit cartésien $A \times B$ (l'ensemble des couples $(a, b)$ avec $a \in A$ et $b \in B$) est fini, avec $$|A \times B| = |A| \times |B|.$$

Exemple

Avec $A = \{1, 2, 3\}$ et $B = \{x, y\}$, les couples de $A \times B$ se disposent en une grille à $3$ lignes et $2$ colonnes :

Il y a $3 \times 2 = 6$ couples, donc $|A \times B| = 6$.

Exemple

Une armoire contient $4$ chemises et $3$ pantalons. Une tenue est un couple (chemise, pantalon), élément d'un produit cartésien, donc il y a $4 \times 3 = 12$ tenues.

Proposition — Principe multiplicatif

Si un objet se construit par $k$ choix successifs, où le premier a $n_1$ possibilités, le deuxième $n_2$ (quel que soit le premier choix), …, le $k$-ième $n_k$, alors le nombre d'objets construits est $$n_1 \times n_2 \times \dots \times n_k.$$

Preuve

Imaginons un arbre de dénombrement. Le premier choix donne $n_1$ branches ; au bout de chacune, le deuxième choix donne $n_2$ nouvelles branches, d'où $n_1 \times n_2$ chemins après deux choix ; et ainsi de suite. Le dessin ci-dessous montre le cas $n_1 = 2$ puis $n_2 = 3$, donnant $2 \times 3 = 6$ chemins complets.

Après $k$ choix, le nombre de chemins complets est le produit $n_1 \times \dots \times n_k$, chaque chemin étant un objet. Cet argument intuitif d'arbre est la justification que l'on utilise.

Exemple

Un repas propose $3$ entrées, $4$ plats et $2$ desserts. Un menu complet est une entrée, puis un plat, puis un dessert : par le principe multiplicatif il y a $3 \times 4 \times 2 = 24$ menus possibles.

Compétences à pratiquer

Appliquer le principe multiplicatif

II.2 p-uplets et tirages ordonnés avec répétition

Le premier modèle standard : on tire $p$ éléments d'un ensemble, l'un après l'autre, en notant l'ordre et en s'autorisant à répéter. C'est exactement un $p$-uplet de l'ensemble.

Signaler une erreur

Définition — p-uplet

Soit $E$ un ensemble fini et $p \in \mathbb{N}^*$. Un $p$-uplet (ou $p$-liste) de $E$ est une liste ordonnée $(x_1, \dots, x_p)$ de $p$ éléments de $E$, avec répétition autorisée ; c'est un élément de $E^p$. Il modélise un tirage ordonné avec répétition de $p$ éléments.

Proposition — Nombre de p-uplets

Si $|E| = n$, le nombre de $p$-uplets de $E$ est $$|E^p| = n^p.$$

Preuve

Construire $(x_1, \dots, x_p)$, c'est faire $p$ choix successifs : chacune des $p$ positions se remplit librement par l'un quelconque des $n$ éléments (répétition autorisée), donc chacune a $n$ possibilités. Par le principe multiplicatif le compte est $n \times n \times \dots \times n = n^p$ ($p$ facteurs).

Exemple

Un code à $4$ chiffres est un $4$-uplet de $\{0, 1, \dots, 9\}$ : il y a $10^4 = 10\,000$ codes.
Un brin d'ADN de longueur $5$ sur l'alphabet $\{A, C, G, T\}$ est un $5$-uplet : il y a $4^5 = 1024$ tels brins.

Méthode — Reconnaître un tirage ordonné avec répétition

Utiliser $n^p$ lorsque les objets sont des listes ordonnées (l'ordre des entrées compte) et que la répétition est autorisée (un même élément peut apparaître plusieurs fois). Formulations typiques : codes, mots sur un alphabet, résultats de $p$ lancers d'un dé.

Compétences à pratiquer

Dénombrer des tirages ordonnés avec répétition

III Arrangements et permutations

III.1 Arrangements : tirages ordonnés sans répétition

Le deuxième modèle garde l'ordre mais interdit la répétition : on tire $p$ éléments distincts dans l'ordre. Le compte diminue à chaque étape car un élément est consommé.

Signaler une erreur

Définition — Arrangement

Soit $|E| = n$ et $p \in \{1, \dots, n\}$. Un $p$-arrangement de $E$ est une liste ordonnée $(x_1, \dots, x_p)$ de $p$ éléments distincts de $E$ (un $p$-uplet sans répétition). Il modélise un tirage ordonné sans répétition.

Exemple

Avec $E = \{a, b, c\}$, les $2$-arrangements sont les $6$ couples ordonnés de lettres distinctes : $(a,b)$, $(b,a)$, $(a,c)$, $(c,a)$, $(b,c)$, $(c,b)$.
$(a, a)$ n'est pas un arrangement : il répète la lettre $a$.

Proposition — Nombre d'arrangements

Avec $|E| = n$ et $p \in \{1, \dots, n\}$, le nombre de $p$-arrangements de $E$, noté $A_n^p$, est $$A_n^p = n(n-1)(n-2)\cdots(n-p+1) = \frac{n!}{(n-p)!}.$$

Preuve

On construit la liste par $p$ choix successifs. Le premier élément a $n$ possibilités ; le deuxième doit différer du premier, donc $n-1$ ; le troisième $n-2$ ; et le $p$-ième a $n - (p-1) = n - p + 1$ possibilités. Par le principe multiplicatif : $$\begin{aligned} A_n^p &= n(n-1)\cdots(n-p+1) \\ &= \frac{n(n-1)\cdots(n-p+1)\,(n-p)!}{(n-p)!} && \text{(on multiplie et divise par } (n-p)! \text{)} \\ &= \frac{n!}{(n-p)!}. && \text{(le numérateur vaut } n! \text{)} \end{aligned}$$

Exemple

Un club de $10$ membres élit un président, un secrétaire et un trésorier, tous distincts. Un résultat est une liste ordonnée de $3$ membres distincts, soit un $3$-arrangement de $10$ membres : $$A_{10}^3 = 10 \times 9 \times 8 = 720.$$

Compétences à pratiquer

Dénombrer des arrangements

III.2 Permutations

Une permutation est le cas extrême de l'arrangement : on ordonne tous les éléments de l'ensemble. C'est le nombre de façons d'aligner $n$ objets distincts.

Signaler une erreur

Définition — Permutation

Une permutation d'un ensemble fini $E$ avec $|E| = n$ est un $n$-arrangement de $E$ : une liste ordonnée utilisant chaque élément de $E$ exactement une fois.

Proposition — Nombre de permutations

Un ensemble de cardinal $n$ a exactement $n!$ permutations.

Preuve

Une permutation est un $p$-arrangement avec $p = n$, donc son compte est $$A_n^n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!,$$ en utilisant $0! = 1$. Directement : la première place a $n$ choix, la suivante $n-1$, jusqu'à la dernière qui n'a qu'un seul choix, ce qui donne $n \times (n-1) \times \dots \times 1 = n!$.

Exemple

Le nombre de façons d'aligner $5$ livres distincts sur une étagère est $5! = 120$.
Les ordonnancements de $\{1, 2, 3\}$ sont les $3! = 6$ listes $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, $(3,2,1)$.

Méthode — Reconnaître un tirage ordonné sans répétition

Utiliser $A_n^p = \dfrac{n!}{(n-p)!}$ lorsque les objets sont des listes ordonnées d'éléments distincts (l'ordre compte, sans répétition) ; utiliser $n!$ lorsqu'on ordonne tous les éléments. Formulations typiques : classements, podiums, attribution de rôles distincts, alignement.

Compétences à pratiquer

Dénombrer des permutations

IV Combinaisons et parties

IV.1 Combinaisons : tirages sans ordre et sans répétition

Le dernier modèle abandonne l'ordre : on choisit $p$ éléments distincts sans tenir compte de l'ordre dans lequel on les prend. Un tel choix est simplement un sous-ensemble de taille $p$.

Signaler une erreur

Définition — Combinaison

Soit $|E| = n$ et $p \in \{0, 1, \dots, n\}$. Une $p$-combinaison de $E$ est un sous-ensemble de $E$ à $p$ éléments (une partie de $E$ à $p$ éléments). Elle modélise un tirage sans ordre et sans répétition. Leur nombre est noté $\binom{n}{p}$ (lu « $p$ parmi $n$ »).

Exemple

Avec $E = \{1, 2, 3\}$, les $2$-combinaisons de $E$ sont les sous-ensembles de taille $2$ : $$\{1, 2\}, \quad \{1, 3\}, \quad \{2, 3\},$$ il y en a donc $\binom{3}{2} = 3$. Remarquer que $\{1, 2\}$ et $\{2, 1\}$ sont le même sous-ensemble — l'ordre est ignoré.

Exemple

Choisir $2$ livres parmi $7$, sans ordre entre les deux, est une $2$-combinaison de $7$, donc son nombre est $\binom{7}{2}$. Il y a $7 \times 6 = 42$ choix ordonnés de $2$ livres distincts, et chaque paire de livres est comptée deux fois (les deux ordres), donc $$\binom{7}{2} = \frac{7 \times 6}{2} = 21.$$

Proposition — Nombre de combinaisons

Avec $|E| = n$ et $p \in \{0, 1, \dots, n\}$ : $$\binom{n}{p} = \frac{n!}{p!\,(n-p)!},$$ et pour $1 \le p \le n$ ceci vaut $\dfrac{A_n^p}{p!}$. En particulier $\binom{n}{0} = 1$ (le seul $0$-sous-ensemble est $\emptyset$).

Preuve

Prenons $1 \le p \le n$ et comparons les deux modèles. Un $p$-arrangement s'obtient en choisissant d'abord un sous-ensemble de $p$ éléments, puis en l'ordonnant. Chaque sous-ensemble de $p$ éléments peut être ordonné de $p!$ façons (les permutations de ses $p$ éléments), et ces ordonnancements donnent exactement $p!$ arrangements distincts à partir d'un sous-ensemble. Donc $$\begin{aligned} A_n^p &= \binom{n}{p} \times p! && \text{(chaque sous-ensemble fournit } p! \text{ arrangements)} \\ \binom{n}{p} &= \frac{A_n^p}{p!} && \text{(on divise par } p! \text{)} \\ &= \frac{n!}{p!\,(n-p)!}. && \text{(} A_n^p = n!/(n-p)! \text{)} \end{aligned}$$ Pour $p = 0$ la formule donne $\binom{n}{0} = n!/(0!\,n!) = 1$, l'unique sous-ensemble vide, donc la forme close vaut pour tout $p \in \{0, \dots, n\}$.

Exemple

Un jury de $3$ personnes est choisi parmi $10$ candidats, sans ordre entre les trois sièges. C'est une $3$-combinaison de $10$ : $$\binom{10}{3} = \frac{10!}{3!\,7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120.$$ À comparer aux $A_{10}^3 = 720$ choix ordonnés : chaque jury y était compté $3! = 6$ fois.

Compétences à pratiquer

Dénombrer des combinaisons

IV.2 Faits de dénombrement et nombre de parties

Deux faits de dénombrement sur $\binom{n}{p}$, déjà rencontrés en calculant avec les coefficients binomiaux, se lisent directement sur le modèle des sous-ensembles. On dénombre ensuite d'un coup tous les sous-ensembles d'un ensemble.

Signaler une erreur

Proposition — Symétrie et Pascal

Pour $p \in \{0, \dots, n\}$, la relation de symétrie $$\binom{n}{p} = \binom{n}{n-p},$$ et pour $1 \le p \le n-1$, la relation de Pascal $$\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}.$$

Preuve

Symétrie : choisir les $p$ éléments à garder dans un sous-ensemble revient à choisir les $n-p$ éléments à laisser de côté, donc les deux comptes sont égaux. Pascal : fixons un élément $a$ de $E$ ; un $p$-sous-ensemble soit évite $a$ (un $p$-sous-ensemble des $n-1$ autres éléments, au nombre de $\binom{n-1}{p}$), soit contient $a$ (ses $p-1$ éléments restants forment un sous-ensemble des $n-1$ autres, au nombre de $\binom{n-1}{p-1}$). Ces deux cas sont disjoints, donc par le principe d'addition le total est $\binom{n-1}{p-1} + \binom{n-1}{p}$. La relation de Pascal construit le triangle ci-dessous, chaque entrée étant la somme des deux situées juste au-dessus :

Exemple

Symétrie : $\binom{8}{3} = \binom{8}{5} = 56$ — choisir $3$ à garder, c'est choisir $5$ à laisser.
Pascal : $\binom{5}{2} = \binom{4}{1} + \binom{4}{2} = 4 + 6 = 10$.

Proposition — Nombre de parties

Un ensemble fini $E$ avec $|E| = n$ a exactement $2^n$ sous-ensembles : $$|\mathcal{P}(E)| = 2^n.$$

Preuve

Construire un sous-ensemble de $E$ revient à décider, pour chacun des $n$ éléments, s'il est dedans ou dehors — deux choix par élément. Par le principe multiplicatif le nombre de sous-ensembles est $2 \times 2 \times \dots \times 2 = 2^n$ ($n$ facteurs).

Exemple

L'ensemble $E = \{a, b, c\}$ a $2^3 = 8$ sous-ensembles : $$\emptyset, \ \{a\}, \ \{b\}, \ \{c\}, \ \{a,b\}, \ \{a,c\}, \ \{b,c\}, \ \{a,b,c\}.$$ Le regroupement par taille le confirme : $\binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 1 + 3 + 3 + 1 = 8$.

Méthode — Choisir le bon modèle de dénombrement

Face à un tirage de $p$ éléments dans un ensemble à $n$ éléments, répondre à deux questions :

L'ordre compte-t-il ? et la répétition est-elle autorisée ?

Les deux réponses sélectionnent le compte :

	avec répétition	sans répétition
ordonné	$n^p$	$A_n^p = \dfrac{n!}{(n-p)!}$
non ordonné	(non étudié)	$\binom{n}{p} = \dfrac{n!}{p!\,(n-p)!}$

La case non-ordonné-avec-répétition est laissée vide : son compte existe mais n'est pas étudié cette année. Les trois autres cases couvrent tout problème de dénombrement rencontré ici, et la question maîtresse — ordre ? répétition ? — est le réflexe à acquérir.

Signaler une erreur

Pour aller plus loin

Le dénombrement est le moteur des probabilités discrètes : lorsque les issues sont équiprobables, la probabilité d'un événement est le nombre de cas favorables divisé par le nombre total de cas — deux cardinaux à calculer. Les principes multiplicatif et d'addition et les quatre modèles de tirage seront utilisés dans tous les chapitres de probabilités à venir.

Signaler une erreur

Compétences à pratiquer

Dénombrer des sous-ensembles
Choisir le bon modèle

V Pour aller plus loin

Compétences à pratiquer

Au-delà des quatre modèles