CommeUnJeu · L1 MPSI

Dénombrement

⌚ ~91 min ▢ 11 blocs ✓ 37 exercices ➣ Prérequis : Dénombrement, Formule du binôme de Newton

Le dénombrement, c'est ce que l'on fait quand on demande « combien »? À l'école on comptait sur les doigts ; au lycée on a appris les formules $n^p$, $\frac{n!}{(n-p)!}$, $\binom{n}{p}$ et on les a appliquées à des problèmes de tirage de boules. Ce chapitre fait deux choses. D'abord il rend le langage rigoureux : « combien » devient « cardinal », défini comme l'entier $n$ pour lequel il existe une bijection $\llbracket 1, n \rrbracket \to E$. Ensuite il organise les formules autour des trois modèles physiques d'un tirage --- avec remise, sans remise, simultané --- et les démontre par dénombrement direct.
Le chapitre est le pont technique vers les probabilités. Sur un univers fini équiprobable, $\mathbb{P}(A) = |A| / |\Omega|$, donc tout calcul de probabilité est un calcul de dénombrement. Le réflexe que vous devez avoir en sortant du chapitre tient en une ligne : lire l'énoncé, se demander « l'ordre compte-t-il? y a-t-il remise? », et choisir la formule. Tout le chapitre est construit pour installer ce réflexe.
Un conseil : compter, c'est énumérer, pas calculer. Quand une formule ne s'applique pas, listez ce que vous voulez compter dans un ordre réfléchi --- la formule sortira presque toujours de l'énumération.

I Cardinal d'un ensemble fini

Cette section met en place le langage des cardinaux finis. Le cardinal $|E|$ est l'entier qui répond à la question « combien d'éléments possède $E$? ». On le précise par bijection avec $\llbracket 1, n \rrbracket$, puis on étudie son comportement vis-à-vis des trois opérations qui reviennent partout dans la suite : passage à un sous-ensemble, action d'une application, combinaison d'ensembles par réunion, différence ou produit. La section se termine sur deux formules dérivées --- le cardinal d'un ensemble d'applications $F^E$ et celui d'un ensemble de parties $\mathcal{P}(E)$ --- qui constituent les briques fondamentales du reste du chapitre.

I.1 Ensemble fini$\virgule$ cardinal

Au lycée, le cardinal d'un ensemble fini, c'était « le nombre d'éléments » --- compté à la main ou par énumération. Ici on veut une définition qui ne suppose pas que l'on sache déjà compter. La manière rigoureuse est de comparer $E$ à un ensemble de référence dont on convient qu'il est « clairement de cardinal $n$ » : l'intervalle d'entiers $\llbracket 1, n \rrbracket = \{1, 2, \ldots, n\}$. Si l'on peut faire correspondre un à un les éléments de $E$ à ceux de $\llbracket 1, n \rrbracket$, alors $E$ « possède $n$ éléments ».

Définition — Ensemble fini$\virgule$ cardinal

Un ensemble $E$ est dit fini s'il est vide, ou s'il existe un entier $n \in \mathbb{N}^*$ et une bijection $\llbracket 1, n \rrbracket \to E$. Dans ce dernier cas, l'entier $n$ est unique (admis --- la théorie axiomatique de $\mathbb{N}$ est hors programme) et s'appelle le cardinal de $E$, noté $|E|$, $\mathrm{Card}(E)$ ou $\#E$. Par convention, $|\emptyset| = 0$.
Un ensemble non fini est dit infini.

Proposition — Équipotence et cardinal

Soient $E$ un ensemble fini de cardinal $n$ et $F$ un ensemble en bijection avec $E$. Alors $F$ est fini et $|F| = n$.

Preuve

Si $n = 0$, alors $E = \emptyset$, et toute bijection $E \to F$ force $F = \emptyset$, d'où $|F| = 0 = n$. Si $n \ge 1$, fixons une bijection $\varphi : \llbracket 1, n \rrbracket \to E$ et soit $\psi : E \to F$ la bijection donnée. Alors $\psi \circ \varphi : \llbracket 1, n \rrbracket \to F$ est une composée de bijections, donc une bijection. $F$ est donc fini de cardinal $n$.

Méthode — Montrer qu'un ensemble est fini de cardinal n

Pour montrer qu'un ensemble $E$ est fini de cardinal $n$, on exhibe une bijection $\llbracket 1, n \rrbracket \to E$ --- ou, ce qui revient au même, une bijection entre $E$ et un ensemble connu de cardinal $n$.

Exemple

Pour des entiers $m \le n$, l'ensemble $\llbracket m, n \rrbracket$ est fini de cardinal $n - m + 1$. En effet, $$ \llbracket 1, n - m + 1 \rrbracket \to \llbracket m, n \rrbracket, \quad k \mapsto k + m - 1 $$ est une bijection.

Compétences à pratiquer

Déterminer le cardinal d'un ensemble fini

I.2 Cardinal d'une partie$\virgule$ cas d'égalité

Deux faits sur les sous-ensembles servent à chaque étape du chapitre et au-delà. Le premier est intuitif : un sous-ensemble d'un ensemble fini est fini, de cardinal inférieur ou égal. On l'admet. Le second est le résultat-outil : si un sous-ensemble a le même cardinal que l'ensemble qui le contient, l'inclusion est en réalité une égalité. Ce second fait permet de prouver $A = B$ en vérifiant une seule inclusion plus un compte de cardinaux --- ce qui est souvent bien plus facile que vérifier les deux inclusions.

Proposition — Cardinal d'une partie et cas d'égalité

Soit $E$ un ensemble fini et $A \subset E$. Alors $A$ est fini et $|A| \le |E|$. De plus, si $|A| = |E|$, alors $A = E$.

Admis

Cette propriété intuitive du cardinal fini est admise à ce niveau (les plus intuitives sont admises).

Méthode — Montrer une égalité d'ensembles à cardinal fini

Pour montrer $A = B$ avec $A$ et $B$ finis, il suffit de montrer $$ A \subset B \quad \text{et} \quad |A| = |B|. $$ Cette astuce sert partout dans la suite : en algèbre linéaire pour montrer qu'un sous-espace de pleine dimension est l'espace tout entier, dans le groupe symétrique pour identifier des groupes finis, en théorie des déterminants pour reconnaître une base.

