Combinatoire élémentaire

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 combinatoires, 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’anciennes, 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 à son y, alors y est le plus grand élément de P . On définit de la même manière la notion d’élément minimal et de plus petit élément en inversant la relation d’ordre 6et φ(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. 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 pour.. 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.

pour 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. engendrée par la relation de couverture qui change un facteur de la forme ab d’une permutation en le facteur ba sous la condition que a < b. Autrement dit, une permutation σ est couverte par une permutation ν si σ est de la forme σ = uabv et ν de la forme ν = ubav. Cet poset est en fait un treillis, et est connu sous le nom de permutoèdre droit [GR63]. Nous l’appellerons dans ce qui suit simplement permutoèdre. La figure 1.1 montre le diagramme de Hasse du permutoèdre droit d’ordre 4.possède une structure de groupe où le produit de deux permutations est leur composition lorsque celles-ci sont vues comme des applications. L’inverse d’une permutation est son application inverse. Ce groupe est connu sous le nom de groupe symétrique. Nous avons ainsi par exemple 35412·41253 = 13524 et 35412= σ. Par exemple, la permutation 31254 n’est pas connexe puisque 31254 = 312 21, et la permutation 35421 n’est pas anti-connexe puisque 35421 = 21 132. En revanche, 35421 est connexe et 31254 est anti-connexe. Le produit de mélange décalé ✂ est défini linéairement sur l’espace vectoriel combinatoire Vect(S) parmunies d’une flèche qui pointe vers leur but. Un chemin arbitraire sera représentée par une ligne en zigzag reliant les deux sommets qu’il connecte. L’étiquette d’un sommet d’un graphe étiqueté sera dessinée à l’intérieur du cercle qui le représente.