Le présent mémoire est une synthèse de quelques-uns des principaux résultats d'auteurs tels que Burstein, Corteel, Steingrimsson, Viennot et Williams traitant des tableaux de permutation et des tableaux-vidés. Ceux-ci sont des diagrammes dits de Ferrer remplis de 1 et de 0 selon certaines contraintes. Comme on le montrera, l'ensemble des tableaux de permutation et l'ensemble des tableaux-vidés sont en bijection avec l'ensemble des permutations. On introduit un algorithme mettant en évidence une bijection directe entre tableaux de permutation et tableaux-vidés. Ceci répond à une question apparemment ouverte de Burstein. On présente ensuite comment traduire plusieurs statistiques sur les permutations (nombre de croisements, d'alignements, de certains motifs, etc) dans le contexte des tableaux de permutation et des tableaux-vidés. Le principal résultat combinatoire sur les tableaux de permutation est une expression polynomiale donnant la distribution complète d'un motif de permutation de longueur supérieure à 2. On termine par une étude d'un sous-ensemble des tableaux de permutation: l'ensemble des tableaux de Catalan. Les tableaux de permutation et les tableaux de Catalan apparaissent naturellement, en liaison avec les problèmes de la mécanique statistique, notamment dans l'étude des modèles « Partially Asymmetric Exclusion Model »(PASEP) et « Totally Asymmetric Exclusion Model »(TASEP). Ils permettent de déterminer les probabilités stationnaires de particules en mouvement. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Tableau de permutation, Tableau-vidé, Permutation, Tableau de Catalan, PASEP.

No description available.

No description available.

Cette thèse s'intéresse au problème de la recherche de motif dans les permutations, qui a pour objectif de savoir si un motif apparaît dans un texte, en prenant en compte que le motif et le texte sont des permutations. C'est-à-dire s'il existe des éléments du texte tel que ces éléments sont triés de la même manière et apparaissent dans le même ordre que les éléments du motif. Ce problème est NP complet. Cette thèse expose des cas particuliers de ce problème qui sont solvable en temps polynomial.Pour cela nous étudions le problème en donnant des contraintes sur le texte et/ou le motif. En particulier, le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 2413 et 3142 (appelé permutation séparable) et le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 213 et 231 sont considérés. Des problèmes dérivés de la recherche de motif et le problème de la recherche de motif bivinculaire sont aussi étudiés. / This thesis focuses on permutation pattern matching problem, which askswhether a pattern occurs in a text where both the pattern and text are permutations.In other words, we seek to determine whether there exist elements ofthe text such that they are sorted and appear in the same order as the elementsof the pattern. The problem is NP-complete. This thesis examines particularcases of the problem that are polynomial-time solvable.For this purpose, we study the problem by giving constraints on the permutationstext and/or pattern. In particular, the cases in which the text and/orpattern are permutations in which the patterns 2413 and 3142 do not occur(also known as separable permutations) and in which the text and/or patternare permutations in which the patterns 213 and 231 do not occur (also known aswedge permutations) are also considered. Some problems related to the patternmatching and the permutation pattern matching with bivincular pattern arealso studied.

La correspondance de Robinson-Schensted envoie une permutation sur une paire de tableaux de Young standards de même forme. La forme de ces deux tableaux est aussi appelée forme de la permutation. Récemment, à l'aide de la théorie de Kazhdan-Lusztig, Hohlweg a caractérisé les permutations ayant le nombre d'inversions minimal et celles ayant le nombre d'inversions maximal dans un tapis qui est l'ensemble des permutations de forme fixée. Guo-Niu Han (2004) a montré, par un argument combinatoire, que la caractérisation de Hohlweg pour les permutations minimales dans un tapis est une conséquence de l'algorithme géométrique que Viennot (1976) avait construit pour la correspondance de Robinson-Schensted. Dans ce mémoire, on montre, par un argument combinatoire très similaire à celui de Guo-Niu Han, que la caractérisation de Hohlweg pour les permutations maximales est aussi une conséquence de l'algorithme géométrique de Viennot. Cette construction, qui est une variante de celle de Han, est originale. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Partages, Diagrammes de Ferrers, Tableaux de Young standards, Formule des équerres, Inversions et diagramme de Rothe d'une permutation, Représentations du groupe symétrique, Correspondance de Robinson-Schensted, Construction de Viennot, Cellules bilatères de Kazhdan-Lusztig dans le groupe symétrique, Sous-groupes de Young, Tableaux lisibles par colonnes, Permutations minimales, Permutations maximales.

This paper forms an introductory account of the irreducible representations of the permutation group using Young Tableaux as the tool to achieve this. The basics of C*-Algebra theory and Young Tableaux are provided including a brief history of the two subjects. This paper provides a straightforward development of the subject up to the main result which says that restricting the irreducible representations of S_n corresponding to the Young diagrams of shape ? to S_n-1 decomposes as the direct sum of the irreducible representations of S_n-1 corresponding to the Young diagrams formed by removing one box from ?. / Graduate

Polynomial functions over finite fields are a major tool in computer science and electrical engineering and have a long history. Some of its aspects, like interpolation and permutation polynomials are described in this thesis. A complete characterization of subfield compatible polynomials (f in E[x] such that f(K) is a subset of L, where K,L are subfields of E) was recently given by J. Hull. In his work, he introduced the Frobenius permutation which played an important role. In this thesis, we fully describe the cycle structure of the Frobenius permutation. We generalize it to a permutation called a monomial permutation and describe its cycle factorization. We also derive some important congruences from number theory as corollaries to our work.

Thesis (Ph.D.)--University of Western Australia, 2006.

No description available.

We introduce a symbolic computational approach to detecting all permutation and parity symmetries in any general evolution equation, and to generating associated invariant polynomials, from given monomials, under the action of these symmetries. Traditionally, discrete point symmetries of differential equations are systemically found by solving complicated nonlinear systems of partial differential equations; in the presence of Lie symmetries, the process can be simplified further. Here, we show how to find parity- and permutation-type discrete symmetries purely based on algebraic calculations. Furthermore, we show that such symmetries always form groups, thereby allowing for the generation of new group-invariant conserved quantities from known conserved quantities. This work also contains an implementation of the said results in Mathematica. In addition, it includes, as a motivation for this work, an investigation of the connection between variational symmetries, described by local Lie groups, and conserved quantities in Hamiltonian systems.