Exemple

Montrer que si $A \subset \llbracket 1, n \rrbracket$ est de cardinal $n$, alors $A = \llbracket 1, n \rrbracket$.

Correction

On a $A \subset \llbracket 1, n \rrbracket$ et $|A| = n = |\llbracket 1, n \rrbracket|$. Par le cas d'égalité, $A = \llbracket 1, n \rrbracket$.

Compétences à pratiquer

Calculer des cardinaux et appliquer le cas d'égalité

I.3 Effet d'une application sur le cardinal$\virgule$ tiroirs

Une injection $f : E \to F$ « recopie $E$ à l'intérieur de $F$ » : l'image $f(E)$ est une partie de $F$ en bijection avec $E$, donc $E$ « rentre dans » $F$ du point de vue du cardinal. Une surjection $f : E \to F$ « couvre $F$ depuis $E$ » : tout élément de $F$ est atteint, donc $E$ « est au moins aussi gros que » $F$. On admet ces deux faits intuitifs. Ce qui n'est pas évident --- et qui est le théorème central de la section Cardinal d'un ensemble fini --- c'est le cas d'égalité : lorsque $|E| = |F|$ sont finis égaux, les trois notions injective, surjective, bijective fusionnent en une seule. Cette fusion est un résultat-outil utilisé dans tous les raisonnements en dimension finie de la suite.

Méthode — Une injection ne peut augmenter le cardinal (admis)

Soit $f : E \to F$ une injection entre ensembles finis. Alors $|E| \le |F|$, avec égalité si et seulement si $f$ est bijective.

Méthode — Une surjection ne peut diminuer le cardinal (admis)

Soit $f : E \to F$ une surjection entre ensembles finis. Alors $|F| \le |E|$, avec égalité si et seulement si $f$ est bijective.

Theorem — Caractérisation des bijections à cardinal fini égal

Soient $E$ et $F$ deux ensembles finis tels que $|E| = |F|$, et $f : E \to F$ une application. Les trois assertions suivantes sont équivalentes :

$f$ est bijective ;
$f$ est injective ;
$f$ est surjective.

Preuve

$f$ bijective implique trivialement $f$ injective et $f$ surjective. Réciproquement :

Si $f$ est injective, la première Méthode donne $|E| \le |F|$, avec égalité ssi $f$ est bijective. Comme $|E| = |F|$ par hypothèse, le cas d'égalité force $f$ bijective.
Si $f$ est surjective, la seconde Méthode donne $|F| \le |E|$, avec égalité ssi $f$ est bijective. Comme $|E| = |F|$, le cas d'égalité force à nouveau $f$ bijective.

Les trois propriétés sont donc équivalentes.

Méthode — À cardinal fini égal$\virgule$ l'injectivité suffit

Lorsque $E$ et $F$ ont le même cardinal fini, prouver qu'une application $f : E \to F$ est bijective se réduit à prouver qu'elle est injective : la surjectivité est automatique. Ce raccourci est employé partout dans la suite (arithmétique modulaire, groupes finis, algèbre linéaire en dimension finie).

Proposition — Principe des tiroirs

Il n'existe pas d'application injective $\llbracket 1, n+1 \rrbracket \to \llbracket 1, n \rrbracket$. Autrement dit : si l'on range $n+1$ chaussettes dans $n$ tiroirs, au moins deux chaussettes se retrouvent dans le même tiroir.

Preuve

Une injection $\llbracket 1, n+1 \rrbracket \to \llbracket 1, n \rrbracket$ donnerait, par la Méthode « Une injection ne peut augmenter le cardinal », $n+1 \le n$, ce qui est absurde.

Exemple

Montrer qu'étant donnés cinq points quelconques dans un carré de côté $2$, deux d'entre eux sont à distance au plus $\sqrt{2}$.

Correction

Découpons le carré de côté $2$ en quatre sous-carrés de côté $1$ par les deux médianes.

Les quatre sous-carrés constituent les « tiroirs ». En répartissant $5$ points dans $4$ tiroirs, le principe des tiroirs donne au moins deux points dans le même sous-carré. À l'intérieur d'un carré de côté $1$, la distance maximale entre deux points est la diagonale, égale à $\sqrt{2}$. Deux des cinq points sont donc à distance au plus $\sqrt{2}$.

Compétences à pratiquer

Appliquer la caractérisation à cardinal égal et le principe des tiroirs

I.4 Opérations sur les cardinaux$\virgule$ principe des bergers

L'arithmétique des cardinaux suit deux règles pratiques. La réunion disjointe additionne : quand on a « soit le premier cas, soit le second cas » sans recouvrement, on additionne les cardinaux. Le produit cartésien multiplie : quand on a « le premier choix puis le second choix » indépendants, on multiplie. Le principe unificateur est le principe des bergers : quand chaque « berger » possède le même nombre de « moutons », le total est le nombre de bergers fois le nombre de moutons par berger. On l'énonce dans sa forme la plus puissante, à l'aide des fibres d'une application.

Proposition — Réunion disjointe

Soient $A_1, \ldots, A_n$ des ensembles finis deux à deux disjoints. Alors $A_1 \sqcup \cdots \sqcup A_n$ est fini et $$ \left| \bigsqcup_{k=1}^n A_k \right| = \sum_{k=1}^n |A_k|. $$

Preuve

Récurrence sur $n$.

Cas de base $n = 1$. Trivial : un unique ensemble $A_1$ a pour cardinal $|A_1|$.
Cas $n = 2$. Posons $a = |A_1|$, $b = |A_2|$, et choisissons des bijections $\varphi_1 : \llbracket 1, a \rrbracket \to A_1$ et $\varphi_2 : \llbracket 1, b \rrbracket \to A_2$. Définissons $\varphi : \llbracket 1, a + b \rrbracket \to A_1 \sqcup A_2$ par $\varphi(k) = \varphi_1(k)$ pour $k \le a$ et $\varphi(k) = \varphi_2(k - a)$ pour $a < k \le a + b$. La disjonction assure que $\varphi$ est une bijection, d'où $|A_1 \sqcup A_2| = a + b$.
Hérédité de $n$ à $n + 1$. Regrouper $A_1 \sqcup \cdots \sqcup A_{n+1} = (A_1 \sqcup \cdots \sqcup A_n) \sqcup A_{n+1}$ et appliquer le cas $n = 2$ (les deux blocs entre parenthèses sont disjoints par hypothèse). Puis appliquer l'hypothèse de récurrence au premier bloc.

