NobleBlocks

Research indexThesis

Pattern avoidance in inversion sequences

Testart

Open access

NobleIDark:/48914/w1/20261104/C997F84DDOI10.70675/a27887e8z83dfz4d07zb13dz284ec4208b60

Abstract

Évitement de motifs dans les séquences d’inversions Cette thèse est consacrée à l'étude de l'évitement de motifs dans les séquences d'inversions, et particulièrement au dénombrement de ces objets. Les séquences d'inversions apparaissent naturellement comme des encodages de permutations via le code de Lehmer, mais elles constituent également une structure combinatoire riche à part entière. Alors que les motifs de permutations ont été largement étudiés depuis plusieurs décennies, l'étude systématique des motifs dans les séquences d'inversions est plus récente et a déjà révélé de nombreuses connexions avec des suites d'entiers bien connues et d'autres objets combinatoires. Les deux premiers chapitres étudient le dénombrement des séquences d'inversions évitant un ou deux motifs de longueur trois. En s'appuyant sur des travaux qui ont laissé de nombreux cas ouverts, nous complétons le dénombrement de ces classes en fournissant des formules de comptage pour toutes les paires de motifs restantes. Notre approche repose sur deux techniques principales. La première utilise des décompositions récursives des séquences d'inversions, conduisant à des relations de récurrence à plusieurs variables qui permettent de calculer efficacement un grand nombre de termes. La seconde utilise des constructions par arbres de génération, qui représentent les séquences d'inversions comme des nœuds dans des arbres étiquetés dont la croissance est déterminée par des règles de succession. Ces méthodes fournissent des procédures de dénombrement efficaces, et apportent un éclairage sur la structure des classes combinatoires considérées. Dans plusieurs cas, nous obtenons des fonctions génératrices algébriques. Dans les autres cas, nos résultats suggèrent que leurs fonctions génératrices ne sont pas holonomes. Dans le chapitre suivant, nous nous concentrons sur les séquences d'inversions évitant le motif 021 ainsi que d'autres motifs supplémentaires. En utilisant un encodage par des chemins de Dyck colorés, nous montrons que les séquences d'inversions évitant n'importe quel ensemble fini de motifs contenant 021 ont toujours une fonction génératrice algébrique. Ce résultat s'étend à certains sous-ensembles de séquences d'inversions tels que les "ascent sequences" et les fonctions à croissance restreinte. De plus, lorsque l'ensemble de motifs interdits contient à la fois 021 et un motif strictement croissant, nous montrons que les fonctions génératrices correspondantes sont rationnelles. Ces résultats sont obtenus grâce à des liens avec la théorie des langages formels, en interprétant les classes considérées comme des langages reconnus par des automates à compteur ou des automates finis. Dans le dernier chapitre, nous introduisons les séquences d'inversions minimales contenant un motif donné. Celles-ci forment le plus petit ensemble de séquences d'inversions dont l'évitement est équivalent à l'évitement de ce motif. Nous établissons des propriétés structurelles de ces séquences, en les caractérisant par leurs occurrences du motif donné. À partir de ces propriétés, nous déduisons des bornes supérieures et inférieures sur leur longueur, montrant qu'elles sont toujours finies. Pour certains motifs, nous obtenons des équations fonctionnelles pour dénombrer les séquences d'inversions minimales via une bijection avec des arbres croissants. Nous fournissons également des résultats de dénombrement pour les petits motifs en procédant par génération exhaustive. Enfin, nous étudions le dénombrement des séquences d'inversions sous forme réduite, aboutissant à une connexion avec les nombres de poly-Bernoulli.

Discussion

More

Suggest a correction or report