Ensembles, applications, dénombrement

Dénombrer, c'est compter sans énumérer. Personne ne dressera la liste des $10\,000\,000$ codes possibles d'une carte à sept chiffres : on veut le nombre, pas la liste. Tout le chapitre consiste à reconnaître, derrière un énoncé en français, laquelle de quatre situations on a sous les yeux — et l'immense majorité des erreurs de bac vient de ce diagnostic, pas du calcul qui suit.

Ensembles : le vocabulaire minimal

Un ensemble est une collection d'objets distincts, sans ordre. On note $x \in A$ l'appartenance, $A \subset B$ l'inclusion, et $\operatorname{card}(A)$ le cardinal de $A$, c'est-à-dire son nombre d'éléments.

Trois opérations et leurs cardinaux :

La première ligne est la formule du crible. Le terme soustrait n'est pas une subtilité : les éléments communs ont été comptés deux fois, une fois dans chaque ensemble, et il faut retirer ce doublon. Additionner sans retrancher est l'erreur la plus fréquente du chapitre.

La dernière ligne mérite d'être lue comme un principe multiplicatif : quand un choix se décompose en étapes indépendantes, les nombres de possibilités se multiplient. C'est de là que sortiront toutes les formules qui suivent.

Enfin, l'ensemble des parties de $E$, noté $\mathcal{P}(E)$, a pour cardinal $2^n$ si $\operatorname{card}(E) = n$ : construire une partie, c'est décider pour chaque élément s'il entre ou non — $n$ décisions binaires indépendantes.

Injection, surjection, bijection

Soit $f : E \to F$ une application.

• $f$ est injective si deux éléments distincts ont des images distinctes : personne ne partage son image. Formellement, $f(x) = f(y) \Rightarrow x = y$.
• $f$ est surjective si tout élément de $F$ est atteint : $\forall y \in F,\ \exists x \in E,\ f(x) = y$.
• $f$ est bijective si elle est les deux : chaque élément de $F$ a exactement un antécédent.

Ces trois mots ne sont pas là pour décorer : ils comptent. Si $f$ est injective, alors $\operatorname{card}(E) \leqslant \operatorname{card}(F)$ ; si elle est bijective, alors $\operatorname{card}(E) = \operatorname{card}(F)$. C'est le principe de toute la technique du dénombrement par bijection : pour compter un ensemble difficile, on le met en bijection avec un ensemble facile, et on compte celui-là.

Les quatre modèles de tirage

Tout exercice de dénombrement se ramène à tirer $p$ objets parmi $n$. Deux questions, et deux seulement, déterminent la formule.

Le tirage se fait-il avec remise ? Autrement dit, un objet peut-il apparaître plusieurs fois ? L'ordre compte-t-il ? Autrement dit, deux tirages des mêmes objets dans un ordre différent sont-ils des résultats différents ?

Les trois cases utiles se lisent l'une après l'autre, et chaque contrainte ajoutée fait chuter le compte :

Le raisonnement derrière les formules vaut mieux que les formules elles-mêmes.

Pour une $p$-liste, chaque tirage est indépendant : $n$ choix, $p$ fois de suite, donc $n^p$. Un code à $4$ chiffres, c'est $10^4 = 10\,000$ possibilités.

Pour un arrangement, le vivier diminue d'un objet à chaque tirage : $n \times (n-1) \times \cdots \times (n-p+1)$, ce qui s'écrit $\dfrac{n!}{(n-p)!}$. Le podium d'une course à $8$ concurrents : $A_8^3 = 8 \times 7 \times 6 = 336$.

Pour une combinaison, on part de l'arrangement et on corrige : chaque poignée de $p$ objets a été comptée une fois par ordre possible, c'est-à-dire $p!$ fois. On divise donc par $p!$. Un jury de $3$ personnes parmi $8$ : $C_8^3 = \dfrac{336}{6} = 56$.

Le cas $p = n$ d'un arrangement porte un nom : une permutation de $n$ objets, et il y en a $n!$.

Propriétés des combinaisons

