Classes et objets combinatoires

Classes combinatoires

L’un des concepts fondamentaux en combinatoire est le dénombrement. Il sert à énumérer un ensemble fini ou même un ensemble infini muni d’une notion de taille telle que pour tout entier naturel n le nombre d’objets de taille n est fini. Définition 1.1.1. Une classe combinatoire est un ensemble C muni d’une application appelée taille | · | : C → N qui associe à chaque élément c de C un entier naturel |c|. On demande de plus que, pour chaque entier naturel n, le nombre d’éléments de taille n de C soit fini. Exemple 1.1.2. L’ensemble des mots d’un alphabet fini muni de l’application taille longueur du mot est une classe combinatoire. Si on considère l’ensemble des mots sur 2 lettres muni de cette même application taille, alors, pour tout entier n > 0, il y a 2 n mots de taille n. D’autres exemples de classes combinatoires sont l’ensemble des entiers naturels ayant pour taille leur valeur, les chemins sur un graphe donné ayant pour taille leur longueur, les pavages par un ensemble de tuiles donné d’une surface finie où la taille est celle de cette surface, les urnes composées de boules noires et blanches où la taille est le nombre de boules . . . Remarque 1.1.3. Un ensemble peut être doté de plusieurs tailles différentes. Disposant d’une classe combinatoire, on cherche à calculer le nombre d’objets de taille n pour tout entier n. Idéalement, on espère trouver une formule close en fonction de n, mais l’existence d’une telle formule n’est pas garantie. Une des techniques de base pour traiter ces problèmes d’énumération est celle des séries génératrices, qui sont des fonctions codant le nombre d’objets de taille n pour tout n et qui ont l’avantage de capturer certaines propriétés des classes combinatoires (l’union disjointe des classes combinatoires est la somme des séries génératrices, le produit cartésien des classes combinatoires est le produit des séries génératrices,. . .). Plus d’informations concernant les fonctions génératrices sont présentées dans [Com74, Mac96, Rio12] et aussi dans [BLL98] qui traite de la théorie des espèces que l’on ne considérera pas dans ce mémoire. Définition 1.1.4. Soit C un ensemble et soit cn le nombre d’éléments de taille n de C. La série génératrice ordinaire associée à C est la série C(x) définie par : C(x) = X∞ n=0 cnx n . (1.1) On considère parfois une autre expression équivalente pour la série génératrice ordinaire, à savoir : C(x) = X c∈C x |c| . (1.2) Dans le cas de structures étiquetées, on considère aussi la série génératrice exponentielle : EC(x) = X∞ n=0 cn x n n! (1.3) 10 1.1 Classes et objets combinatoires qui a pour expression équivalente la série génératrice : EC(x) = X∞ n=0 x |c| |c|! . (1.4)

Mots et permutations

Les mots et les permutations sont des objets de base en combinatoire. De nombreuses opérations sur des objets plus complexes peuvent s’exprimer à l’aide des mots et de la concaténation. Nous aurons besoin de certaines notions et opérations classiques que nous définissons dès maintenant. Définition 1.1.5. Un alphabet est un ensemble dont les éléments sont appelés lettres. On le note généralement A. Tous les alphabets considérés dans ce mémoire sont totalement ordonnés. On utilise dans la suite deux alphabets différents : l’alphabet des lettres {a, b, . . . , z} et l’alphabet des entiers {1, 2, . . . , n, . . .}. Ces deux alphabets, sauf mention contraire, sont ordonnés selon l’ordre usuel. Définition 1.1.6. Un mot ω est une suite finie de lettres. La longueur d’un mot ω, notée |ω|, est le nombre de lettres qui le composent. L’unique mot de longueur 0 est le mot vide que l’on note . Définition 1.1.7. Soit ω = ω1 · · · ωn un mot de longueur n sur l’alphabet A. Un facteur de ω est un mot ωiωi+1 · · · ωi+` , où i et ` sont deux entiers vérifiant 1 6 i 6 n et i+` 6 n. Un facteur ωiωi+1 · · · ωn est appelé un suffixe. Un sous-mot de ω est un mot composé d’un sous-ensemble des lettres de ω dont on a conservé l’ordre. En d’autres termes, c’est un mot de la forme ωj1 ωj2 · · · ωjn , avec 1 6 j1 < j2 < · · · < jn 6 n. Remarque 1.1.8. Les facteurs sont en particulier des sous-mots. Le mot vide est à la fois facteur et sous-mot de n’importe quel mot. Exemple 1.1.9. Les mots aadaddaa et bbacda sont respectivement un sousmot et un facteur du mot abbacdaddeaa. Définition 1.1.10. Étant donnés deux mots u et v sur l’alphabet A, la concaténation de u et v est le mot, noté u · v, obtenu en écrivant les lettres de v à la suite de celles de u. Exemple 1.1.11. Le concaténé de acdb et bd est le mot acdb · bd = acdbbd. Définition 1.1.12. L’ensemble des mots sur l’alphabet A muni de la concaténation a une structure de monoïde dont l’élément neutre est le mot vide. On l’appelle le monoïde libre, et on le note A∗ .