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

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler's exponential generating function formula for the Eulerian polynomials. They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics. The family of colored permutation groups includes the family of symmetric groups and the family of hyperoctahedral groups, also called the type A Coxeter groups and type B Coxeter groups, respectively. By specializing our formulas to these cases, they reduce to the Shareshian-Wachs q-analog of Euler's formula, formulas of Foata and Han, and a new generalization of a formula of Chow and Gessel.

Les principaux sujets d'intérêt de cette thèse concerneront deux notions de la complexité d'un mot infini : la complexité abélienne et la complexité de permutation. La complexité abélienne a été étudiée durant les dernières décennies. La complexité de permutation est, elle, une forme de complexité des mots relativement nouvelle qui associe à chaque mot apériodique de manière naturelle une permutation infinie. Nous nous pencherons sur deux sujets dans le domaine de la complexité abélienne. Dans un premier temps, nous nous intéresserons à une notion abélienne de la maximal pattern complexity définie par T. Kamae. Deuxièmement, nous analyserons une limite supérieure de cette complexité pour les mots C-équilibré. Dans le domaine de la complexité de permutation des mots apériodiques binaires, nous établissons une formule pour la complexité de permutation du mot de Thue-Morse, conjecturée par Makarov, en étudiant la combinatoire des sous-permutations sous l'action du morphisme de Thue-Morse. Par la suite, nous donnons une méthode générale pour calculer la complexité de permutation de l'image de certains mots sous l'application du morphisme du doublement des lettres. Finalement, nous déterminons la complexité de permutation de l'image du mot de Thue-Morse et d'un mot Sturmien sous l'application du morphisme du doublement des lettres. / The main topics of interest in this thesis will be two types of complexity, abelian complexity and permutation complexity. Abelian complexity has been investigated over the past decades. Permutation complexity is a relatively new type of word complexity which investigates lexicographical ordering of shifts of an aperiodic word. We will investigate two topics in the area of abelian complexity. Firstly we will consider an abelian variation of maximal pattern complexity. Secondly we consider an upper bound for words with the C-balance property. In the area of permutation complexity, we compute the permutation complexity function for a number of words. A formula for the complexity of Thue-Morse word is established by studying patterns in subpermutations and the action of the Thue-Morse morphism on the subpermutations. We then give a method to calculate the complexity of the image of certain words under the doubling map. The permutation complexity function of the image of the Thue-Morse word under the doubling map and the image of a Sturmian word under the doubling map are established.

This thesis investigates permutation pattern classes in a language theoretic context. Specifically we explored the regularity of sets of permutations under the rank encoding. We found that the subsets of plus- and minus-(in)decomposable permutations of a regular pattern class under the rank encoding are also regular languages under that encoding. Further we investigated the sets of permutations, which in their block-decomposition have the same simple permutation, and again we found that these sets of permutations are regular languages under the rank encoding. This natural progression from plus- and minus-decomposable to simple decomposable permutations led us further to the set of simple permutations under the rank encoding, which we have also shown to be regular under the rank encoding. This regular language enables us to find the set of simple permutations of any class, independent of whether the class is regular under the rank encoding. Furthermore the regularity of the languages of some types of classes is discussed. Under the rank encoding we show that in general the skew-sum of classes, separable classes and wreath classes are not regular languages; but that the direct-sum of classes, and with some restrictions on the cardinality of the input classes the skew-sum and wreath sum of classes in fact are regular under this encoding. Other encodings such as the insertion encoding and the geometric grid encoding are discussed and in the case of the geometric grid encoding alternative and constructive ways of retrieving the basis of a geometric grid class are suggested. The aforementioned results of the rank encoding have been implemented, amongst other previously shown results, and tested. The program is available and accessible to everyone. We show that the implementation for finding the block-decomposition of a permutation has cubic time complexity with respect to the length of the permutation. The code for constructing the automaton that accepts the language of all plus-indecomposable permutations of a regular class under the rank encoding has quadratic time complexity with respect to the alphabet of the language. The procedure to find the automaton that accepts the language of minus-decomposable permutations has complexity O(k⁵) and we show that the implementation of the automaton to find the language of simple permutations under the rank encoding has time complexity O(k⁵ 2ᵏ), where k is the size of the alphabet. Further we show benchmark testing on previous important results involving the rank encoding on classes and their bases.

Thesis. 1977. Ph.D.--Massachusetts Institute of Technology. Dept. of Mathematics. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Vita. / Bibliography : leaves 104-110. / Ph.D.

Thesis. 1975. Ph.D.--Massachusetts Institute of Technology. Dept. of Mathematics. / Vita. / Includes bibliographical references. / Ph.D.

Dans ce texte est présentée une sélection des travaux de l'auteur, portant, par exemple, sur la convolution libre rectangulaire, la transition de phase BBP, l'infinie divisibilité libre, les vecteurs propres de matrices de Wigner, etc...

Les principaux sujets d'intérêt de cette thèse concerneront deux notions de la complexité d'un mot infini : la complexité abélienne et la complexité de permutation. La complexité abélienne a été étudiée durant les dernières décennies. La complexité de permutation est, elle, une forme de complexité des mots relativement nouvelle qui associe à chaque mot apériodique de manière naturelle une permutation infinie. Nous nous pencherons sur deux sujets dans le domaine de la complexité abélienne. Dans un premier temps, nous nous intéresserons à une notion abélienne de la maximal pattern complexity définie par T. Kamae. Deuxièmement, nous analyserons une limite supérieure de cette complexité pour les mots C-équilibré. Dans le domaine de la complexité de permutation des mots apériodiques binaires, nous établissons une formule pour la complexité de permutation du mot de Thue-Morse, conjecturée par Makarov, en étudiant la combinatoire des sous-permutations sous l'action du morphisme de Thue-Morse. Par la suite, nous donnons une méthode générale pour calculer la complexité de permutation de l'image de certains mots sous l'application du morphisme du doublement des lettres. Finalement, nous déterminons la complexité de permutation de l'image du mot de Thue-Morse et d'un mot Sturmien sous l'application du morphisme du doublement des lettres.

The distribution theory of runs and patterns has a long and rich history. In this dissertation we study the distribution of some run-related statistics in sequences and random permutations of arbitrary multi-sets. Using the finite Markov chain imbedding technique (FMCI), which was proposed by Fu and Koutras (1994), we proposed an alternative method to calculate the exact distribution of the total number of adjacent increasing and adjacent consecutive increasing subsequences in sequences. Fu and Hsieh (2015) obtained the exact distribution of the length of the longest increasing subsequence in random permutations. To the best of our knowledge, little or no work has been done on the exact distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets. Here we obtained the exact distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets. We also obtain the the exact distribution of the length of the longest increasing subsequence for the set of all permutations of length N generated from {1,2,...,n}. / February 2016

Consider a probability distribution on the permutations of n elements. If the probability of each permutation is proportional to θK, where K is the number of cycles in the permutation, then we say that the distribution generates a θ-biased random permutation. A random permutation is a special θ-biased random permutation with θ = 1. The mth moment of the rth longest cycle of a random permutation is Θ(nm), regardless of r and θ. The joint moments are derived, and it is shown that the longest cycles of a permutation can either be positively or negatively correlated, depending on θ. The mth moments of the rth shortest cycle of a random permutation is Θ(nm−θ/(ln n)r−1) when θ < m, Θ((ln n)r) when θ = m, and Θ(1) when θ > m. The exponent of cycle lengths at the 100qth percentile goes to q with zero variance. The exponent of the expected cycle lengths at the 100qth percentile is at least q due to the Jensen’s inequality, and the exact value is derived.