Structures algébriques et ordres sur les objets combinatoires

Produits et algèbres

On enrichit souvent les espaces vectoriels d’objets combinatoires d’une notion de produit, on obtient alors une algèbre. Exemple 1.1.2. Le produit basé sur la concaténation des mots : A∗ × A∗ → A∗ , u.v → uv. (1.2) Par exemple aab.abab = aababab. De façon similaire, on définit la concaténation décalée sur les permutations σ ~. µ = σ~µ (1.3) où ~µ est le mot µ où les lettres ont été décalées de |σ|. Par exemple 132 ~. 3421 = 1326754. Exemple 1.1.3. Le produit de mélange sur sur les mots se définit récursivement par u✁v :=    u si v = ǫ, v si u = ǫ, u1(u ′ ✁ v) + v1(u ✁ v ′ ) sinon, où u1, v1 ∈ A et u = u1u ′ et v = v1v ′ . (1.4) C’est la somme de tous les « mélanges » des lettres de u et v tels que l’ordre des lettres dans u et v respectivement ne soit pas modifié. Par exemple, ab ✁ ba = abba + abba + abab + baba + baab + baab (1.5) = 2 abba + 2 baab + abab + baba (1.6) Comme pour la concaténation, on peut définir le produit de mélange décalé sur les permutations. σ ✂ µ = σ ✁ ~µ (1.7) par exemple : 12 ✂ 21 = 1243 + 1423 + 1432 + 4123 + 4132 + 4312 (1.8) Définition 1.1.4. L’algèbre A d’une classe combinatoire est dite graduée si son produit vérifie la relation suivante : |x × y| = |x| + |y| (1.9) pour tout x, y ∈ A. Dit autrement, pour tout n, m ∈ N, on a que le produit × est une application de An × Am vers An+m. 

Opérations sur les mots et les permutations

Les mots et les permutations sont des objets de base en combinatoire. De nombreuses opérations sur des objets plus complexes peuvent en fait 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. Soit u = u1 . . . un un mot de taille n. Un facteur de u est un mot v = uiui+1 . . . ui+m avec 1 ≤ i ≤ n et i + m ≤ n. Le mot u s’écrit alors u = u ′ vu′′ où u ′ et u ′′ sont deux autres facteurs de u. Si v est placé au début de u, c’est-à-dire si v = u1 . . . um, on dit que v est un facteur gauche ou préfixe de u. De même si v est placé à la fin de u, c’est-à-dire si v = un−m . . . un, on dit que v est un facteur droit ou suffixe de u. Un sous-mot de u est un mot v = uj1 . . . ujm où 1 ≤ j1 < j2 < · · · < jm ≤ n. C’est-à-dire que le sous-mot v est composé d’un sousensemble des lettres de u dont on a conservé l’ordre. Par exemple si u = aabcba alors aab est un préfixe, ba un suffixe, bc un facteur et abb un sous-mot de u. Les préfixes et suffixes sont en particulier des facteurs, et les facteurs, des sous-mots. Le mot vide ǫ est à la fois préfixe, suffixe, facteur et sous-mot de n’importe quel mot u. On parle de facteur (resp. préfixe, suffixe ou sous-mot) propre quand on n’inclut pas le mot vide. Toutes ces notions s’appliquent aussi aux permutations qui sont des mots particuliers. Par exemple la permutation 52431 admet entre autres le préfixe 52, le suffixe 431, le facteur 24 et le sous-mot 231. On remarque qu’en général ces mots ne sont pas eux-mêmes des permutations. Une solution pour rester dans la même classe combinatoire est de standardiser les mots. Définition 1.1.5. Soit u = u1 . . . un un mot de taille n sur un alphabet ordonné A = {a1, a2, . . .} (par exemple, les entiers positifs). On dit que u admet une inversion (i, j) avec i < j si ui > uj . Le standardisé de u, noté std(u), est l’unique permutation σ de taille n telle que les inversions de σ soient exactement les inversions de u. Par exemple, si u = baa sur l’alphabet ordonné A = {a < b}, alors u admet deux inversions (1, 2) et (1, 3). La seule permutation de taille 3 admettant uniquement ces deux inversions est std(u) = 312. De façon générale, la standardisation revient à numéroter les lettres de u des plus petites lettres vers les plus grandes lettres et de la gauche vers la droite, cf. figure 1.1. Par définition, le standardisé d’une permutation est la permutation elle-même. On peut utiliser la standardisation sur les facteurs et sous-mots d’une permutation pour obtenir à nouveau des permutations. Par exemple, les préfixes standardisés de 52431 sont {ǫ, 1, 21, 312, 4132, 52431}

Posets Il est possible de définir des relations d’ordre sur les objets combinatoires

Les ensembles partiellement ordonnés sont couramment appelés posets, de l’anglais Partially Ordered Set. Cet objet est fondamental dans notre travail. Les posets peuvent s’étudier à la fois comme des objets combinatoires en tant que tels ou comme des structures appliquées à d’autres objets combinatoires. C’est surtout dans ce second contexte que nous les rencontrerons. Nous présentons ici les notions fondamentales dont nous aurons besoin. 1.2.1 Définition Définition 1.2.1. Un poset est un ensemble P muni d’une relation d’ordre ≤ vérifiant les conditions 1. de réflexivité : ∀x ∈ P, x ≤ x ; 2. de transitivité : ∀x, y, z ∈ P, si x ≤ y et y ≤ z alors x ≤ z ; 3. d’antisymétrie : ∀x, y ∈ P, si x ≤ y et y ≤ x alors x = y. Si la relation d’ordre est telle que pour tout x, y ∈ P, alors soit x ≤ y , soit y ≤ x, on dit que l’ordre est total ou linéaire.