Proposition — Réunion de deux ensembles

Pour $A$ et $B$ finis, $$ |A \cup B| = |A| + |B| - |A \cap B|. $$

Preuve

Décomposons $A \cup B$ en réunion disjointe : $$ A \cup B = A \sqcup (B \setminus A). $$ Par réunion disjointe, $|A \cup B| = |A| + |B \setminus A|$. De même, $B = (B \cap A) \sqcup (B \setminus A)$ est une décomposition disjointe, donnant $|B| = |A \cap B| + |B \setminus A|$, d'où $|B \setminus A| = |B| - |A \cap B|$. En substituant : $$ |A \cup B| = |A| + |B| - |A \cap B|. $$

Extension à trois ensembles et le crible hors programme

La même décomposition donne, pour $A$, $B$, $C$ finis : $$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|. $$ Cette formule est ponctuellement utile et peut être utilisée à l'occasion, mais elle n'est pas un attendu systématique du chapitre. La formule d'inclusion-exclusion générale --- appelée « formule du crible » --- est hors programme à ce niveau : « La formule du crible est hors programme. » Nous ne la prouverons pas, ni ne l'utiliserons systématiquement. Le seul exercice « pour aller plus loin » qui la mentionne est explicitement signalé hors programme.

Méthode — Différence et complémentaire

Pour $B \subset A$ finis, $|A \setminus B| = |A| - |B|$. En particulier, pour $A \subset E$ finis, $|A^c| = |E| - |A|$ où $A^c = E \setminus A$.

Proposition — Principe des bergers (forme avec fibres)

Soit $f : E \to F$ une application entre ensembles finis. Si toutes les fibres $f^{-1}(\{y\})$, pour $y \in F$, ont le même cardinal $p$, alors $$ |E| = p \cdot |F|. $$

Preuve

Les fibres de $f$ forment une partition de $E$ : $$ E = \bigsqcup_{y \in F} f^{-1}(\{y\}), $$ en $|F|$ paquets disjoints, chacun de cardinal $p$. Par réunion disjointe, $$ |E| = \sum_{y \in F} |f^{-1}(\{y\})| = \sum_{y \in F} p = p \cdot |F|. $$

Méthode — Image du berger

Le nom pédagogique dit tout : voyez $F$ comme l'ensemble des bergers ($y \in F$), et chaque fibre $f^{-1}(\{y\})$ comme le troupeau de moutons de ce berger. Si chaque berger a le même nombre $p$ de moutons, le total est $p$ fois le nombre de bergers. C'est la lecture multiplicative de « choisir le berger puis choisir un mouton » --- le prototype de tout calcul « puis » de la section Listes, arrangements, combinaisons.

Proposition — Réunion disjointe de paquets égaux (corollaire)

Si $A_1, \ldots, A_n$ sont deux à deux disjoints et tous de cardinal $p$, alors $$ \left| \bigsqcup_{k=1}^n A_k \right| = n \cdot p. $$

Preuve

Cas direct de la Proposition de réunion disjointe. De manière équivalente : la projection $\bigsqcup A_k \to \llbracket 1, n \rrbracket$ envoyant $x \in A_k$ sur $k$ est une application dont toutes les fibres ont pour cardinal $p$, et le principe des bergers donne $n \cdot p$.

Proposition — Produit cartésien

Soient $E_1, \ldots, E_p$ des ensembles finis. Alors $$ |E_1 \times E_2 \times \cdots \times E_p| = |E_1| \cdot |E_2| \cdots |E_p|. $$ En particulier, pour tout ensemble fini $E$ et $p \ge 1$, $$ |E^p| = |E|^p. $$

Preuve

Récurrence sur $p$.

Cas de base $p = 1$. Trivial : $|E_1| = |E_1|$.
Cas $p = 2$. On considère la projection $$ \pi : E_1 \times E_2 \to E_1, \quad (x_1, x_2) \mapsto x_1. $$ Pour tout $x_1 \in E_1$, la fibre $\pi^{-1}(\{x_1\}) = \{x_1\} \times E_2$ a pour cardinal $|E_2|$. Par le principe des bergers, $|E_1 \times E_2| = |E_2| \cdot |E_1|$.
Hérédité $p \to p + 1$. On écrit $E_1 \times \cdots \times E_p \times E_{p+1}$ comme $(E_1 \times \cdots \times E_p) \times E_{p+1}$ et on applique le cas $p = 2$ à ces deux facteurs. Puis on applique l'hypothèse de récurrence au premier facteur.

Méthode — Le slogan du chapitre

« On a SOIT ceci, SOIT cela » $\longrightarrow$ ADDITION.
« On fait ceci, PUIS cela » $\longrightarrow$ MULTIPLICATION. Lire un énoncé et reconnaître lequel de ces deux schémas s'applique est le premier réflexe de tout calcul de dénombrement.

Exemple

Combien de couples $(x, y) \in \llbracket 1, n \rrbracket^2$ vérifient $x \ne y$?

Correction

Construisons le couple en deux étapes : choisir $x$ ($n$ choix) PUIS choisir $y \ne x$ ($n - 1$ choix). Par le slogan multiplicatif, $$ \#\{(x, y) \in \llbracket 1, n \rrbracket^2 \mid x \ne y\} = n (n - 1). $$ On peut aussi raisonner par complémentaire : le nombre total de couples est $n^2$ (produit cartésien), et le nombre de couples avec $x = y$ est $n$ (la diagonale), donc $n^2 - n = n(n-1)$.

Compétences à pratiquer

Calculer des cardinaux de réunions et de produits

I.5 Cardinal de $F^E$ et de $\mathcal{P}(E)$

