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.

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. En effet, pour chaque taille $n\in \mathbb {N}$, il n'existe qu'un nombre fini de mots de taille $n$, en l'occurrence $\mathrm {card} (A)^{n}$, où $\mathrm {card} (A)$ est le nombre de lettres de $A$.

Voir aussi

• Combinatoire analytique