Tesi: "Permutations. Mathematics"

1

Steingrímsson, Einar. "Permutations statistics of indexed and poset permutations". Thesis, Massachusetts Institute of Technology, 1992. http://hdl.handle.net/1721.1/35952.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

2

West, Julian 1964. "Permutations with forbidden subsequences, and, stack-sortable permutations". Thesis, Massachusetts Institute of Technology, 1990. http://hdl.handle.net/1721.1/13641.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

3

Elizalde, Sergi 1979. "Statistics on pattern-avoiding permutations". Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/16629.

Testo completo

Abstract (sommario):

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004.
Includes bibliographical references (p. 111-116).
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
This thesis concerns the enumeration of pattern-avoiding permutations with respect to certain statistics. Our first result is that the joint distribution of the pair of statistics 'number of fixed points' and 'number of excedances' is the same in 321-avoiding as in 132-avoiding permutations. This generalizes a recent result of Robertson, Saracino and Zeilberger, for which we also give another, more direct proof. The key ideas are to introduce a new class of statistics on Dyck paths, based on what we call a tunnel, and to use a new technique involving diagonals of non-rational generating functions. Next we present a new statistic-preserving family of bijections from the set of Dyck paths to itself. They map statistics that appear in the study of pattern-avoiding permutations into classical statistics on Dyck paths, whose distribution is easy to obtain. In particular, this gives a simple bijective proof of the equidistribution of fixed points in the above two sets of restricted permutations.
(cont.) Then we introduce a bijection between 321- and 132-avoiding permutations that preserves the number of fixed points and the number of excedances. A part of our bijection is based on the Robinson-Schensted-Knuth correspondence. We also show that our bijection preserves additional parameters. Next, motivated by these results, we study the distribution of fixed points and excedances in permutations avoiding subsets of patterns of length 3. We solve all the cases of simultaneous avoidance of more than one pattern, giving generating functions which enumerate them. Some cases are generalized to patterns of arbitrary length. For avoidance of one single pattern we give partial results. We also describe the distribution of these statistics in involutions avoiding any subset of patterns of length 3. The main technique consists in using bijections between pattern-avoiding permutations and certain kinds of Dyck paths, in such a way that the statistics in permutations that we consider correspond to statistics on Dyck paths which are easier to enumerate. Finally, we study another kind of restricted permutations, counted by the Motzkin numbers. By constructing a bijection into Motzkin paths, we enumerate them with respect to some parameters, including the length of the longest increasing and decreasing subsequences and the number of ascents.
by Sergi Elizalde.
Ph.D.

Gli stili APA, Harvard, Vancouver, ISO e altri

4

Mao, Cheng Ph D. Massachusetts Institute of Technology. "Matrix estimation with latent permutations". Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/117863.

Testo completo

Abstract (sommario):

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 151-167).
Motivated by various applications such as seriation, network alignment and ranking from pairwise comparisons, we study the problem of estimating a structured matrix with rows and columns shuffled by latent permutations, given noisy and incomplete observations of its entries. This problem is at the intersection of shape constrained estimation which has a long history in statistics, and latent permutation learning which has driven a recent surge of interest in the machine learning community. Shape constraints on matrices, such as monotonicity and smoothness, are generally more robust than parametric assumptions, and often allow for adaptive and efficient estimation in high dimensions. On the other hand, latent permutations underlie many graph matching and assignment problems that are computationally intractable in the worst-case and not yet well-understood in the average-case. Therefore, it is of significant interest to both develop statistical approaches and design efficient algorithms for problems where shape constraints meet latent permutations. In this work, we consider three specific models: the statistical seriation model, the noisy sorting model and the strong stochastic transitivity model. First, statistical seriation consists in permuting the rows of a noisy matrix in such a way that all its columns are approximately monotone, or more generally, unimodal. We study both global and adaptive rates of estimation for this model, and introduce an efficient algorithm for the monotone case. Next, we move on to ranking from pairwise comparisons, and consider the noisy sorting model. We establish the minimax rates of estimation for noisy sorting, and propose a near-linear time multistage algorithm that achieves a near-optimal rate. Finally, we study the strong stochastic transitivity model that significantly generalizes the noisy sorting model for estimation from pairwise comparisons. Our efficient algorithm achieves the rate (n- 3 /4 ), narrowing a gap between the statistically optimal rate Õ(n-1 ) and the state-of-the-art computationally efficient rate [Theta] (n- 1/ 2 ). In addition, we consider the scenario where a fixed subset of pairwise comparisons is given. A dichotomy exists between the worst-case design, where consistent estimation is often impossible, and an average-case design, where we show that the optimal rate of estimation depends on the degree sequence of the comparison topology.
by Cheng Mao.
Ph. D.

