Combinatoire élémentaire et formule du binôme de Newton

Les principes de dénombrement

Compter les éléments d’un ensemble fini est l’opération la plus élémentaire de l’arithmétique tant que l’ensemble peut être parcouru élément par élément. Cependant, quand les éléments sont les façons d’effectuer un choix composé, comme ranger dix livres sur une étagère ou choisir une délégation de trois personnes parmi trente, l’énumération devient impraticable, et le nombre s’obtient en décomposant le choix en morceaux ou en phases. Toute la combinatoire élémentaire repose sur deux principes, qui se démontrent à partir d’une définition précise de ce que signifie compter.

Compter les éléments d’un ensemble, c’est les numéroter : associer à chaque nombre de $1$ à $n$ un élément, sans en répéter aucun et sans en omettre aucun. On dit qu’un ensemble $A$ a $n$ éléments, où $n$ est un entier naturel, lorsqu’il existe une bijection de l’ensemble $\{1, 2, \ldots, n\}$ sur $A$, c’est-à-dire une fonction qui envoie des nombres distincts sur des éléments distincts et atteint tous les éléments de $A$ ; l’ensemble vide a $0$ élément, et un ensemble est fini s’il est vide ou s’il a $n$ éléments pour un certain entier naturel $n$. Les bijections, leur composition et leur réciproque sont étudiées dans la leçon sur les ensembles, relations et fonctions.

Fait admis (nombre d’éléments). On admet sans démonstration que le nombre d’éléments d’un ensemble fini est bien défini : un ensemble ne peut pas avoir à la fois $m$ éléments et $n$ éléments si $m \neq n$. On admet aussi que tout sous-ensemble d’un ensemble fini est fini.

Les deux faits se démontrent par récurrence sur $n$ ; le premier est, au fond, le principe des tiroirs, selon lequel il n’existe aucune fonction qui envoie les $n + 1$ nombres de $\{1, \ldots, n + 1\}$ sur des nombres distincts de $\{1, \ldots, n\}$. Leurs démonstrations sont longues et n’apportent aucune idée utilisée par la suite ; c’est pourquoi on les admet. Sans le premier, l’expression « le nombre d’éléments » n’aurait pas de sens, et une démonstration combinatoire, qui compte un même ensemble de deux façons, ne pourrait pas conclure que les deux résultats sont égaux.

Par récurrence sur le nombre d’ensembles réunis, le principe s’étend à toute famille finie d’ensembles deux à deux disjoints : la réunion de $A_1, \ldots, A_r$, qui ont $n_1, \ldots, n_r$ éléments, a $n_1 + \cdots + n_r$ éléments, car la réunion des $r + 1$ premiers est celle des $r$ premiers et du dernier, qui n’a aucun élément commun avec eux. On en déduit le second principe, qui compte les choix effectués par phases.

De même, par récurrence sur le nombre de phases, le principe multiplicatif s’étend à tout nombre fini de phases : un choix en $r$ phases, qui peuvent s’effectuer respectivement de $n_1, n_2, \ldots, n_r$ façons, peut s’effectuer de $n_1 n_2 \cdots n_r$ façons. Par exemple, dans le système décimal étudié dans la leçon sur les systèmes de numération de position, il y a $9 \cdot 10 \cdot 10 = 900$ nombres de trois chiffres, car le premier chiffre ne peut pas être $0$ et les deux autres sont libres. Il convient de remarquer que le principe multiplicatif exige que le nombre d’options de chaque phase ne dépende pas de ce qui a été choisi auparavant, même si les options elles-mêmes en dépendent ; si cette condition n’est pas remplie, on sépare des cas dans lesquels elle l’est et on additionne leurs résultats par le principe additif.

Les phases successives d’un choix se représentent par un arbre de dénombrement : d’un point initial, la racine, partent autant de branches que la première phase a d’options ; de l’extrémité de chaque branche, autant que la deuxième en a, et ainsi de suite. Chaque parcours de la racine à une extrémité finale, ou feuille, est un choix complet, et le principe multiplicatif compte les feuilles sans les dessiner.