Deux formules tombent du calcul multiplicatif des cardinaux. L'ensemble $F^E$ de toutes les applications $E \to F$ a pour cardinal $|F|^{|E|}$ : ce n'est rien d'autre que $F^p$ déguisé, avec $p = |E|$. L'ensemble des parties $\mathcal{P}(E)$ a pour cardinal $2^{|E|}$ : une partie est décrite en disant « dedans / dehors » pour chaque élément, ce qui est une application $E \to \{0, 1\}$. Ce sont les briques sur lesquelles tous les calculs ultérieurs reposeront.

Méthode — Cardinal de $F^E$

Soient $E$ et $F$ des ensembles finis avec $E$ non vide, et écrivons $E = \{x_1, x_2, \ldots, x_p\}$ avec $p = |E|$. Une application $f : E \to F$ est entièrement déterminée par la liste de ses valeurs $$ (f(x_1), f(x_2), \ldots, f(x_p)) \in F^p. $$ Réciproquement, toute liste dans $F^p$ définit une unique application. L'application $f \mapsto (f(x_1), \ldots, f(x_p))$ est donc une bijection $F^E \to F^p$, et $$ |F^E| = |F^p| = |F|^p = |F|^{|E|}. $$ Si $E = \emptyset$, il existe une unique application $\emptyset \to F$ (l'application vide), donc $|F^\emptyset| = 1 = |F|^0$, en accord avec la formule.

Proposition — Cardinal de l'ensemble des parties

Pour $E$ un ensemble fini, $$ |\mathcal{P}(E)| = 2^{|E|}. $$

Preuve

L'application $$ \Phi : \mathcal{P}(E) \to \{0, 1\}^E, \quad A \mapsto \indicatrice_A $$ est une bijection : toute partie est déterminée par son indicatrice, et toute fonction $E \to \{0, 1\}$ est l'indicatrice d'une unique partie. Par la Méthode précédente, $$ |\mathcal{P}(E)| = |\{0, 1\}^E| = 2^{|E|}. $$

Méthode — Briques$\virgule$ compter les applications$\virgule$ compter les parties

Pour compter « toutes les applications $E \to F$ » : utiliser $|F|^{|E|}$.
Pour compter « toutes les parties de $E$ » : utiliser $2^{|E|}$.

Ces deux formules sont le réflexe dès qu'un énoncé dit « combien de fonctions \ldots » ou « combien de parties \ldots ».

Exemple

On prend $E = \{a, b, c\}$. Calculer le nombre d'applications $E \to \{0, 1\}$ et le nombre de parties de $E$. Vérifier que ces deux comptes coïncident.

Correction

Par la Méthode, $|\{0, 1\}^E| = 2^{|E|} = 2^3 = 8$ applications, et $|\mathcal{P}(E)| = 2^{|E|} = 8$ parties. Les deux comptes coïncident --- et c'est normal, puisque la bijection $A \mapsto \indicatrice_A$ identifie les parties aux applications à valeurs dans $\{0, 1\}$. La liste rend le résultat concret : les $8$ parties sont $$ \emptyset, \quad \{a\}, \{b\}, \{c\}, \quad \{a, b\}, \{a, c\}, \{b, c\}, \quad \{a, b, c\}, $$ et chacune correspond à une application $E \to \{0, 1\}$ via son indicatrice.

Compétences à pratiquer

Compter les applications et les parties

II Listes$\virgule$ arrangements$\virgule$ combinaisons

Cette seconde section est celle où l'on construit le réflexe central du chapitre. Toute question de dénombrement du type « combien de façons de tirer $p$ éléments dans un ensemble de cardinal $n$? » relève de l'un des trois modèles ci-dessous, et le modèle pertinent se choisit par deux questions binaires :

L'ordre du tirage compte-t-il?
Remet-on chaque élément après l'avoir tiré?

Les trois cas résultants --- $p$-liste (avec ordre, avec remise), $p$-arrangement (avec ordre, sans remise), $p$-combinaison (sans ordre, sans remise) --- donnent trois formules : $n^p$, $\frac{n!}{(n-p)!}$, $\binom{n}{p}$. Le quatrième cas (sans ordre, avec remise) est hors programme. La sous-section Synthèse --- les trois modèles fondamentaux clôture par le tableau récapitulatif à trois lignes ; le reste de la section construit les formules modèle par modèle.

II.1 Énumérer pour compter

Avant toute formule, un peu de méthode. Compter, c'est en dernier ressort énumérer : on choisit un ordre réfléchi, on parcourt un par un les objets que l'on veut compter, et on lit le total. Les formules des sous-sections p-listes (avec remise) à p-combinaisons et coefficients binomiaux sont des raccourcis qui court-circuitent l'énumération dans des cas reconnaissables --- mais quand aucune formule ne s'applique, l'énumération est le filet de sécurité, et énumérer dans un ordre réfléchi suffit souvent à produire la formule au fil de l'eau.

Méthode — Recette en trois étapes

COMPTER, C'EST ÉNUMÉRER / CONSTRUIRE. Un problème de dénombrement se résout en trois mouvements :

Identifier : quel est l'ensemble des objets que l'on veut compter? Le nommer.
Représenter : encoder chaque objet par une structure de données concrète (un mot, une liste, une partie, un chemin, un uplet).
Décomposer : découper la construction en choix successifs --- ADDITION pour SOIT/SOIT, MULTIPLICATION pour PUIS.

Exemple

Lister les parties de $\llbracket 1, 3 \rrbracket$ en ordre lexicographique, par cardinal croissant. Vérifier qu'il y en a $2^3 = 8$.

Correction

Par cardinal croissant, puis par ordre alphabétique sur les éléments : $$ \emptyset, \quad \{1\}, \quad \{2\}, \quad \{3\}, \quad \{1, 2\}, \quad \{1, 3\}, \quad \{2, 3\}, \quad \{1, 2, 3\}. $$ Soit $1 + 3 + 3 + 1 = 8 = 2^3$ parties, conformément à $|\mathcal{P}(E)| = 2^{|E|}$.

Compétences à pratiquer

Compter de petits ensembles par énumération

II.2 $p$-listes (avec remise)