Gli stili APA, Harvard, Vancouver, ISO e altri

5

Yun, Taedong. "Diagrams of affine permutations and their labellings". Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/83702.

Testo completo

Abstract (sommario):

Thesis (Ph. D.)--Massachusetts Institute of Technology, Department of Mathematics, 2013.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 63-64).
We study affine permutation diagrams and their labellings with positive integers. Balanced labellings of a Rothe diagram of a finite permutation were defined by Fomin- Greene-Reiner-Shimozono, and we extend this notion to affine permutations. The balanced labellings give a natural encoding of the reduced decompositions of affine permutations. We show that the sum of weight monomials of the column-strict balanced labellings is the affine Stanley symmetric function which plays an important role in the geometry of the affine Grassmannian. Furthermore, we define set-valued balanced labellings in which the labels are sets of positive integers, and we investigate the relations between set-valued balanced labellings and nilHecke words in the nilHecke algebra. A signed generating function of column-strict set-valued balanced labellings is shown to coincide with the affine stable Grothendieck polynomial which is related to the K-theory of the affine Grassmannian. Moreover, for finite permutations, we show that the usual Grothendieck polynomial of Lascoux-Schiitzenberger can be obtained by flagged column-strict set-valued balanced labellings. Using the theory of balanced labellings, we give a necessary and sufficient condition for a diagram to be a permutation diagram. An affine diagram is an affine permutation diagram if and only if it is North-West and admits a special content map. We also characterize and enumerate the patterns of permutation diagrams.
by Taedong Yun.
Ph.D.

Gli stili APA, Harvard, Vancouver, ISO e altri

6

Boberg, Jonas. "Counting Double-Descents and Double-Inversions in Permutations". Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-54431.

Testo completo

Abstract (sommario):

In this paper, new variations of some well-known permutation statistics are introduced and studied. Firstly, a double-descent of a permutation π is defined as a position i where πi ≥ 2πi+1. By proofs by induction and direct proofs, recursive and explicit expressions for the number of n-permutations with k double-descents are presented. Also, an expression for the total number of double-descents in all n-permutations is presented. Secondly, a double-inversion of a permutation π is defined as a pair (πi,πj) where i<j but πi ≥ 2πj. The total number of double-inversions in all n-permutations is presented.

Gli stili APA, Harvard, Vancouver, ISO e altri

7

Stadler, Jonathan. "Schur functions, juggling, and statistics on shuffled permutations /". The Ohio State University, 1997. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487947501135397.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

8

Bóna, Miklós. "Exact and asymptotic enumeration of permutations with subsequence conditions". Thesis, Massachusetts Institute of Technology, 1997. http://hdl.handle.net/1721.1/42691.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

9

Hammett, Adam Joseph. "On comparability of random permutations". Columbus, Ohio : Ohio State University, 2007. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1172592365.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

10

Marcus, Adam Wade. "New combinatorial techniques for nonlinear orders". Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24685.

Testo completo

Abstract (sommario):

Thesis (Ph.D.)--Mathematics, Georgia Institute of Technology, 2008.
Committee Chair: Prasad Tetali; Committee Member: Dana Randall; Committee Member: Robin Thomas; Committee Member: Vijay Vazirani; Committee Member: William T. Trotter

Gli stili APA, Harvard, Vancouver, ISO e altri

11

Lewis, Joel Brewster. "Pattern avoidance for alternating permutations and reading words of tableaux". Thesis, Massachusetts Institute of Technology, 2012. http://hdl.handle.net/1721.1/73444.

Testo completo

Abstract (sommario):

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student submitted PDF version of thesis.
Includes bibliographical references (p. 67-69).
We consider a variety of questions related to pattern avoidance in alternating permutations and generalizations thereof. We give bijective enumerations of alternating permutations avoiding patterns of length 3 and 4, of permutations that are the reading words of a "thickened staircase" shape (or equivalently of permutations with descent set {k, 2k, 3k, . . .}) avoiding a monotone pattern, and of the reading words of Young tableaux of any skew shape avoiding any of the patterns 132, 213, 312, or 231. Our bijections include a simple bijection involving binary trees, variations on the Robinson-Schensted-Knuth correspondence, and recursive bijections established via isomorphisms of generating trees.
by Joel Brewster Lewis.
Ph.D.

