Combinatoire élémentaire

Ce chapitre, premier d’une série de trois chapitres préliminaires, pose les définitions et les concepts de base d’algèbre et de combinatoire utilisés dans ce travail.Dans le paragraphe 1.1, nous fixons nos notations et rappelons les définitions ainsi que les notions fondamentales sous-jacentes à cinq structures algébriques élémentaires : les classes com- binatoires, les monoïdes, les ensembles partiellement ordonnés, les treillis et les espaces vectoriels combinatoires. Les mots sont des objets combinatoires à la fois très simples et très riches. Nous leur consacrons le paragraphe 1.2, où les permutations, qui sont des mots particuliers, sont égale- ment passées en revue. Enfin, dans le paragraphe 1.3, les définitions de base à propos des graphes et des arbres sont posées. Nous nous attardons plus particulièrement sur les arbres binaires, qui sont l’un des personnages principaux de ce mémoire.6. Il existe d’autres opérations bien connues sur les classes combinatoires qui à partir d’an- ciennes, en produisent de nouvelles. Par exemple, la construction ensemble prend en entrée une classe combinatoire C et produit la classe combinatoire dont les éléments sont des en- sembles d’éléments de C. De même, les constructions multi-ensemble et suite produisent, sur l’entrée d’une classe combinatoire C respectivement la classe combinatoire dont les éléments sont des multi-ensembles d’éléments de C et la classe combinatoire dont les élé- ments sont des suites d’éléments de C. Ces constructions, ainsi que les séries génératrices correspondantes, sont décrites par exemple en [FS09].

En fonction des besoins, nous noterons tantôt un monoïde sous la forme de triplet (M, ·, 1), tantôt sous la forme de couple (M, ·), ou même tout simplement en faisant référence à sonensemble sous-jacent M si le contexte le permet. Cette dernière convention de notation, où l’on fait référence à l’ensemble sous-jacent d’une structure algébrique pour parler de la structure algébrique elle-même, sera utilisée tout au long de ce mémoire.Dans cette partie, nous rappelons les notions de base concernant les ensembles partiellement ordonnés et les treillis que nous utiliserons dans ce mémoire. Pour des notions plus précises et détaillées, le lecteur pourra consulter [BS81] ou [Sta11].et φ(y) = φ(x) + 1 si y couvre x dans P , alors P est gradué. Le diagramme de Hasse de P est le graphe orienté (voir le paragraphe 1.3.1) dont l’ensemble de sommets est P et dont les arcs correspondent aux couples (x, y) tel que y couvre x dans P . Pour alléger nos représentations graphiques, les arcs d’un diagramme de Hasse ne seront pas orientés ; ils le sont implicitement par le fait que l’élément couvert se trouve plus haut que l’élément couvrant.

Structures combinatoires et algébriques élémentaires

Une définition des treillis, alternative à la définition 1.1.4, propose de voir une telle structure comme un ensemble L muni de deux lois de composition internes ∨ et ∧ qui vérifient les conditions (i) d’associativité, de commutativité et d’idempotence (i.e., x ∨ x = x et x ∧ x = x pourPour le reste de ce mémoire, le symbole K désigne un corps quelconque de caractéristique nulle. Sauf mention contraire, toutes les structures algébriques le nécessitant sont définies sur K, et ceci implicitement.Nous supposons connues du lecteur les notions basiques d’algèbre linéaire. Le but de ce paragraphe est d’introduire le vocabulaire que nous utiliserons dans le reste du texte, notamment dans le contexte des espaces vectoriels libres sur un ensemble. En effet, la plupart des espaces vectoriel que nous manipulerons sont des espaces vectoriels dont les bases sont indexées par des objets combinatoires.et nous pouvons voir Vect(E) comme l’espace vectoriel des sommes formelles finies d’éléments de E à coefficients dans K. La base des F est la base fondamentale de Vect(E). Remarquons que dans certains cas, par souci de lisibilité, nous noterons simplement par x un élément Fpour un ensemble E quelconque, et désignent respectivement le monoïde libre des suites finies d’éléments de E, l’ensemble des suites finies et non vides d’éléments de E, l’ensemble des suites de longueur n d’éléments de E et l’espace vectoriel des polynômes non commutatifs sur l’ensemble E de variables.