dénombrement

Un cadenas accepte des codes de trois chiffres, chaque chiffre étant choisi parmi 1, 2, 3 et 4. Écrire les 64 codes un par un serait possible, mais le dénombrement permet d'obtenir ce total sans dresser toute la liste.

Chaque position offre quatre choix, et un chiffre peut revenir. Il y a donc 4 × 4 × 4 = 64 codes. On multiplie parce que tout choix du premier chiffre peut être suivi de chacun des choix du deuxième, puis du troisième.

Le dénombrement détermine le cardinal, c'est-à-dire le nombre d'éléments, d'un ensemble fini. Le comptage direct énumère les objets. Un arbre de choix représente les décisions successives. Une partition découpe l'ensemble en sous-ensembles deux à deux disjoints dont la réunion redonne l'ensemble entier. Le principe additif additionne alors leurs cardinaux. Le principe multiplicatif multiplie les nombres de choix de plusieurs étapes lorsque leur nombre, à chaque étape, reste le même quels que soient les choix précédents.

Soit un ensemble de n éléments, avec n au moins égal à 1, et un entier p positif ou nul. Une p-liste est une suite ordonnée de p éléments, avec répétition autorisée : il y en a $n^{p}n^p$. Lorsque p est inférieur ou égal à n, un arrangement est une suite ordonnée de p éléments distincts : il y en a $\frac{n!}{(n-p)!}\backslash frac\{n!\}\{(n-p)!\}$. Une combinaison est une sélection non ordonnée de p éléments distincts : il y en a $\left(\genfrac{}{}{0px}{}{n}{p}\right)=\frac{n!}{p!(n-p)!}\backslash binom\{n\}\{p\}=\backslash frac\{n!\}\{p!(n-p)!\}$.

Une permutation ordonne tous les éléments : c'est un arrangement avec p = n, et il y en a n!. Pour choisir la bonne formule, deux questions suffisent souvent : l'ordre compte-t-il, et la répétition est-elle autorisée ? Si les choix possibles varient selon les étapes, un arbre ou une partition évite d'appliquer mécaniquement une formule inadaptée.

Un cadenas utilise un code de trois chiffres choisis parmi 1, 2, 3 et 4. L'ordre compte : 123 et 321 sont deux codes différents. La répétition est autorisée : 111 est donc admis. Le schéma condense l'arbre des choix en montrant quatre branches possibles à chacune des trois positions.

Données.
Longueur du code : 3 chiffres.
Chiffres disponibles : {1, 2, 3, 4}.
Répétition : autorisée.
Ordre : pris en compte.

Étape 1. La première position peut recevoir l'un des quatre chiffres : elle offre 4 choix.

Étape 2. Quel que soit le premier chiffre, la deuxième position offre encore 4 choix, puisque la répétition est autorisée.

Étape 3. La troisième position offre elle aussi 4 choix. Le principe multiplicatif donne :

Il existe donc exactement 64 codes. Contrôle. Pour chacun des 4 premiers chiffres, les deux positions restantes forment 4 × 4 = 16 fins possibles ; 4 groupes de 16 donnent bien 64.

Pour compter des codes ou des mots de longueur fixée, on examine d'abord si les positions sont ordonnées et si un symbole peut revenir. Avec répétition, une p-liste convient ; sans répétition, on choisit un arrangement.

Pour former un groupe, l'ordre de sélection n'a généralement pas d'effet : choisir Alice, Bilal et Chloé donne le même groupe dans n'importe quel ordre. Une combinaison évite alors de compter plusieurs fois la même sélection.

Lorsque les cas s'excluent, on les sépare puis on additionne leurs nombres. Lorsque plusieurs choix successifs composent chaque résultat, on multiplie. Si le nombre de choix dépend des décisions précédentes, un arbre permet de compter branche par branche.

Arrangement et combinaison. Dans un arrangement, l'ordre compte ; dans une combinaison, il ne compte pas. Avec les chiffres 1, 2 et 3 pris deux à deux, 12 et 21 sont deux arrangements, mais ils représentent la même combinaison {1, 2}.

p-liste et arrangement. Les deux objets sont ordonnés, mais la p-liste autorise les répétitions. Le code 111 appartient aux codes du cadenas ; il ne serait pas un arrangement de trois chiffres distincts.

Dénombrement et probabilité. Le dénombrement calcule combien d'issues existent. Une probabilité attribue un poids à un événement. Diviser les cas favorables par tous les cas n'est valable que lorsque les issues élémentaires sont équiprobables.

Des cas qui se chevauchent ne s'additionnent pas directement. Si un même objet appartient à deux catégories, la somme le compte deux fois. Il faut rendre les cas disjoints ou corriger le chevauchement avant d'appliquer le principe additif.

Un produit suppose des étapes correctement décrites. Pour le cadenas, chaque position offre toujours 4 choix. Si un chiffre était interdit après lui-même, le nombre de choix passerait de 4 à 3 après la première position ; le produit 4³ ne conviendrait plus.

Diviser par un nombre de permutations exige une symétrie réelle. On divise les arrangements par p! pour obtenir les combinaisons parce que chaque sélection de p éléments distincts possède exactement p! ordres. Si les objets se répètent ou si certains ordres sont interdits, cette multiplicité peut changer.

Le cas vide compte. Il existe une unique sélection de zéro élément et une unique permutation de l'ensemble vide. La convention 0! = 1 maintient ainsi les formules cohérentes aux cas charnières p = 0 et n = 0.

Analyse combinatoire — Situer les techniques de dénombrement dans l'étude plus large des configurations finies.

La combinatoire, hier et aujourd'hui Entretien avec Pierre Duchet — Découvrir comment le champ de la combinatoire s'est élargi et quelles questions l'animent.