Gli stili APA, Harvard, Vancouver, ISO e altri

12

Beane, Robbie Allen. "Inverse limits of permutation maps". Diss., Rolla, Mo. : Missouri University of Science and Technology, 2008. http://scholarsmine.mst.edu/thesis/pdf/Beane_09007dcc804f93c9.pdf.

Testo completo

Abstract (sommario):

Thesis (Ph. D.)--Missouri University of Science and Technology, 2008.
Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed May 9, 2008) Includes bibliographical references (p. 71-73).

Gli stili APA, Harvard, Vancouver, ISO e altri

13

Armstrong, Alyssa. "The Pancake Problem: Prefix Reversals of Certain Permutations". Wittenberg University Honors Theses / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=wuhonors1242223287.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

14

Acan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams". The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

15

Shi, Tongjia. "Cycle lengths of θ-biased random permutations". Scholarship @ Claremont, 2014. http://scholarship.claremont.edu/hmc_theses/65.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

16

Waton, Stephen D. "On permutation classes defined by token passing networks, gridding matrices and pictures : three flavours of involvement". Thesis, St Andrews, 2007. http://hdl.handle.net/10023/237.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

17

Cassels, Joshua, e Anant Godbole. "Covering Arrays for Equivalence Classes of Words". Digital Commons @ East Tennessee State University, 2018. https://dc.etsu.edu/honors/446.

Testo completo

Abstract (sommario):

Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the dt t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds on the minimum size k = k(n) of a covering array. Most definitive results are for t = 2, 3, 4.

Gli stili APA, Harvard, Vancouver, ISO e altri

18

Chebikin, Denis. "Polytopes, generating functions, and new statistics related to descents and inversions in permutations". Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/43793.

Testo completo

Abstract (sommario):

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2008.
Includes bibliographical references (p. 75-76).
We study new statistics on permutations that are variations on the descent and the inversion statistics. In particular, we consider the alternating descent set of a permutation [sigma] = [sigma] 1 [sigma] 2 an defined as the set of indices i such that either i is odd and ai > ui+l, or i is even and au < au+l. We show that this statistic is equidistributed with the 3-descent set statistic on permutations [sigma] = [sigma] 1 [sigma] 2 ... [sigma] n+1 with al = 1, defined to be the set of indices i such that the triple [sigma] i [sigma] i + [sigma] i +2 forms an odd permutation of size 3. We then introduce Mahonian inversion statistics corresponding to the two new variations of descents and show that the joint distributions of the resulting descent-inversion pairs are the same. We examine the generating functions involving alternating Eulerian polynomials, defined by analogy with the classical Eulerian polynomials ... using alternating descents. By looking at the number of alternating inversions in alternating (down-up) permutations, we obtain a new qanalog of the Euler number En and show how it emerges in a q-analog of an identity expressing E, as a weighted sum of Dyck paths. Other parts of this thesis are devoted to polytopes relevant to the descent statistic. One such polytope is a "signed" version of the Pitman-Stanley parking function polytope, which can be viewed as a generalization of the chain polytope of the zigzag poset. We also discuss the family of descent polytopes, also known as order polytopes of ribbon posets, giving ways to compute their f-vectors and looking further into their combinatorial structure.
by Denis Chebikin.
Ph.D.

Gli stili APA, Harvard, Vancouver, ISO e altri

19

Bogaerts, Mathieu. "Codes et tableaux de permutations, construction, énumération et automorphismes". Doctoral thesis, Universite Libre de Bruxelles, 2009. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210302.

Testo completo

Abstract (sommario):

Un code de permutations G(n,d) un sous-ensemble C de Sym(n) tel que la distance de Hamming D entre deux éléments de C est supérieure ou égale à d. Dans cette thèse, le groupe des isométries de (Sym(n),D) est déterminé et il est prouvé que ces isométries sont des automorphismes du schéma d'association induit sur Sym(n) par ses classes de conjugaison. Ceci mène, par programmation linéaire, à de nouveaux majorants de la taille maximale des G(n,d) pour n et d fixés et n compris entre 11 et 13. Des algorithmes de génération avec rejet d'objets isomorphes sont développés. Pour classer les G(n,d) non isométriques, des invariants ont été construits et leur efficacité étudiée. Tous les G(4,3) et les G(5,4) ont été engendrés à une isométrie près, il y en a respectivement 61 et 9445 (dont 139 sont maximaux et décrits explicitement). D’autres classes de G(n,d) sont étudiées.

A permutation code G(n,d) is a subset C of Sym(n) such that the Hamming distance D between two elements of C is larger than or equal to d. In this thesis, we characterize the isometry group of the metric space (Sym(n),D) and we prove that these isometries are automorphisms of the association scheme induced on Sym(n) by the conjugacy classes. This leads, by linear programming, to new upper bounds for the maximal size of G(n,d) codes for n and d fixed and n between 11 and 13. We develop generating algorithms with rejection of isomorphic objects. In order to classify the G(n,d) codes up to isometry, we construct invariants and study their efficiency. We generate all G(4,3) and G(4,5)codes up to isometry; there are respectively 61 and 9445 of them. Precisely 139 out of the latter codes are maximal and explicitly described. We also study other classes of G(n,d)codes.

Doctorat en sciences, Spécialisation mathématiques
info:eu-repo/semantics/nonPublished

Gli stili APA, Harvard, Vancouver, ISO e altri

20

Jung, JiYoon. "ANALYTIC AND TOPOLOGICAL COMBINATORICS OF PARTITION POSETS AND PERMUTATIONS". UKnowledge, 2012. http://uknowledge.uky.edu/math_etds/6.

Testo completo

Abstract (sommario):

In this dissertation we first study partition posets and their topology. For each composition c we show that the order complex of the poset of pointed set partitions is a wedge of spheres of the same dimension with the multiplicity given by the number of permutations with descent composition c. Furthermore, the action of the symmetric group on the top homology is isomorphic to the Specht module of a border strip associated to the composition. We also study the filter of pointed set partitions generated by knapsack integer partitions. In the second half of this dissertation we study descent avoidance in permutations. We extend the notion of consecutive pattern avoidance to considering sums over all permutations where each term is a product of weights depending on each consecutive pattern of a fixed length. We study the problem of finding the asymptotics of these sums. Our technique is to extend the spectral method of Ehrenborg, Kitaev and Perry. When the weight depends on the descent pattern, we show how to find the equation determining the spectrum. We give two length 4 applications, and a weighted pattern of length 3 where the associated operator only has one non-zero eigenvalue. Using generating functions we show that the error term in the asymptotic expression is the smallest possible.

Gli stili APA, Harvard, Vancouver, ISO e altri

21

Okazaki, Satomi. "Cycle types of permutations with restricted positions and a characterization of a new class of interval orders". Thesis, Massachusetts Institute of Technology, 1996. http://hdl.handle.net/1721.1/38403.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

22

Irving, John. "Combinatorial Constructions for Transitive Factorizations in the Symmetric Group". Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1102.

Testo completo

Abstract (sommario):

We consider the problem of counting transitive factorizations of permutations; that is, we study tuples (σr,. . . ,σ1) of permutations on {1,. . . ,n} such that (1) the product σr. . . σ1 is equal to a given target permutation π, and (2) the group generated by the factors σi acts transitively on {1,. . . ,n}. This problem is widely known as the Hurwitz Enumeration Problem, since an encoding due to Hurwitz shows it to be equivalent to the enumeration of connected branched coverings of the sphere by a surface of given genus with specified branching. Much of our work concerns the enumeration of transitive factorizations of permutations into a minimal number of transposition factors. This problem has received considerable attention, and a formula for the number c(π) of such factorizations of an arbitrary permutation π has been derived through various means. The formula is remarkably simple, being a product of well-known combinatorial numbers, but no bijective proof of it is known except in the special case where π is a full cycle. A major goal of this thesis is to provide further combinatorial rationale for this formula. We begin by introducing an encoding of factorizations (into transpositions) as edge-labelled maps. Our central result is a bijection that allows trees to be "pruned" from such maps. This is shown to explain the appearance of factors of the form k^k in the aforementioned formula for c(π). It also has the effect of shifting focus to the combinatorics of smooth maps (i. e. maps without vertices of degree one). By providing decompositions for certain smooth planar maps, we are able to give combinatorial evaluations of c(π) when π is composed of up to three cycles. Many of these results are generalized to factorizations in which the factors are cycles of any length. We also investigate the Double Hurwitz Problem, which calls for the enumeration of factorizations whose leftmost factor is of specified cycle type, and whose remaining factors are transpositions. Finally, we extend our methods to the enumeration of factorizations up to an equivalence relation induced by possible commutations between adjacent factors.

Gli stili APA, Harvard, Vancouver, ISO e altri

23

Serrano, Luis. "Transitive Factorizations of Permutations and Eulerian Maps in the Plane". Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1128.

Testo completo

Abstract (sommario):

The problem of counting ramified covers of a Riemann surface up to homeomorphism was proposed by Hurwitz in the late 1800's. This problem translates combinatorially into factoring a permutation with a specified cycle type, with certain conditions on the cycle types of the factors, such as minimality and transitivity. Goulden and Jackson have given a proof for the number of minimal, transitive factorizations of a permutation into transpositions. This proof involves a partial differential equation for the generating series, called the Join-Cut equation. Furthermore, this argument is generalized to surfaces of higher genus. Recently, Bousquet-Mélou and Schaeffer have found the number of minimal, transitive factorizations of a permutation into arbitrary unspecified factors. This was proved by a purely combinatorial argument, based on a direct bijection between factorizations and certain objects called m-Eulerian trees. In this thesis, we will give a new proof of the result by Bousquet-Mélou and Schaeffer, introducing a simple partial differential equation. We apply algebraic methods based on Lagrange's theorem, and combinatorial methods based on a new use of Bousquet-Mélou and Schaeffer's m-Eulerian trees. Some partial results are also given for a refinement of this problem, in which the number of cycles in each factor is specified. This involves Lagrange's theorem in many variables.

Gli stili APA, Harvard, Vancouver, ISO e altri

24

Borie, Nicolas. "Calcul des invariants de groupes de permutations par transformee de fourier". Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00656789.

Testo completo

Abstract (sommario):

Cette thèse porte sur trois problèmes en combinatoire algébrique effective et algorithmique.Les premières parties proposent une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d'obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L'étude théorique est illustrée par de nombreux bancs d'essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d'entiers modulo l'action d'un groupe de permutation, dont l'algorithmique fait l'objet d'une partie préliminaire.La quatrième partie cherche à déterminer, pour un certain quotient naturel d'une algèbre de Hecke affine, quelles spécialisations des paramètres aux racines de l'unité donne un comportement non générique.Finalement, la dernière partie présente une conjecture sur la structure d'une certaine $q$-déformation des polynômes harmoniques diagonaux en plusieurs paquets de variables pour la famille infinie de groupes de réflexions complexes.Tous ces chapitres s'appuient fortement sur l'exploration informatique, et font l'objet de multiples contributions au logiciel Sage.

Gli stili APA, Harvard, Vancouver, ISO e altri

25

Widmer, Steven. "Autour de la Complexité des mots". Phd thesis, Université Claude Bernard - Lyon I, 2010. http://tel.archives-ouvertes.fr/tel-00812583.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

26

Hoffmann, Ruth. "On dots in boxes, or permutation pattern classes and regular languages". Thesis, University of St Andrews, 2015. http://hdl.handle.net/10023/7034.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

27

Benaych-Georges, Florent. "Matrices aléatoires et probabilités libres". Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2011. http://tel.archives-ouvertes.fr/tel-00655935.

Testo completo

Abstract (sommario):

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...

Gli stili APA, Harvard, Vancouver, ISO e altri

28

Lin, Zhicong. "Eulerian calculus arising from permutation statistics". Phd thesis, Université Claude Bernard - Lyon I, 2014. http://tel.archives-ouvertes.fr/tel-00996105.

Testo completo

Abstract (sommario):

In 2010 Chung-Graham-Knuth proved an interesting symmetric identity for the Eulerian numbers and asked for a q-analog version. Using the q-Eulerian polynomials introduced by Shareshian-Wachs we find such a q-identity. Moreover, we provide a bijective proof that we further generalize to prove other symmetric qidentities using a combinatorial model due to Foata-Han. Meanwhile, Hyatt has introduced the colored Eulerian quasisymmetric functions to study the joint distribution of the excedance number and major index on colored permutations. Using the Decrease Value Theorem of Foata-Han we give a new proof of his main generating function formula for the colored Eulerian quasisymmetric functions. Furthermore, certain symmetric q-Eulerian identities are generalized and expressed as identities involving the colored Eulerian quasisymmetric functions. Next, generalizing the recent works of Savage-Visontai and Beck-Braun we investigate some q-descent polynomials of general signed multipermutations. The factorial and multivariate generating functions for these q-descent polynomials are obtained and the real rootedness results of some of these polynomials are given. Finally, we study the diagonal generating function of the Jacobi-Stirling numbers of the second kind by generalizing the analogous results for the Stirling and Legendre-Stirling numbers of the second kind. It turns out that the generating function is a rational function, whose numerator is a polynomial with nonnegative integral coefficients. By applying Stanley's theory of P-partitions we find combinatorial interpretations of those coefficients

