Classe combinatoire

En mathématiques, et plus précisément en combinatoire, une classe combinatoire est un ensemble d'objets dont on connaît la taille, donnée par un entier. Bien qu'il puisse y avoir un nombre infini d'objets, le nombre d'objets d'une taille donnée doit toujours être fini.

Définition formelle

Une classe combinatoire est par définition un ensemble $A$ muni d'une application $|\cdot |:A\to \mathbb {N}$ appelée taille qui, à chaque élément $a$ de l'ensemble $A$ associe un entier naturel $|a|$. On demande de plus que, pour chaque $n$, le nombre d'éléments de taille $n$ est fini.

Suite de comptage

La suite de comptage d'une classe combinatoire est la suite qui, à une taille donnée $n\in \mathbb {N}$, associe le nombre d'éléments $a\in A$ de taille $n$. Autrement dit, c'est la suite $c_{n\in \mathbb {N} }$ définie par

$c_{n}=\mathrm {card} \{a\in A,|a|=n\}$

Les suites de comptage sont l'un des principaux objets d'études de la combinatoire énumérative. On dit que deux classes de comptage sont isomorphes lorsqu'elles ont la même suite de comptage. En combinatoire, on cherche fréquemment à mettre en relation des classes combinatoires qui, au premier abord, désignent des objets mathématiques complètement différents, mais qui ont la même suite de comptage. On parle alors de cryptomorphisme.

Exemples

• L'ensemble des listes de mots $A^{*}$ sur un alphabet $A$ muni de la fonction $|\cdot |:A^{*}\to \mathbb {N}$ qui, à tout mot $w\in A^{*}$, associe sa longueur $|w|$ forme une classe combinatoire dont la suite de comptage est $c_{n}=\mathrm {card} (A)^{n}$, avec $\mathrm {card} (A)$ est le nombre de lettres de $A$. Autrement dit, il existe $\mathrm {card} (A)^{n}$ mots de taille $n$.

Voir aussi

• Combinatoire analytique