Une $p$-liste est l'objet combinatoire le plus simple : un uplet ordonné de $p$ éléments tirés dans $E$, avec répétitions autorisées. Le modèle physique est le tirage de boules vu au lycée, avec ordre et avec remise : on tire une boule, on note son numéro, on la remet, on retire, etc. La formule est la plus propre du chapitre --- $n^p$ --- et ce n'est rien d'autre que $|E^p|$ de la sous-section Opérations sur les cardinaux, principe des bergers dans un autre langage.

Définition — $p$-liste

Pour $p \ge 1$, une $p$-liste (ou $p$-uplet) de $E$ est un élément de $E^p$, c'est-à-dire un uplet ordonné $(y_1, \ldots, y_p)$ avec chaque $y_i \in E$. Les répétitions sont autorisées : on peut avoir $y_i = y_j$ pour $i \ne j$.
Par convention, il existe une unique $0$-liste de $E$ : l'uplet vide. Les formules ci-dessous restent valables pour $p = 0$ avec $n^0 = 1$.

Méthode — Nombre de $p$-listes

Pour $|E| = n$ et $p \ge 0$, il y a $$ n^p $$ $p$-listes de $E$. C'est la formule du produit cartésien $|E^p| = |E|^p$ de la sous-section Opérations sur les cardinaux, principe des bergers, rebaptisée (avec $E^0$ singleton, l'uplet vide). Modèle pratique : tirages successifs avec remise.

Méthode — Lien avec les applications

Une $p$-liste $(y_1, \ldots, y_p)$ de $F$ est la même donnée qu'une application $\llbracket 1, p \rrbracket \to F$ définie par $i \mapsto y_i$. La formule $|F|^p$ pour les $p$-listes est donc la même que la formule $|F|^{|E|}$ pour les applications $E \to F$ avec $|E| = p$.

Exemple

Combien de mots de $5$ lettres peut-on former sur l'alphabet latin ($26$ lettres)?

Correction

Un mot de $5$ lettres sur un alphabet de $26$ lettres est une $5$-liste de l'alphabet (avec remise, puisque les lettres peuvent se répéter). Le compte est $$ 26^5 = 11\,881\,376. $$

Exemple

Combien de codes PIN à $4$ chiffres peut-on former sur les chiffres de $0$ à $9$?

Correction

Un code PIN à $4$ chiffres est une $4$-liste sur l'ensemble des chiffres $\llbracket 0, 9 \rrbracket$ (avec remise : un chiffre peut être réutilisé). Le compte est $$ 10^4 = 10\,000. $$

Compétences à pratiquer

Compter mots et codes (avec remise)

II.3 $p$-arrangements$\virgule$ permutations$\virgule$ injections

Un $p$-arrangement est une $p$-liste avec la contrainte supplémentaire que tous les éléments sont distincts. Le modèle physique est le tirage de boules avec ordre et sans remise : on tire une boule, on l'écarte, on retire-en une autre différente, etc. La formule --- le produit décroissant $n(n-1) \cdots (n-p+1)$ --- vient du slogan multiplicatif avec un nombre de choix disponibles diminuant de $1$ à chaque étape. La forme factorielle $\frac{n!}{(n-p)!}$ est le même nombre, regroupé. Le cas particulier $p = n$ donne le nombre de permutations de $E$, soit $n!$. Et parce qu'interdire les répétitions dans la suite revient à interdire $f(i) = f(j)$ dans l'application correspondante, la même formule compte le nombre d'applications injectives $\llbracket 1, p \rrbracket \to E$.

Définition — $p$-arrangement

Pour $p \ge 1$, un $p$-arrangement de $E$ est une $p$-liste de $E$ dont tous les éléments sont distincts.
Par convention, l'uplet vide est l'unique $0$-arrangement ; la formule ci-dessous reste valable pour $p = 0$ avec $\frac{n!}{n!} = 1$.

Proposition — Nombre de $p$-arrangements

Soit $|E| = n$ et $1 \le p \le n$. Le nombre de $p$-arrangements de $E$ est $$ n (n-1) (n-2) \cdots (n-p+1) = \frac{n!}{(n-p)!}. $$ Pour $p > n$, il n'y a pas de $p$-arrangement de $E$ (le compte vaut $0$).

Preuve

Construisons un $p$-arrangement étape par étape.

Étape $1$ : choisir $y_1 \in E$ --- $n$ choix possibles.
Étape $2$ : choisir $y_2 \in E$ avec $y_2 \ne y_1$ --- $n - 1$ choix.
Étape $k$ ($1 \le k \le p$) : choisir $y_k \in E$ distinct de $y_1, \ldots, y_{k-1}$ --- $n - (k-1) = n - k + 1$ choix.

Par le slogan multiplicatif « PUIS $\to \times$ » itéré $p$ fois, $$ \#\{p\text{-arrangements de } E\} = n \cdot (n-1) \cdots (n-p+1) = \frac{n \cdot (n-1) \cdots 1}{(n-p) \cdot (n-p-1) \cdots 1} = \frac{n!}{(n-p)!}. $$ Pour $p > n$, l'étape $n+1$ n'a aucun élément disponible ($0$ choix), donc le compte vaut $0$.

Définition — Permutation

Une permutation d'un ensemble fini $E$ est une bijection $E \to E$. L'ensemble des permutations de $E$ est noté $\mathfrak{S}_E$ (ou $\mathfrak{S}_n$ lorsque $E = \llbracket 1, n \rrbracket$).

Proposition — Nombre de permutations

Pour $|E| = n$, $$ |\mathfrak{S}_E| = n\,! $$

Preuve

Une permutation de $E$ est en particulier une injection $E \to E$ ; par le Théorème central de la sous-section Effet d'une application sur le cardinal, tiroirs, en cardinal fini égal $|E| = |E|$, une injection est automatiquement bijective. Donc les permutations sont exactement les $n$-arrangements de $E$. La Proposition précédente donne $\frac{n!}{(n-n)!} = \frac{n!}{0!} = n!$.

Proposition — Nombre d'applications injectives

Soient $E$ et $F$ des ensembles finis avec $|E| = p$ et $|F| = n$. Le nombre d'applications injectives $E \to F$ est $$ \frac{n!}{(n-p)!} \quad \text{si } p \le n, \qquad 0 \quad \text{si } p > n. $$