Gli stili APA, Harvard, Vancouver, ISO e altri

29

Kasraoui, Anisse. "Études combinatoires sur les permutations et partitions d'ensemble". Phd thesis, Université Claude Bernard - Lyon I, 2009. http://tel.archives-ouvertes.fr/tel-00393631.

Testo completo

Abstract (sommario):

Cette thèse regroupe plusieurs travaux de combinatoire énumérative sur les permutations et permutations d'ensemble. Elle comporte 4 parties.Dans la première partie, nous répondons aux conjectures de Steingrimsson sur les partitions ordonnées d'ensemble. Plus précisément, nous montrons que les statistiques de Steingrimsson sur les partitions ordonnées d'ensemble ont la distribution euler-mahonienne. Dans la deuxième partie, nous introduisons et étudions une nouvelle classe de statistiques sur les mots : les statistiques "maj-inv". Ces dernières sont des interpolations graphiques des célèbres statistiques "indice majeur" et "nombre d'inversions". Dans la troisième partie, nous montrons que la distribution conjointe des statistiques"nombre de croisements" et "nombre d'imbrications" sur les partitions d'ensemble est symétrique. Nous étendrons aussi ce dernier résultat dans le cadre beaucoup plus large des 01-remplissages de "polyominoes lunaires".La quatrième et dernière partie est consacrée à l'étude combinatoire des q-polynômes de Laguerre d'Al-Salam-Chihara. Nous donnerons une interprétation combinatoire de la suite de moments et des coefficients de linéarisations de ces polynômes.

Gli stili APA, Harvard, Vancouver, ISO e altri

30

Whitaker, erica j. "Congruence and Noncongruence Subgroups of Γ(2) via Graphs on Surfaces". The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1321205804.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

31

Rodrigues, Christiane Buffo 1983. "O método simbólico aplicado a problemas de combinatória". [s.n.], 2013. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307513.

Testo completo

Abstract (sommario):

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-22T15:43:28Z (GMT). No. of bitstreams: 1 Rodrigues_ChristianeBuffo_M.pdf: 948322 bytes, checksum: be5636b0d15a131df52736cd4f4782d0 (MD5) Previous issue date: 2013
Resumo: Este trabalho trata da aplicação do Método Simbólico na resolução de problemas de Combinatória. A vantagem desta técnica é o cálculo direto de uma expressão fechada para a Função Geradora F(z) do problema escrito como uma Série de Potências. Consequentemente garantimos a facilidade na enumeração da sequência que queremos a partir do coeficiente de zn de F(z). O desenvolvimento de nosso estudo foi feito aplicando-se o método a dois tipos de Classes: Rotuladas e não Rotuladas, apontando as diferenças básicas entre elas através de exemplos e resultados teóricos. Ao final, concluímos que a enumeração independe do tipo de modelagem feita para o problema
Abstract: This work deals with the application of the Symbolic Method in the solutions of combinatorial problems. The advantage of this technique is the direct calculus for the exact expression of the Generating Function F(z) of the problem, written as a Power Series. Consequently, we ensure the enumeration of the desired sequence, from the coefficient of zn of F(z). Our study was developed by applying the method in two types of Classes: Labeled and unlabelled, pointing the basic differences between them through examples and theoretical results. Finally, we concluded that the enumeration does not depend of the type of the model chosen for the problem
Mestrado
Matematica Aplicada
Mestra em Matemática Aplicada

Gli stili APA, Harvard, Vancouver, ISO e altri

32

Gelineau, Yoann. "Études combinatoires des nombres de Jacobi-Stirling et d'Entringer". Phd thesis, Université Claude Bernard - Lyon I, 2010. http://tel.archives-ouvertes.fr/tel-00531200.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

33

Dansie, B. R. "The analysis of permutations /". Title page, contents and abstract only, 1988. http://web4.library.adelaide.edu.au/theses/09PH/09phd191.pdf.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

34

Kuzucuoglu, M. "Barely transitive permutation groups". Thesis, University of Manchester, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.233097.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

35

Ledauphin, Stéphanie. "Analyse statistique d'évaluations sensorielles au cours du temps". Phd thesis, Université de Nantes, 2007. http://tel.archives-ouvertes.fr/tel-00139887.

Testo completo

Abstract (sommario):

