Cette thèse se situe dans les domaines de la combinatoire algébrique, bijective et énumérative.Elle s'intéresse à l'étude des fonctions de parking généralisées suivant ces trois axes.medskip. Dans une première partie, on s'intéresse aux fonctions de parking généralisées en tant qu'espèce de structures combinatoires (théorie introduite par A.nom{Joyal} et développée F. nom{Bergeron}, G. nom{Labelle} et P.nom{Leroux}). On définit cette espèce à partir d'une équation fonctionnelle faisant intervenir l'espèce des séquences d'ensembles.On obtient un relèvement non-commutatif de la série indicatrice de cycles dans les fonctions symétriques non-commutatives, exprimé dans différentes bases.Par spécialisation, on obtient de nouvelles formules d'énumérations des fonctions de parking généralisées et de leurs types d'isomorphismes.En remplaçant l'espèce des ensembles par d'autres espèces dans l'équation fonctionnelle, on définit de nouvelles structures: les $seqPF$-tables de parking. Dans les cas particuliers où $seqPF : m mapsto a + b(m-1)$, on établit une bijection entre les $seqPF$-tables de parking et de nouvelles structures arborescentes, généralisant la bijection de C. H.nom{Yan} entre les $seqPF$-fonctions de parking et les séquences de $a$forêts de $b$-arbres.medskip. Dans une seconde partie, on s'intéresse à l'énumération d'automates. On commence par construire une bijection simple entre les automates(non-initiaux) et les séquences d'ensembles. À partir de cette bijection, on extrait la sous-famille des automates quasi-distingués (c'est-à-dire les automates pour lesquels les couples status de terminaison et fonction de transition des états sont distincts). L'énumération de ces automates quasi-distingués fournit une meilleure borne supérieure pour le nombre d'automates minimaux que celle obtenue par M.nom{Domaratzki} & textit{al}. Ensuite, on construit une nouvelle bijection entre les $2m^k$-fonctions de parking et les automates acycliques (non-initiaux) sur un alphabet à $k$ symboles. De cette dernière, on extrait, directement sur les fonctions parking, denombreuses informations de structure sur les automates, en particulier des informations liées à la minimalité.À partir de ces informations, on déduit une formule d'énumération des automates acycliques minimaux.medskipDans une troisième partie, on formalise la technique commune de réalisation polynomiale des algèbres de Hopf: fqsym, wqsym, pqsym, etc. Pour ceci, ondéfinit la notion de type d'alphabet et d'application partitionnante. La notion d'application partitionnante formalise les bonnes propriétés de la standardisation, le tassement, la parkisation, etc associées à ces précédentes algèbres de Hopf. On montre que certaines opérations, produit cartésien, coloration, union ouencore intersection, stabilisent ces notions.À partir de celles-ci, on définit deux constructions d'algèbres de Hopf combinatoire en dualité; et l'on montre qu'elles sont automatiquement munies de structures d'algèbres dendriformes et du produit $#$. En guise d'applications, on définit, pour toute famille de $seqPF$-fonctions deparking, une application généralisant la parkisation. On montre que cette dernière est une application partitionnante si et seulement si $seqPF : nmapsto 1 + m(n-1)$. Ceci permet de retrouver les algèbres de Hopf sur les$m$-fonctions de parking généralisées de J.-C. nom{Novelli} et J-.Y.nom{Thibon}. / This thesis comes within the scope of algebraic, bijective and enumerative combinatorics. It deals with the study of generalized parking functions following those axes.In the first part, we are interested in generalized parking as a species of combinatorial structures. We define this species from a functional equation involving the species of set sequences. We lift the cycle index serie to the non-commutative symmetric functions, express in several bases. By specialization, we obtain new enumeration formula of generalized parking and their isomorphism types.In the functional equation, the species of sets can be replaced by some other species. This defines new structures: the $chi$-parking tables. In particular cases with $chi : m mapsto a + b(m-1)$, we define a bijection between the $chi$-parking tables and new tree structures. This defines a generalization of the C. H. Yan bijection.In the second part, we are interested in the enumeration of automata. Firstly, we construct a simple bijection between (non-initial) automata and sequences of sets. From this bijection we extract a subfamily of quasi-distinguished automata. We obtain a better upper bound of the number of minimal automata than the one of M. Domaratzki.Then we construct a new bijection between $2m^k$-parking functions and (non-initial) acyclic automata over an alphabet of $k$ symbols. From this bijection we extract, from parking function, informations about automata structures. We deduce an enumeration formula of the minimal acyclic automata.In a third part, we formalize the common technique of polynomial realization of Hopf algebras: FQSym, WQSym, PQSym, etc.. We define a notion of type of alphabet and partitioning map. We highlight some operation which stabilizes these notions. Based on this, we define two constructions of dual combinatorial Hopf algebra; and we show that they are automatically endowed of dendriform coalgebra, and $#$-product.As an application, we define, for every family of $chi$-parking functions, a generalization of the parkization. We show that this is a partitionning map if and only if $chi : m mapsto 1 + b(m-1)$.
| Identifer | oai:union.ndltd.org:theses.fr/2015SACLS111 |
| Date | 07 December 2015 |
| Creators | Priez, Jean-Baptiste |
| Contributors | Université Paris-Saclay (ComUE), Hivert, Florent |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text, Image, StillImage |
Page generated in 0.0024 seconds