Preuve

Écrivons $E = \{x_1, \ldots, x_p\}$. Comme dans la Méthode de la sous-section Cardinal de $F^E$ et de $\mathcal{P}(E)$, une application $E \to F$ s'identifie à la liste $(f(x_1), \ldots, f(x_p)) \in F^p$. L'application est injective si et seulement si toutes les valeurs $f(x_i)$ sont distinctes, c'est-à-dire si et seulement si la liste correspondante est un $p$-arrangement de $F$. Par la Proposition précédente, le compte vaut $\frac{n!}{(n-p)!}$ pour $p \le n$, $0$ sinon.

Méthode — Sans-remise $\Leftrightarrow$ injection $\Leftrightarrow$ permutation

Le même nombre $\frac{n!}{(n-p)!}$ compte trois objets : les $p$-arrangements d'un ensemble à $n$ éléments, les applications injectives d'un $p$-ensemble dans un $n$-ensemble, et (quand $p = n$) les permutations d'un $n$-ensemble. Reconnaître l'une de ces trois formes dans un énoncé donne immédiatement la formule.

Exemple

De combien de façons peut-on tirer $5$ cartes successivement sans remise dans un jeu de $52$ cartes?

Correction

C'est le nombre de $5$-arrangements d'un ensemble à $52$ éléments : $$ \frac{52\,!}{(52 - 5)\,!} = \frac{52\,!}{47\,!} = 52 \cdot 51 \cdot 50 \cdot 49 \cdot 48. $$

Exemple

De combien de façons peut-on asseoir $n$ personnes sur un banc rectiligne? Autour d'une table ronde?

Correction

Banc rectiligne. Numérotons les $n$ places de gauche à droite. Asseoir $n$ personnes revient à se donner un $n$-arrangement de $\{1, \ldots, n\}$ pour les places, c'est-à-dire une permutation. Total : $n!$ placements.
Table ronde. La convention doit être explicite :
- Si les places sont numérotées (chaque chaise a sa propre identité), la table ronde se comporte comme le banc rectiligne : $n!$ placements.
- Si deux placements qui ne diffèrent que par une rotation sont considérés identiques (la table ronde sans repère), on fixe la position d'une personne donnée --- disons la personne $n$ --- et on assoit les $n - 1$ autres sur les $n - 1$ places restantes. Total : $(n - 1)!$ placements.

Le facteur $n$ entre les deux comptes est exactement le nombre de rotations qui identifient les configurations sur la table ronde sans repère.

Compétences à pratiquer

Compter anagrammes$\virgule$ placements et permutations contraintes

II.4 $p$-combinaisons et coefficients binomiaux

Une $p$-combinaison est une partie de $E$ de cardinal $p$ : les éléments sont rassemblés en ensemble, sans notion d'ordre. Le modèle physique est le tirage simultané : on attrape d'un coup une poignée de $p$ boules dans le sac. Le nombre de $p$-combinaisons d'un $n$-ensemble est le coefficient binomial $\binom{n}{p}$. Nous avons déjà rencontré $\binom{n}{p}$ dans le chapitre $\mathrm{CalculAlgebrique}$ comme l'expression algébrique $\frac{n!}{p!(n-p)!}$ ; ici on le redéfinit combinatoirement, puis on prouve l'équivalence avec l'expression factorielle par double comptage. Les identités classiques --- symétrie, Pascal, formule du capitaine --- se démontrent toutes par double comptage, technique signature du chapitre.

Définition — Coefficient binomial (combinatoire)

Pour $n \in \mathbb{N}$ et $p \in \mathbb{Z}$, le coefficient binomial $\binom{n}{p}$ est le cardinal de l'ensemble des parties à $p$ éléments de $\llbracket 1, n \rrbracket$ : $$ \binom{n}{p} = \big| \mathcal{P}_p(\llbracket 1, n \rrbracket) \big| \quad \text{où} \quad \mathcal{P}_p(F) = \{ A \subset F \mid |A| = p \}. $$ On utilise la convention usuelle $\llbracket 1, 0 \rrbracket = \emptyset$. Conséquences immédiates :

$\binom{n}{p} = 0$ pour $p < 0$ ou $p > n$ (aucune partie de cardinal hors $[0, n]$).
$\binom{n}{0} = 1$ pour tout $n \ge 0$ (la seule partie de cardinal $0$ est $\emptyset$).
$\binom{n}{n} = 1$ pour tout $n \ge 0$ (la seule partie de cardinal $n$ est $\llbracket 1, n \rrbracket$).
$\binom{0}{0} = 1$ : la seule partie de $\emptyset$ de cardinal $0$ est $\emptyset$.

Définition — $p$-combinaison

Pour $p \ge 0$, une $p$-combinaison de $E$ est une partie de $E$ de cardinal $p$. L'ensemble des $p$-combinaisons de $E$ est noté $\mathcal{P}_p(E)$.

Proposition — Cardinal de $\mathcal{P}_p(E)$

Pour $|E| = n$, $$ |\mathcal{P}_p(E)| = \binom{n}{p}. $$

Preuve

Choisissons une bijection $\varphi : \llbracket 1, n \rrbracket \to E$. L'application induite $$ \Phi : \mathcal{P}_p(\llbracket 1, n \rrbracket) \to \mathcal{P}_p(E), \quad X \mapsto \varphi(X) $$ est une bijection : elle envoie une partie de cardinal $p$ sur une partie de cardinal $p$ (car $\varphi$ étant bijective, $|\varphi(X)| = |X|$), et sa réciproque est $Y \mapsto \varphi^{-1}(Y)$. Donc $|\mathcal{P}_p(E)| = |\mathcal{P}_p(\llbracket 1, n \rrbracket)| = \binom{n}{p}$.

Theorem — Expression factorielle de $\binom{n}{p}$

Pour des entiers $0 \le p \le n$, $$ \binom{n}{p} = \frac{n\,!}{p\,! \, (n - p)\,!}. $$

Preuve

On compte les $p$-arrangements de $\llbracket 1, n \rrbracket$ de deux manières.

Premier compte. Par la formule de la sous-section p-arrangements, permutations, injections, $$ \#\{p\text{-arrangements de } \llbracket 1, n \rrbracket\} = \frac{n!}{(n-p)!}. $$
Second compte. Un $p$-arrangement se construit en deux étapes :
- Choisir la $p$-combinaison sous-jacente (l'ensemble des valeurs apparaissant) --- $\binom{n}{p}$ choix.
- Ordonner cet ensemble en une suite --- $p\,!$ choix (une permutation d'un ensemble à $p$ éléments).
Par le slogan multiplicatif, $$ \#\{p\text{-arrangements de } \llbracket 1, n \rrbracket\} = \binom{n}{p} \cdot p\,! $$

En égalant les deux comptes : $$ \binom{n}{p} \cdot p\,! = \frac{n\,!}{(n - p)\,!} \quad \text{d'où} \quad \binom{n}{p} = \frac{n\,!}{p\,! \, (n - p)\,!}. $$ C'est l'équivalence explicite avec la définition algébrique donnée dans $\mathrm{CalculAlgebrique}$.

Proposition — Symétrie

Pour $0 \le p \le n$, $$ \binom{n}{p} = \binom{n}{n - p}. $$

Preuve

Démonstration combinatoire par complémentation. L'application $$ \mathcal{P}_p(\llbracket 1, n \rrbracket) \to \mathcal{P}_{n-p}(\llbracket 1, n \rrbracket), \quad A \mapsto A^c = \llbracket 1, n \rrbracket \setminus A $$ est une bijection (sa réciproque est elle-même, puisque $(A^c)^c = A$). Donc les deux ensembles ont le même cardinal, soit $\binom{n}{p} = \binom{n}{n - p}$.

Proposition — Formule de Pascal

Pour $1 \le p \le n + 1$, avec la convention $\binom{n}{p} = 0$ pour $p > n$, $$ \binom{n}{p - 1} + \binom{n}{p} = \binom{n + 1}{p}. $$

Preuve

Démonstration combinatoire. On compte les parties de cardinal $p$ de $\llbracket 1, n + 1 \rrbracket$ --- il y en a $\binom{n+1}{p}$. On les sépare en deux familles disjointes selon qu'elles contiennent ou non l'élément distingué $n + 1$ :

Parties de cardinal $p$ contenant $n + 1$ : retirer $n + 1$ donne une partie de cardinal $p - 1$ de $\llbracket 1, n \rrbracket$. Ceci induit une bijection avec $\mathcal{P}_{p-1}(\llbracket 1, n \rrbracket)$, soit $\binom{n}{p-1}$ telles parties.
Parties de cardinal $p$ ne contenant pas $n + 1$ : ce sont exactement les parties de cardinal $p$ de $\llbracket 1, n \rrbracket$, donc $\binom{n}{p}$ d'entre elles.

Par le slogan additif, $\binom{n+1}{p} = \binom{n}{p-1} + \binom{n}{p}$.
Forme équivalente. Le ré-indiçage $p \to p+1$ donne la forme souvent rencontrée dans les manuels : $$ \binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}. $$

Proposition — Formule du capitaine

Pour $1 \le p \le n$, $$ p \cdot \binom{n}{p} = n \cdot \binom{n - 1}{p - 1}. $$

Preuve

Démonstration combinatoire. On compte les couples (équipe de $p$ joueurs parmi $n$, capitaine désigné dans l'équipe) de deux façons.

Premier compte. On choisit l'équipe d'abord ($\binom{n}{p}$ choix), puis on désigne le capitaine dans l'équipe ($p$ choix). Total : $p \cdot \binom{n}{p}$.
Second compte. On choisit le capitaine d'abord ($n$ choix), puis on complète l'équipe avec $p - 1$ joueurs parmi les $n - 1$ non-capitaines ($\binom{n-1}{p-1}$ choix). Total : $n \cdot \binom{n-1}{p-1}$.

Les deux comptes coïncident, d'où l'identité.

Méthode — Combinaisons $\Leftrightarrow$ tirages simultanés

Quand l'énoncé dit « tirage simultané » ou « sous-ensemble de taille $p$ », le modèle est la $p$-combinaison ; la formule est $\binom{n}{p}$. La marque : l'ordre ne compte pas.

Exemple

De combien de façons peut-on tirer $5$ cartes simultanément dans un jeu de $52$ cartes?

Correction

L'ordre ne compte pas ; le modèle est une $5$-combinaison d'un ensemble à $52$ éléments. Total : $\binom{52}{5}$.

Exemple

Calculer le nombre d'anagrammes du mot BOROROS.

Correction

Le mot $\mathrm{BOROROS}$ a $7$ lettres avec multiplicités : $\mathrm{O}$ apparaît $3$ fois, $\mathrm{R}$ apparaît $2$ fois, $\mathrm{B}$ une fois, $\mathrm{S}$ une fois. On donne deux méthodes.
Méthode 1 : placer chaque lettre dans ses positions.

Choisir les $3$ positions des $\mathrm{O}$ parmi $7$ : $\binom{7}{3}$ façons.
Choisir les $2$ positions des $\mathrm{R}$ parmi les $4$ restantes : $\binom{4}{2}$ façons.
Choisir la position du $\mathrm{B}$ parmi les $2$ restantes : $\binom{2}{1}$ façons.
La dernière position est forcée pour le $\mathrm{S}$ : $\binom{1}{1} = 1$.

Par le slogan multiplicatif, $$ \binom{7}{3} \binom{4}{2} \binom{2}{1} \binom{1}{1} = 35 \cdot 6 \cdot 2 \cdot 1 = 420. $$ Méthode 2 : numéroter puis quotienter. Si l'on distinguait artificiellement les $7$ lettres, il y aurait $7\,!$ permutations. Mais les lettres identiques sont interchangeables : les $3\,!$ permutations des $\mathrm{O}$ et les $2\,!$ des $\mathrm{R}$ produisent le même anagramme. Donc $$ \#\{\text{anagrammes de BOROROS}\} = \frac{7\,!}{3\,! \cdot 2\,!} = \frac{5040}{12} = 420. $$

Compétences à pratiquer

Compter parties$\virgule$ comités et chemins de grille

II.5 Démonstration combinatoire de la formule du binôme

Le chapitre $\mathrm{CalculAlgebrique}$ a prouvé la formule du binôme $(a+b)^n = \sum_{k} \binom{n}{k} a^k b^{n-k}$ par récurrence sur $n$, à l'aide de l'identité de Pascal. Ici on donne une preuve combinatoire : compter d'où vient le terme $a^k b^{n-k}$ dans le développement. C'est exactement le type d'argument de double comptage mis en pratique dans la sous-section précédente.

Theorem — Formule du binôme$\virgule$ preuve combinatoire

Pour $a, b$ dans un anneau commutatif (en particulier pour $a, b \in \mathbb{R}$ ou $\mathbb{C}$) et $n \in \mathbb{N}$, $$ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n - k}. $$

Preuve

On écrit $$ (a + b)^n = \underbrace{(a + b)(a + b) \cdots (a + b)}_{n \text{ facteurs}}. $$ On développe entièrement. Chaque terme du développement correspond à un choix « prendre $a$ ou prendre $b$ » dans chacun des $n$ facteurs. Le terme obtenu en prenant $a$ dans exactement $k$ des facteurs (et $b$ dans les $n - k$ autres) est $$ a^k b^{n - k}. $$ Le nombre de tels choix est le nombre de façons de sélectionner les $k$ facteurs qui fournissent le $a$, c'est-à-dire le nombre de $k$-combinaisons de l'ensemble des $n$ facteurs : $$ \binom{n}{k}. $$ En sommant sur $k = 0, 1, \ldots, n$ on rassemble tous les termes du développement : $$ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n - k}. $$ Forme équivalente. Par symétrie $\binom{n}{k} = \binom{n}{n-k}$, le changement $k \to n - k$ dans la somme donne l'expression équivalente $\sum_k \binom{n}{k} a^{n - k} b^k$, souvent rencontrée dans les manuels. Les deux sont la même identité.

Méthode — Double comptage pour les identités binomiales

Pour démontrer une identité entre coefficients binomiaux, chercher un ensemble unique que les deux membres comptent de deux façons différentes. Cette technique couvre à elle seule : la symétrie $\binom{n}{p} = \binom{n}{n-p}$ (compter les parties vs compter leurs complémentaires), Pascal $\binom{n+1}{p} = \binom{n}{p-1} + \binom{n}{p}$ (parties contenant ou non un élément distingué), le capitaine $p\binom{n}{p} = n\binom{n-1}{p-1}$ (équipe-puis-capitaine vs capitaine-puis-équipe), et la formule du binôme (quels facteurs donnent le $a$).

Boucle de retour vers $|\mathcal{P}(E)| \equal 2^n$

Une seconde preuve de la formule $|\mathcal{P}(E)| = 2^n$ tombe de la formule du binôme. Appliquons la formule du binôme à $a = b = 1$ : $$ 2^n = (1 + 1)^n = \sum_{k=0}^n \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^n \binom{n}{k}. $$ D'autre part, $\mathcal{P}(E) = \bigsqcup_{k=0}^n \mathcal{P}_k(E)$ est une réunion disjointe par cardinal, donc $$ |\mathcal{P}(E)| = \sum_{k=0}^n |\mathcal{P}_k(E)| = \sum_{k=0}^n \binom{n}{k} = 2^n. $$ On retrouve --- par une route complètement différente --- le résultat de la sous-section Cardinal de $F^E$ et de $\mathcal{P}(E)$ démontré là-bas via les indicatrices.

Exemple

Calculer la somme alternée $\displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}$ pour $n \ge 1$.