Dans les industries agro-alimentaires ainsi que dans d'autres secteurs d'activités, l'analyse sensorielle est la clé pour répondre aux attentes des consommateurs. Cette discipline est le plus souvent basée sur l'établissement de profils sensoriels à partir de notes attribuées par des juges entraînés selon une liste de descripteurs (variables sensorielles). Dans ce type d'étude, il importe d'étudier la performance des juges et d'en tenir compte dans l'établissement des profils sensoriels. Dans cette perspective, nous proposons une démarche qui permet de procurer des indicateurs de performance du jury et de chacun des juges et de tenir compte de cette performance pour une détermination d'un tableau moyen. Des tests d'hypothèses pour évaluer la significativité de la contribution des juges à la détermination du compromis sont également proposés.
Depuis une vingtaine d'années, les courbes temps-intensité (TI) qui permettent de décrire l'évolution d'une sensation au cours de l'expérience sont de plus en plus populaires parmi les praticiens de l'analyse sensorielle. La difficulté majeure pour l'analyse des courbes TI provient d'un effet juge important qui se traduit par la présence d'une signature propre à chaque juge. Nous proposons une approche fonctionnelle basée sur les fonctions B-splines qui permet de réduire l'effet juge en utilisant une procédure d'alignement de courbes.
D'autres données sensorielles au cours du temps existent telles que le suivi de la dégradation organoleptique de produits alimentaires. Pour les étudier, nous proposons la modélisation par des chaînes de Markov cachées, de manière à pouvoir ensuite visualiser graphiquement la suivi de la dégradation.

Gli stili APA, Harvard, Vancouver, ISO e altri

36

Gilbey, Julian David. "Permutation group algebras and parking functions". Thesis, Queen Mary, University of London, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.269637.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

37

Benjamin, Ian Francis. "Quasi-permutation representations of finite groups". Thesis, University of Liverpool, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.250561.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

38

Tracey, Gareth M. "Minimal generation of transitive permutation groups". Thesis, University of Warwick, 2017. http://wrap.warwick.ac.uk/97251/.

Testo completo

Abstract (sommario):

This thesis discusses upper bounds on the minimal number of elements d(G) required to generate a finite group G. We derive explicit upper bounds for the function d on transitive and minimally transitive permutation groups, in terms of their degree n. In the transitive case, bounds obtained first by Kovács and Newman, then by Bryant, Kovács and Robinson, and finally by Lucchini, Menegazzo and Morigi, show that d(G) = O(n/ √log n), for a transitive permutation group G of degree n. In this thesis, we find best possible estimates for the constant involved.

Gli stili APA, Harvard, Vancouver, ISO e altri

39

Zmiaikou, David. "Origamis et groupes de permutation". Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00648120.

Testo completo

Abstract (sommario):

Un origami est un revêtement du tore T2, éventuellement ramifié au-dessus de l'origine.Cet objet a été introduit par William P. Thurston et William A. Veech dans les années 1970.Un origami peut être vu comme un ensemble fini de copies du carreau unitaire qui sont collées par translations. Ainsi, un origami est un cas particulier d'une surface de translation,un élément de l'espace des modules de surfaces de Riemann munies d'une 1-forme holomorphe.Un origami O avec n carreaux correspond à une paire de permutations (σ, τ ) Є 2 Sn X Sn définie à conjugaison près. Le groupe Mon(O) engendré par une telle paire s'appelle le groupe de monodromie de O. On dit qu'un origami est primitif si son groupe de monodromie est un groupe de permutation primitif. Il y a une action naturelle du groupeGL2(Z) sur les origamis, le stabilisateur de O pour cette action est le groupe de Veechdésigné par GL(O). Le groupe de monodromie est un invariant des GL2(Z)-orbites.Dans le chapitre 3 de la thèse, nous montrons que le groupe de monodromie de tout origami primitif à n carreaux dans la strate H(2k) est An ou Sn si n ≥ 3k + 2, et noustrouvons la borne exacte quand 2k + 1 est premier. La même proposition est vraie pourla strate H(1; 1) si n =/= 6. Dans le chapitre 4, nous considérons les origamis réguliers,i.e. ceux pour lesquels le nombre de carreaux est égal à l'ordre du groupe de monodromie.Nous construisons de nouvelles familles d'origamis intéressantes et cherchons leurs strates et groupes de Veech. Nous estimons également le nombre de GL2(Z)-orbites et strates distinctes des origamis réguliers ayant un groupe de monodromie donné. Afin de trouver une borne inférieure pour les origamis alternés, nous prouvons que chaque permutation dans An quifixe peu de points est le commutateur d'une paire engendrant An. Dans le chapitre 6, nous étudions une propriété de sous-groupes de PSL2(Z) qui est liée à la propriété d'être le groupe de Veech d'un origami.