Trois identités reviennent à chaque session, et chacune se démontre en une phrase de français plutôt qu'en une ligne de calcul.

Symétrie : $C_n^p = C_n^{\,n-p}$. Choisir les $p$ objets que l'on garde, c'est choisir les $n-p$ que l'on écarte. Une seule décision, deux façons de la décrire.

Relation de Pascal : $C_n^p = C_{n-1}^{\,p-1} + C_{n-1}^{\,p}$. Fixons un objet particulier. Ou bien il est dans la poignée — il reste $p-1$ objets à choisir parmi les $n-1$ autres — ou bien il n'y est pas — il faut alors choisir les $p$ objets parmi les $n-1$ autres. Ces deux cas sont disjoints et couvrent tout.

Cas particuliers : $C_n^0 = C_n^n = 1$ et $C_n^1 = n$. Il y a exactement une façon de ne rien choisir, ce qui justifie la convention $0! = 1$.

La relation de Pascal se lit directement dans le triangle, où chaque terme est la somme des deux qui le surmontent :

Le binôme de Newton

La formule se démontre par récurrence — c'est un exercice classique, qui utilise précisément la relation de Pascal à l'étape d'hérédité. Mais elle se comprend par le dénombrement : développer $(a+b)^n$, c'est choisir, dans chacun des $n$ facteurs, si l'on prend $a$ ou $b$. Le terme $a^p b^{\,n-p}$ apparaît autant de fois qu'il y a de façons de choisir les $p$ facteurs qui fournissent le $a$ — soit $C_n^p$ fois.

Deux conséquences immédiates, en faisant $a = b = 1$ puis $a = -1,\ b = 1$ :

La première retrouve le cardinal de $\mathcal{P}(E)$ : sommer sur toutes les tailles de parties, c'est compter toutes les parties.

Méthode : lire l'énoncé avant de calculer

La dernière ligne vaut un réflexe : les énoncés en « au moins un » se traitent presque toujours par le contraire, « aucun », qui est un seul cas au lieu d'une somme.

À vous

// Trois façons de tirer p objets parmi n, à écrire dans cet ordre.
const factorielle = (k) => (k <= 1 ? 1 : k * factorielle(k - 1));

// p-listes : avec remise, ordonné.
const pListes = (n, p) => 0;      // à corriger

// Arrangements : sans remise, ordonné — n × (n-1) × … × (n-p+1).
const arrangements = (n, p) => 0; // à corriger

// Combinaisons : sans remise, non ordonné.
const combinaisons = (n, p) => 0; // à corriger

console.log(pListes(5, 3));       // attendu : 125
console.log(arrangements(5, 3));  // attendu : 60
console.log(combinaisons(5, 3));  // attendu : 10
console.log(combinaisons(5, 2));  // attendu : 10  (symétrie)
console.log(combinaisons(10, 0)); // attendu : 1

const factorielle = (k) => (k <= 1 ? 1 : k * factorielle(k - 1));

// Chaque tirage est indépendant : n choix, p fois.
const pListes = (n, p) => n ** p;

// Le vivier diminue d'un objet à chaque tirage : c'est n! / (n-p)!,
// mais le produit se calcule directement, sans factorielle géante.
const arrangements = (n, p) => {
  let total = 1;
  for (let i = 0; i < p; i++) total *= n - i;
  return total;
};

// Chaque poignée de p objets a été comptée une fois par ordre possible,
// c'est-à-dire p! fois. On divise donc par p!.
const combinaisons = (n, p) => arrangements(n, p) / factorielle(p);

console.log(pListes(5, 3));       // 125
console.log(arrangements(5, 3));  // 60
console.log(combinaisons(5, 3));  // 10
console.log(combinaisons(5, 2));  // 10 — choisir 3 objets à garder, c'est
                                  // en choisir 2 à écarter : C(n,p) = C(n,n-p)
console.log(combinaisons(10, 0)); // 1 — il y a exactement une façon de ne
                                  // rien choisir, d'où la convention 0! = 1

À retenir