Correction

Appliquons la formule du binôme à $a = -1$, $b = 1$ : $$ \begin{aligned} 0 = 0^n = (-1 + 1)^n &= \sum_{k=0}^n \binom{n}{k} (-1)^k 1^{n-k} \\ &= \sum_{k=0}^n (-1)^k \binom{n}{k}. \end{aligned} $$ D'où $\displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} = 0$ pour $n \ge 1$. Pour $n = 0$, la somme se réduit à son unique terme $k = 0$, donc elle vaut $\binom{0}{0} = 1$ : c'est la convention du produit vide dans la formule du binôme.

Compétences à pratiquer

Démontrer des identités par double comptage et substitution binomiale

II.6 Synthèse --- les trois modèles fondamentaux

Tout le chapitre --- une fois les preuves effacées --- se résume en un tableau. Les trois modèles fondamentaux se classent par deux critères binaires : l'ordre compte-t-il, et y a-t-il remise? Les cardinaux correspondants sont $n^p$, $\frac{n!}{(n-p)!}$ et $\binom{n}{p}$. Lire un énoncé et le rattacher à l'une des trois lignes est le réflexe central du chapitre.

Méthode — Les trois modèles --- tableau récapitulatif

Pour tirer $p$ éléments dans un ensemble de cardinal $n$, les trois modèles standard sont :

Type de tirage	Ordre	Remise	Modèle	Cardinal
Successif, avec remise	oui	oui	$p$-liste de $E$	$n^p$
Successif, sans remise	oui	non	$p$-arrangement de $E$	$\dfrac{n\,!}{(n-p)\,!}$
Simultané	non	non	$p$-combinaison de $E$	$\dbinom{n}{p}$

Méthode — Lire l'énoncé

Face à un problème de dénombrement, poser les deux questions binaires :

L'ordre compte-t-il?
Y a-t-il remise?

On choisit ensuite le modèle :

L'ordre compte et il y a remise : $p$-liste, cardinal $n^p$.
L'ordre compte et il n'y a pas remise : $p$-arrangement, cardinal $\dfrac{n!}{(n-p)!}$ si $p \le n$, $0$ sinon.
L'ordre ne compte pas et il n'y a pas remise : $p$-combinaison, cardinal $\binom{n}{p}$.
L'ordre ne compte pas et il y a remise : multi-ensembles / bâtons-boules --- hors programme.

Compétences à pratiquer

Choisir liste$\virgule$ arrangement ou combinaison à partir de l'énoncé