Gli stili APA, Harvard, Vancouver, ISO e altri

40

Yang, Keyan. "On Orbit Equivalent Permutation Groups". The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1222455916.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

41

Gray, Darren George David. "The submodule structure of some permutation modules". Thesis, University of East Anglia, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.389230.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

42

Trongsiriwat, Wuttisak. "Combinatorics of permutation patterns, interlacing networks, and Schur functions". Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/99322.

Testo completo

Abstract (sommario):

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 71-73).
In the first part, we study pattern avoidance and permutation statistics. For a set of patterns n and a permutation statistic st, let Fst/n ([Pi]; q) be the polynomial that counts st on the permutations avoiding all patterns in [Pi]. Suppose [Pi] contains the pattern 312. For a class of permutation statistics (including inversion and descent statistics), we give a formula that expresses Fst/n ([Pi]; q) in terms of these st-polynomials for some subblocks of the patterns in [Pi]. Using this recursive formula, we construct examples of nontrivial st-Wilf equivalences. In particular, this disproves a conjecture by Dokos, Dwyer, Johnson, Sagan, and Selsor that all inv-Wilf equivalences are trivial. The second part is motivated by the problem of giving a bijective proof of the fact that the birational RSK correspondence satisfies the octahedron recurrence. We define interlacing networks to be certain planar directed networks with a rigid structure of sources and sinks. We describe an involution that swaps paths in these networks and leads to a three-term relations among path weights, which immediately implies the octahedron recurrences. Furthermore, this involution gives some interesting identities of Schur functions generalizing identities by Fulmek-Kleber. Then we study the balanced swap graphs, which encode a class of Schur function identities obtained this way.
by Wuttisak Trongsiriwat.
Ph. D.

Gli stili APA, Harvard, Vancouver, ISO e altri

43

Blackford, J. Thomas. "Permutation groups of extended cyclic codes over Galois Rings /". The Ohio State University, 1999. http://rave.ohiolink.edu/etdc/view?acc_num=osu1488186329502909.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

44

Paula, Ana Rachel Brito de 1990. "Polinômios de permutação e palavras balanceadas". [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307070.

Testo completo

Abstract (sommario):

Orientador: Fernando Eduardo Torres Orihuela
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-27T14:35:36Z (GMT). No. of bitstreams: 1 Paula_AnaRachelBritode_M.pdf: 1519694 bytes, checksum: 61b845f0f57e58e56f6a1f759fc9a382 (MD5) Previous issue date: 2015
Resumo: A dissertação "Polinômios de Permutação e Palavras Balanceadas" tem como principal objetivo estudar a influência dos polinômios de permutação na teoria de códigos mediante o conceito de palavra balanceada. A base do trabalho é o artigo "Permutacion polynomials and aplications to coding theory" de Yann Laigke-Chapuy. Expomos os conceitos básicos de polinômios de permutação como algumas de suas características, exemplos e métodos para identificação dos mesmos. Em seguida trataremos dos códigos lineares com ênfase nos binários explorando particularmente a conjectura de Helleseth
Abstract: The main goal in writing this dissertation is the study of the influence of the Theory of Permutation Polynomials in the context of Coding Theory via the concept of balanced word. Our basic reference is the paper "Permutation polynomials and applications to coding theory" by Y. Laigke- Chapury. Our plan is to introduce the basic concepts in Coding Theory, Permutation Polynomials; then we mainly consider the long-standing open Helleseth¿s conjecture
Mestrado
Matematica Aplicada
Mestra em Matemática Aplicada

Gli stili APA, Harvard, Vancouver, ISO e altri

45

McNab, C. A. "Some problems in permutation groups". Thesis, University of Oxford, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.382633.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

46

Diene, Adama. "Structure of Permutation Polynomials". University of Cincinnati / OhioLINK, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1123788311.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

47

Nambiar, Arun N. "MATHEMATICAL FORMULATION AND SCHEDULING HEURISTICS FOR CYCLIC PERMUTATION FLOW-SHOPS". Ohio University / OhioLINK, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1183424961.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

48

Sharp, Graham R. "Recognition algorithms for actions of permutation groups on pairs". Thesis, University of Oxford, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.244602.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

49

Walton, Jacqueline. "Representing the quotient groups of a finite permutation group". Thesis, University of Warwick, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.340088.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

50

Giudici, Michael Robert. "Fixed point free elements of prime order in permutation groups". Thesis, Queen Mary, University of London, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.252086.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Tesi sul tema "Permutations. Mathematics"

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili