Après une présentation générale des cartes planaires, nous définissons les polyèdres en coin, étudiés par Eppstein et Mumford. Nous en venons rapidement à introduire les triangulations en coin, qui sont les cartes duales des squelettes des polyèdres en coin, et en donnons quelques propriétés. Nous proposons un algorithme de réalisation de polyèdres en coin de complexité linéaire. Pour cela, l'étude des triangulations en coin conduit à des problèmes d'énumération. Une méthode classique, connue depuis Tutte, donne le résultat voulu en faisant intervenir la série des nombres de Catalan. La recherche d'une explication combinatoire à la présence des nombres de Catalan a rendu souhaitable l'utilisation d'autres méthodes, fondées sur des découpages et des recollements de morceaux de triangulations en coin. Ainsi apparaît la famille des triangulations en amande, qui est une nouvelle représentation des nombres de Catalan, qui est en bijection directe avec la famille des arbres binaires, et qui complète notre algorithme de réalisation de polyèdres en coin. Nous apportons enfin une conclusion à ces travaux en tentant de généraliser nos méthodes à des cartes dont les faces sont de degré fixé, mais quelconque. / After a general presentation of planar maps, we define corner polyhedra, studied by Eppstein and Mumford. We soon introduce corner triangulations, that are dual maps of the skeletons of corner polyhedra, and we give some properties of them.We offer a linear time algorithm to realize corner polyhedra. For that, the study of corner triangulations leads to enumeration problems. A classic method, known from Tutte, gives the wanted result, making the series of Catalan numbers appearing. The research for a combinatorial explanation of the presence of Catalan numbers induces the use of other methods, based on cuttings and gluings of some parts of corner triangulations. Thus appears the family of almond triangulations, that is a new representation of Catalan numbers, in bijection with the binary trees family, and that completes our corner polyhedra realization algorithm. We eventually give a conclusion to these works, trying to generalize our methods to maps whose faces have an any fixed degree.

Cette thèse se situe à l'interface de la combinatoire énumérative et algébrique et porte sur l'étude des probabilités du processus d'exclusion partiellement asymétrique (PASEP).Dans un premier temps, nous démontrons bijectivement une conjecture de Novelli-Thibon-Williams concernant l'interprétation combinatoire de coefficients de matrices de transition dans l'algèbre des fonctions symétriques non-commutatives. Plus précisément, ces matrices expriment les coefficients de changement de base des bases complètes et rubans d'une part vers les bases monomiales et fondamentales introduites par Tevlin d'autre part. Les coefficients de ces matrices donnent un raffinement des probabilités du PASEP et sont décrits en utilisant de nouvelles statistiques sur les permutations. La conjecture stipule que ce raffinement peut se formuler via des statistiques déjà connues dans le monde du PASEP. Nous nous intéressons ensuite à une généralisation du PASEP avec deux types de particules dans le modèle : le 2-PASEP. Nous donnons ainsi plusieurs interprétations combinatoires des probabilités de ce modèle. Pour ce faire, nous introduisons une nouvelle famille de chemins généralisant les histoires de Laguerre : les histoires de Laguerre marquées. Nous généralisons ensuite la bijection de Françon-Viennot entre les histoires de Laguerre et les permutations pour définir les permutations partiellement signées qui nous donneront une seconde interprétation combinatoire de ces probabilités. Dans une troisième partie, nous généralisons les travaux de Tevlin afin de définir des bases monomiales et fondamentales dans l'algèbre des compositions segmentées. Afin de décrire les matrices de changement de base entre ces bases et d'autres déjà connues dans cette algèbre, nous définissons une algèbre indexée par les permutations partiellement signées en utilisant les statistiques définies précédemment pour décrire la combinatoire du 2-PASEP. Nous définissons également des q-analogues de ces bases afin de faire le lien avec les probabilités du 2-PASEP en fonction du paramètre q de ce modèle. Enfin, en utilisant le fait que les permutations partiellement signées sont en bijection avec les permutations segmentées, nous nous inspirons des statistiques définies précédemment pour introduire des descentes sur ces objets et ainsi définir une généralisation des polynômes eulériens sur les permutations segmentées. Pour étudier ces polynômes, nous utilisons les outils algébriques développés dans la partie précédente / This thesis comes within the scope of enumerative and algebraic combinatorics and studies the probabilities of the partially asymmetric exclusion process (PASEP).First, we bijectively prove a conjecture of Novelli-Thibon-Williams concerning the combinatorial interpretation of the entries of the transition matrices between some bases of the noncommutative symmetric functions algebra. More precisely, these matrices correspond to the transition matrices of, on the one hand the complete and ribbon bases and on the other hand the monomial and fundamental bases, both introduced by Tevlin. The coefficients of these matrices provide a refinement of the probabilities of the PASEP and are described using new statistics on permutations. This conjecture states that this refinement can also be described using classical statistics of the PASEP. In the second part, we study a generalization of the PASEP using two kinds of particles: the 2-PASEP. Hence, we give several combinatorial interpretations of the probabilities of this model. In order to do so, we define a new family of paths generalizing the Laguerre histories: the marked Laguerre histories. We also generalize the Françon-Viennot bijection between Laguerre histories and permutations to define partially signed permutations giving another combinatorial interpretation of these probabilities. In a third part, we generalize Tevlin's work in order to define a monomial basis and a fundamental basis on the algebra over segmented compositions. In order to describe the transition matrices between these bases and other bases already known in this algebra, we define an algebra indexed by partially signed permutations using the statistics previously defined to describe the combinatorics of the 2-PASEP. We also define some q-analogues of these bases related to the probabilities of the 2-PASEP according to the q parameter of this model. Finally, using the fact that partially signed permutations and segmented permutations are in bijection, we use the statistics defined previously to define descents on these objects and get a generalization of the Eulerian polynomials on segmented permutations. To study these polynomials, we use the algebraic tools introduced in the previous part

Cette thèse se divise en 2 grandes parties indépendantes ; la première traitant des nombres de Jacobi-Stirling, la seconde abordant les nombres d’Entringer. La première partie introduit les nombres de Jacobi-Stirling de seconde et de première espèce comme coefficients algébriques dans des relations polynomiales. Nous donnons des interprétations combinatoires de ces nombres, en termes de partitions d’ensembles et de quasi-permutations pour les nombres de seconde espèce, et en termes de permutations pour les nombres de première espèce. Nous étudions également les fonctions génératrices diagonales de ces familles de nombres, ainsi qu’une de leur généralisation sur le modèle des r-nombres de Stirling. La seconde partie introduit les nombres d’Entringer à l’aide de leur interprétation en termes de permutations alternantes. Nous étudions les différentes formules de récurrence vérifiées par ces nombres et généralisons ces résultats à l’aide d’un q-analogue utilisant la statistique d’inversion. Nous verrons également que ces résultats peuvent être étendus à des permutations de forme donnée quelconque. Enfin, nous définissons la notion de famille d’Entringer, et établissons des bijections entre certaines de ces familles. En particulier, nous établissons une bijection reliant les permutations alternantes de premier terme fixé, aux arbres binaires croissants dont l’extrémité du chemin minimal est fixée. / This thesis is constructed in two main independant parts ; the first one dealing with the numbers of Jacobi-Stirling, the second one tackling the numbers of Entringer. The first part introduces the numbers of Jacobi-Stirling of the second kind and of the first kind, as algebraic coefficients in some polynomial relations. We give some combinatorial interpretations of these numbers, in terms of set partitions and quasi-permutations for the numbers of the second kind, and in terms of permutations for the numbers of the first kind. We also study the diagonal generating functions of these sequences of numbers, and one of their generalization based on the model of r-Stirling numbers. The second part introduces the numbers of Entringer with their interpretation in terms of alternating permutations. We study the different recurrences formulas satisfied by these numbers, and refine these results with a q-analogue using the inversion statistic. We also note that these results can be extend to permutations with any fixed shape. Finally, we define the notion of Entringer family, and provide bijections between some of these families. In particular, we establish a bijection between the alternating permutations with fixed given value, and the binary increasing trees such that the end-point of the minimal path is fixed.

La première partie de ce mémoire est consacrée à l'énumération de diverses familles de structures arborescentes, en général selon le nombre de sommets. Les trois premiers chapitres sont consacrés à l'étude des arborescences de Cayley telles que la racine est inférieure à ses fils et des arborescences alternantes. La plupart de nos résultats sont prouvés bijectivement. Nous nous intéressons ensuite aux arborescences coloriées, et plus particulièrement à la formule d'inversion de séries formelles multivariées de Good-Lagrange. Nous donnons une nouvelle preuve bijective d'une variante de cette formule et utilisons cette preuve pour prouver combinatoirement diverses formules d'énumération de structures arborescentes et en déduire des algorithmes de génération aléatoire pour ces structures (notamment les cactus planaires). Nous concluons cette première partie par un chapitre consacré aux constellations : en combinant notre preuve de la formule de Good-Lagrange et la conjugaison d'arborescences (due à Bousquet-Mélou et Schaeffer), nous prouvons bijectivement une formule (nouvelle) pour l'énumération de constellations selon le nombre de sommets et de faces. Dans la seconde partie, nous étudions le problème de la recherche de motifs dans une arborescence, en utilisant une structure de données classique pour les mots : l'arborescence des suffixes. Nous proposons notamment un algorithme de recherche de motifs dans une arborescence, basé sur un codage d'une arborescence par des mots et sur l'utilisation de l'arborescence des suffixes d'un de ces mots, qui semble avoir de bonnes propriétés expérimentales. Nous concluons en étendant la notion d'arborescence des suffixes des mots aux arborescences et en décrivant un algorithme de construction pour cette structure.

Cette thèse se divise en 2 grandes parties indépendantes ; la première traitant des nombres de Jacobi-Stirling, la seconde abordant les nombres d'Entringer. La première partie introduit les nombres de Jacobi-Stirling de seconde et de première espèce comme coefficients algébriques dans des relations polynomiales. Nous donnons des interprétations combinatoires de ces nombres, en termes de partitions d'ensembles et de quasi-permutations pour les nombres de seconde espèce, et en termes de permutations pour les nombres de première espèce. Nous étudions également les fonctions génératrices diagonales de ces familles de nombres, ainsi qu'une de leur généralisation sur le modèle des r-nombres de Stirling. La seconde partie introduit les nombres d'Entringer à l'aide de leur interprétation en termes de permutations alternantes. Nous étudions les différentes formules de récurrence vérifiées par ces nombres et généralisons ces résultats à l'aide d'un q-analogue utilisant la statistique d'inversion. Nous verrons également que ces résultats peuvent être étendus à des permutations de forme donnée quelconque. Enfin, nous définissons la notion de famille d'Entringer, et établissons des bijections entre certaines de ces familles. En particulier, nous établissons une bijection reliant les permutations alternantes de premier terme fixé, aux arbres binaires croissants dont l'extrémité du chemin minimal est fixée.

Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T04:32:08Z (GMT). No. of bitstreams: 1 BrasilJunior_NelsonGomes_M.pdf: 980636 bytes, checksum: dd8d61baeb633d5f598abc3523def800 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, estudamos a sequência dos Números de Catalan, uma sequência que aparece como solução de vários problemas de contagem envolvendo árvores, palavras, grafos e outras estruturas combinatórias. Atualmente, são conhecidas cerca de 200 interpretações combinatórias distintas para os Números de Catalan, o que motiva o estudo de relações entre estas interpretações, isto é, entre conjuntos cuja cardinalidade é dada pelos termos desta sequência. O principal objetivo do nosso trabalho é, portanto, mostrar bijeções entre esses conjuntos. No início do texto fazemos uma pequena introdução histórica aos números de Catalan, assim como definimos algumas formas de representar a sequência estudada. Depois mostramos algumas bijeções clássicas entre conjuntos contados pela sequência de Catalan. Além disso, apresentamos outras bijeções entre conjuntos envolvendo diversos objetos combinatórios. No total, são exibidas 29 bijeções / Abstract: In this work, we study the sequence of Catalan Numbers, which appears as a solution of many counting problems involving trees, words, graphs and other combinatorial structures. Nowadays, about 200 different combinatorial interpretations of the Catalan Numbers are known and that motivates the study between them, i. e., the study between sets whose cardinality is given by the terms of this sequence. The main objective of our work is therefore to show bijections between these sets. In the beginning, we make a short historical introduction of the Catalan Numbers and define some ways to represent the sequence. After that, we show some classical bijections between sets counted by the Catalan Numbers. Additionally, we exhibit other bijections between sets involving several combinatorial objects. Altogether, 29 bijections are presented / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada