Parking functions have been a focus of mathematical research since the mid-1970s. Various generalizations have been introduced since the mid-1990s and deep relationships between these and other areas of mathematics have been discovered. Here, we introduced a new generalization, the G-multiparking function, where G is a simple graph on a totally ordered vertex set {1, 2, . . . , n}. We give an algorithm that converts a G-multiparking function into a rooted spanning forest of G by using a graph searching technique to build a sequence F1, F2, . . . , Fn, where each Fi is a subforest of G and Fn is a spanning forest of G. We also give another algorithm that converts a rooted spanning forest of G to a G-multiparking function and prove that the resulting functions (between the sets of G-multiparking functions and rooted spanning forests of G) are bijections and inverses of each other. Each of these two algorithms relies on a choice function , which is a function from the set of pairs (F,W) (where F is a subforest of G and W is a set of some of the leaves of F) into W. There are many possible choice functions for a given graph, each giving formality to the concept of choosing how a graph searching algorithm should procede at each step (i.e. if the algorithm has reached Fi, then Fi+1 is some forest on the vertex set V (Fi)∪{(Fi,W)} for some W). We also define F-redundant edges, which are edges whose removal from G does not affect the execution of either algorithm mentioned above. This concept leads to a categorization of the edges of G, which in turn provides a new formula for the Tutte polynomial of G and other enumerative results.

Since their introduction by Konheim and Weiss, parking functions have evolved into objects of surprising combinatorial complexity for their simple definitions. First, we introduce these structures, give a brief history of their development and give a few basic theorems about their structure. Then we examine the internal structures of parking functions, focusing on the distribution of descents and inversions in parking functions. We develop a generalization to the Catalan numbers in order to count subsets of the parking functions. Later, we introduce a generalization to parking functions in the form of k-blocked parking functions, and examine their internal structure. Finally, we expand on the extension to the Catalan numbers, exhibiting examples to explore its internal structure. These results continue the exploration of the deep structures of parking functions and their relationship to other combinatorial objects.

Cette thèse se situe en combinatoire algébrique, et plus particulièrement en théorie combinatoire des représentations linéaires des monoïdes finis.Rappelons qu'un monoïde est un ensemble fini M muni d'une multiplication et d'un élément neutre, et qu'une représentation de M est un morphisme de M dans le monoïde des matrices $M_n(ck)$ où $ck$ est un corps, typiquement $ck =CC$. Les résultats des dernières décennies donnent un contrôle assez fin sur les représentations des monoïdes, permettant souvent de se ramener à de la théorie des représentations des groupes et de la combinatoire sur des préordres.En 1996, Krob et Thibon ont montré que l'induction et la restriction des représentations irréductibles et projectives de la tour des $0$-algèbres de Hecke $H_n(0)$ permet de munir l'ensemble des caractères d'une structure d'algèbre de Hopf, qui est isomorphe a l'algèbre de Hopf $ncsf$ des fonctions symétriques non commutatives. Cela donne une emph{catégorification} de$ncsf$, c'est-à-dire une interprétation de celle-ci en terme de théorie des représentations. Ils prolongent ainsi un résultat dû à Frobenius établissant un lien entre l'anneau des caractères de la tour des groupes symétriques et lesfonctions symétriques. Un problème naturel depuis lors est d'essayer de catégorifier d'autres algèbres de Hopf -- par exemple l'algèbre $pbt$ desarbres binaires de Loday et Ronco -- par des tours d'algèbres.Deviner une telle tour d'algèbres est difficile en général. Dans le cadre de cemanuscrit on restreint le champ de recherche aux tours de monoïdes, afin de mieux contrôler leurs représentations. C'est naturel car ce cadre couvre enfait les deux exemples fondamentaux ci-dessus, tandis qu'il est impossible decatégorifier $ncsf$ avec seulement une tour de groupes.Nous commençons par donner quelques résultats sur les représentations des toursde monoïdes. Ensuite, nous nous intéressons à la catégorification par destours de semi-treillis, et en particulier de quotients du permutoèdre. Avecceux-ci, nous catégorifions la structure de cogèbre de $fqsym$ sur la base$gbasis$ et celle d'algèbre de $fqsym$ sur la base $fbasis$. Cela ne permetcependant pas de catégorifier simultanément toute la structure de Hopf de ces algèbres. Dans un second temps, nous menons une recherche exhaustive des catégorifications de $pbt$. Nous montrons que, sous des hypothèses naturelles,il n'existe pas de catégorification de $pbt$ par une tour de monoïdesapériodiques. Enfin, nous démontrons que, dans un certain sens, la tour des monoïdes $0$-Hecke est la tour de monoïdes la plus simple catégorifiant $ncsf$.La seconde partie porte sur les fonctions de parking, par application des résultats de la première partie. D'une part, nous étudions la théorie des représentations de la tour des fonctions de parking croissantes. D'autre part,dans un travail commun avec Jean-Baptiste Priez nous reprenons une généralisation des fonctions de parking due à Stanley et Pitman. Afin d'obtenir des formules d'énumérations, nous utilisons une variante -- plus efficace dansle cas présent -- de la théorie des espèces. Nous donnons une action de$H_n(0)$ (et non du groupe symétrique) sur les fonctions de parking généralisées, et utilisons le théorème de catégorification de Krob et Thibon,pour relever dans les fonctions symétriques non commutatives le caractère de cette action. / This thesis is focused on combinatorical representation theory of finitemonoids within the field of algebraic combinatorics.A monoid $M$ is a finite set endowed with a multiplication and a neutralelement. A representation of $M$ is a morphism from $M$ into the monoid ofmatrices $M_n(ck)$ where $ck$ is a field; in this work it will typically bereferred to as $ck = CC$.The results obtained in the last decades allows us to use representation theoryof groups, and combinatorics on preorders in order to explore representationtheory of finite monoides.In 1996, Krob and Thibon proved that the induction and restriction rules ofirreducible and projective representations of the tower of $0$-Hecke monoidsendows its ring of caracters with a Hopf algebra structure, isomorph to thenon-commutative symmetric functions Hopf algebra $ncsf$. This gives acategorification of $ncsf$, which is an interpretation of the non-commutativesymmetruc functions in the language of representation theory. This extends atheorem of Frobenius endowing the character ring of symmetric groups to theHopf algebra of symmetric functions. Since then a natural problem is tocategorify other Hopf algebras -- for instance the Planar Binary Tree algebraof Loday and Ronco -- by a tower of algebras.Guessing such a tower of algebra is a difficult problem in general.In this thesis we restrict ourselves to towers of monoids in order to have abetter control on its representations. This is quite natural as on one hand,this setup covers both previous fundamental examples, whereas $ncsf$cannot be categorified in the restricted set of tower of group algebras.In the first part of this work, we start with some results about representationtheory of towers of monoids. We then focus on categorification with towers ofsemilatices, for example the tower of permutohedrons. We categorify thealgebra, and cogebra structure of $fqsym$, but not the full Hopf algebrastructure with its dual. We then make a comprehensive search in order tocategorify $pbt$ with a tower of monoids. We show that under naturalhypothesis, there exists no tower of monoids satisfying the categorificationaxioms. Finally we show that in some sense, the tower of $0$-Hecke monoids isthe simplest tower categorifying $ncsf$.The second part of this work deals with parking functions, applying resultsfrom the first part. We first study the representation theory of non decreasingparking functions. We then present a joint work with Jean-Baptiste Priez on ageneralization of parking functions from Pitman and Stanley. To obtainenumeration formulas, we use a variant of the species theory which was moreefficient in our case.We used an action of $H_n(0)$ instead of the symmetric group and use theKrob-Thibon theorem to lift the character of this action into the Hopf algebraof non-commutative symmetric functions.