To see the other types of publications on this topic, follow the link: Permutations.
Dissertations / Theses on the topic 'Permutations'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Permutations.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Cox, Charles. "Infinite permutation groups containing all finitary permutations." Thesis, University of Southampton, 2016. https://eprints.soton.ac.uk/401538/.
Full textAbstract:
Groups naturally occu as the symmetries of an object. This is why they appear in so many different areas of mathematics. For example we find class grops in number theory, fundamental groups in topology, and amenable groups in analysis. In this thesis we will use techniques and approaches from various fields in order to study groups. This is a 'three paper' thesis, meaning that the main body of the document is made up of three papers. The first two of these look at permutation groups which contain all permutations with finite support, the first focussing on decision problems and the second on the R? property (which involves counting the number of twisting conjugacy classes in a group). The third works with wreath products C}Z where C is cyclic, and looks to dermine the probability of choosing two elements in a group which commute (known as the degree of commutativity, a topic which has been studied for finite groups intensely but at the time of writing this thesis has only two papers involving infinite groups, one of which is in this thesis).
2
Ku, Cheng Yeaw. "Intersecting families of permutations and partial permutations." Thesis, Queen Mary, University of London, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.416959.
Full text
3
Steingrímsson, Einar. "Permutations statistics of indexed and poset permutations." Thesis, Massachusetts Institute of Technology, 1992. http://hdl.handle.net/1721.1/35952.
Full text
4
West, Julian 1964. "Permutations with forbidden subsequences, and, stack-sortable permutations." Thesis, Massachusetts Institute of Technology, 1990. http://hdl.handle.net/1721.1/13641.
Full text
5
Cooper, Joshua N. "Quasirandom permutations /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2003. http://wwwlib.umi.com/cr/ucsd/fullcit?p3091341.
Full text
6
Hyatt, Matthew. "Quasisymmetric Functions and Permutation Statistics for Coxeter Groups and Wreath Product Groups." Scholarly Repository, 2011. http://scholarlyrepository.miami.edu/oa_dissertations/609.
Full textAbstract:
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.
7
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.
Full textAbstract:
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.
8
Maazoun, Mickaël. "Permutons limites universels de permutations aléatoires à motifs exclus." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN064.
Full textAbstract:
Les permutations à motifs exclus sont un thème important de la combinatoire énumérative et leur étude probabiliste un sujet récent en pleine expansion, notamment l'étude de la limite d'échelle, au sens des permutons, du diagramme d'une permutation aléatoire uniforme dont la taille tent vers l'infini dans une classe définie par exclusion de motifs. Le cas des permutations séparables a été étudié par Bassino, Bouvel, Féray, Gerin et Pierrot, qui ont démontré la convergence vers un objet aléatoire, permuton séparable Brownien. Nous fournissons une construction explicite à partir de processus stochastiques permettant d'étudier les propriétés fractales et de calculer certaines statistiques de cet objet. Nous étudions la classe d'universalité de ce permuton dans le cadre des classes admettant une spécification finie au sens de la décomposition par substitution. Pour nombre d'entre elles, sous une condition combinatoire simple, leur limite est une déformation à un paramètre du permuton séparable Brownien. Dans le cas des classes closes par substitution, nous considérons également des conditions suffisantes pour sortir de cette classe d'universalité, et introduisons la famille des permutons stables. Les cographes sont les graphes d'inversion des permutations séparables. Nous étudions par des méthodes similaires la convergence au sens des graphons du cographe étiqueté ou non-étiqueté uniforme, et montrons que le degré normalisé d'un sommet uniforme dans un cographe uniforme est asymptotiquement uniforme. Finalement, nous étudions les limites d'échelle et locale de la famille à motifs vinculaires exclus des permutations de Baxter. Cette classest en bijection avec de nombreux objets combinatoires remarquables, notamment les cartes bipolaires orientées. Notre résultat s'interprète en terme de la convergence de telles cartes au sens de la Peanosphere, complétant un résultat de Gwynne, Holden et SunPattern-avoiding permutations are an important theme of enumerative combinatorics, and their study from a probabilistic point of view form a recently expanding subject, for instance by considering the scaling limit behavior, in the permuton sense, of the diagram of a large uniform permutation in a pattern-avoiding class. The case of separable permutations was studied by Bassino, Bouvel, Féray, Gerin and Pierrot, who showed convergence to a random object, the Brownian separable permuton. We provide an explicit construction through stochastic processes, allowing to study the fractal properties, and compute some statistics, of this object. We study the universality class of this permuton among classes admitting a finite specification in the sense of the so-called decomposition substitution. For many of them, under a simple combinatorial condition, their limit is a one-parameter deformation of the Brownian permuton. In the specific instance of substitution-closed classes, we also consider sufficient conditions to escape this universality class, and introduct the family of stable permutons. Cographs are the inversion graphs of separable permutations. Using similar methods, we investigate the scaling limit in the graphon sense of uniform labeled and unlabeled cographs. We also show that the normalized degree of a uniform vertex in a uniform cograph is asymptotically uniform. Finally, we study local and scaling limits of Baxter permutations, a class avoiding vincular patterns. This family is in bijection with many remarkable combinatorial objects, in particular bipolar oriented maps. Our result has interpretations in terms of the Peanosphere convergence of such maps, completing a result of Gwynne, Holden and Sun
9
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.
Full textAbstract:
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
10
Dansie, B. R. "The analysis of permutations /." Title page, contents and abstract only, 1988. http://web4.library.adelaide.edu.au/theses/09PH/09phd191.pdf.
Full text
11
Vergara, John Paul C. "Sorting by Bounded Permutations." Diss., Virginia Tech, 1997. http://hdl.handle.net/10919/30401.
Full textAbstract:
Let P be a predicate applicable to permutations. A permutation that satisfies P is called a generator. Given a permutation $pi$, MinSort_P is the problem of finding a shortest sequence of generators that, when composed with $pi$, yields the identity permutation. The length of this sequence is called the P distance of $pi$. Diam_P is the problem of finding the longest such distance for permutations of a given length. MinSort_P and Diam_P, for some choices of P, have applications in the study of genome rearrangements and in the design of interconnection networks.
This dissertation considers generators that are swaps, reversals, or block-moves. Distance bounds on these generators are introduced and the corresponding problems are investigated. Reduction results, graph-theoretic models, exact and approximation algorithms, and heuristics for these problems are presented. Experimental results on the heuristics are also provided.
When the bound is a function of the length of the permutation, there are several sorting problems such as sorting by block-moves and sorting by reversals whose bounded variants are at least as difficult as the corresponding unbounded problems. For some bounded problems, a strong relationship exists between finding optimal sorting sequences and correcting the relative order of individual pairs of elements. This fact is used in investigating MinSort_P and Diam_P for two particular predicates.
A short block-move is a generator that moves an element at most two positions away from its original position. Sorting by short block-moves is solvable in polynomial time for two large classes of permutations: woven bitonic permutations and woven double-strip permutations. For general permutations, a polynomial-time (4/3)-approximation algorithm that computes short block-move distance is devised. The short block-move diameter for length-n permutations is determined.
A short swap is a generator that swaps two elements that have at most one element between them. A polynomial-time 2-approximation algorithm for computing short swap distance is devised and a class of permutations where the algorithm computes the exact short swap distance is determined. Bounds for the short swap diameter for length-n permutations are determined.Ph. D.
12
Sliačan, Jakub. "Packing and counting permutations." Thesis, Open University, 2018. http://oro.open.ac.uk/55735/.
Full textAbstract:
A permutation class is a set of permutations closed under taking subpermutations. We study two aspects of permutation classes: enumeration and packing. Our work on enumeration consists of two campaigns. First, we enumerate all juxtaposition classes of the form “Av(abc) next to Av(xy)”, where abc and xy are permutations of lengths three and two, respectively. We represent elements from such a juxtaposition class by Dyck paths decorated with sequences of points. Context-free grammars are then used to enumerate these decorated Dyck paths. Second, we classify as algebraic the generating functions of 1×m permutation grid classes where one cell is context-free and the remaining cells are monotone. We rely on properties of combinatorial specifications of context-free classes and use operators to express juxtapositions. Repeated application of operators resolves cases for m > 2. We provide examples to re-prove known results and give new ones. Our methods are algorithmic and could be implemented on a PC. Our work on packing consolidates current knowledge about packing densities of 4-point permutations. We also improve the lower bounds for the packing densities of 1324 and 1342 and provide rigorous upper bounds for the packing densities of 1324, 1342, and 2413. All our bounds are within 10-4 of the true packing densities. Together with the known bounds, we have a fairly complete picture of 4-point packing densities. Additionally, we obtain several bounds (lower and upper) for permutations of length at least five. Our main tool for the upper bounds is the framework of flag algebras introduced by Razborov in 2007. We also present Permpack — a flag algebra package for permutations.
13
Draper, Thomas Gordon. "Nonlinear complexity of Boolean permutations." College Park, Md.: University of Maryland, 2009. http://hdl.handle.net/1903/9449.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2009.Thesis research directed by: Dept. of Mathematics. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
14
Hammett, Adam Joseph. "On comparability of random permutations." Columbus, Ohio : Ohio State University, 2007. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1172592365.
Full text
15
Blacklaw, Grant Andrew. "Permutations, loops and difference sets." Thesis, Royal Holloway, University of London, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.406303.
Full text
16
Elizalde, Sergi 1979. "Statistics on pattern-avoiding permutations." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/16629.
Full textAbstract:
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.
17
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.
Full textAbstract:
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.
18
Delepelaire, Jean-François. "F - Groupes de permutations transitifs." Aix-Marseille 1, 1991. http://www.theses.fr/1991AIX11341.
Full textAbstract:
On determine la structure et les classes de conjugaison des f-sous-groupes transitifs maximaux du groupe symetrique de degre n, f etant une formation de groupes resolubles soumise a certaines conditions. Par exemple f peut etre la classe de tous les groupes finis hyperresolubles
19
Odom, Jacob Henry. "Indexing Large Permutations in Hardware." Thesis, Virginia Tech, 2019. http://hdl.handle.net/10919/89906.
Full textAbstract:
Generating unbiased permutations at run time has traditionally been accomplished through application specific optimized combinational logic and has been limited to very small permutations. For generating unbiased permutations of any larger size, variations of the memory dependent Fisher-Yates algorithm are known to be an optimal solution in software and have been relied on as a hardware solution even to this day. However, in hardware, this thesis proves Fisher-Yates to be a suboptimal solution. This thesis will show variations of Fisher-Yates to be suboptimal by proposing an alternate method that does not rely on memory and outperforms Fisher-Yates based permutation generators, while still able to scale to very large sized permutations. This thesis also proves that this proposed method is unbiased and requires a minimal input. Lastly, this thesis demonstrates a means to scale the proposed method to any sized permutations and also to produce optimal partial permutations.Master of Science
In computing, some applications need the ability to shuffle or rearrange items based on run time information during their normal operations. A similar task is a partial shuffle where only an information dependent selection of the total items is returned in a shuffled order. Initially, there may be the assumption that these are trivial tasks. However, the applications that rely on this ability are typically related to security which requires repeatable, unbiased operations. These requirements quickly turn seemingly simple tasks to complex. Worse, often they are done incorrectly and only appear to meet these requirements, which has disastrous implications for security. A current and dominating method to shuffle items that meets these requirements was developed over fifty years ago and is based on an even older algorithm refer to as Fisher-Yates, after its original authors. Fisher-Yates based methods shuffle items in memory, which is seen as advantageous in software but only serves as a disadvantage in hardware since memory access is significantly slower than other operations. Additionally, when performing a partial shuffle, Fisher-Yates methods require the same resources as when performing a complete shuffle. This is due to the fact that, with Fisher-Yates methods, each element in a shuffle is dependent on all of the other elements. Alternate methods to meet these requirements are known but are only able to shuffle a very small number of items before they become too slow for practical use. To combat the disadvantages current methods of shuffling possess, this thesis proposes an alternate approach to performing shuffles. This alternate approach meets the previously stated requirements while outperforming current methods. This alternate approach is also able to be extended to shuffling any number of items while maintaining a useable level of performance. Further, unlike current popular shuffling methods, the proposed method has no inter-item dependency and thus offers great advantages over current popular methods with partial shuffles.
20
Kammoun, Mohamed Slim. "Universalité pour les permutations aléatoires." Thesis, Lille 1, 2020. http://www.theses.fr/2020LIL1I032.
Full textAbstract:
On présente dans cette thèse des techniques de preuve d'universalité pour les permutations aléatoires. La principale méthode utilise une marche aléatoire sur le groupe symétrique. Cette technique nous permet de généraliser plusieurs résultats de convergence connus pour le cas uniforme, entre autres, le résultat de Baik, Deift et Johansson sur les fluctuations de la longueur de la plus longue sous-suite croissante. Cette technique n'est pas spécifique aux permutations aléatoires. On présente ainsi une généralisation à d'autres groupes. Une deuxième partie de la thèse est consacrée à l'utilisation de la méthode des moments ; on étudie la structure en cycle de produits de permutations indépendantes ayant une loi stable sous conjugaison. On montre qu'un simple contrôle des points fixes et des cycles de longueur 2 garantit une universalité pour les lois jointes des petits cycles du produitWe present, in this work, universality techniques for random permutations. The main method uses a random walk on the symmetric group. This technique allows us to generalize several results of known convergences for the uniform case. We generalize for example the result of Baik, Deift and Johansson on the fluctuations of the length of the longest increasing subsequence. This technique is not specific to random permutations. We present then a generalization to other groups.Using the method of moments, we study the cycle structure of the product of two independent conjugation invariant random permutations. We show that a simple control of fixed points and cycles of length 2 guarantees universality for the joint distribution of the small cycles of the product of the two permutations
21
Liese, Jeffrey Edward. "Counting patterns in permutations and words." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2008. http://wwwlib.umi.com/cr/ucsd/fullcit?p3307363.
Full textAbstract:
Thesis (Ph. D.)--University of California, San Diego, 2008.Title from first page of PDF file (viewed July 22, 2008). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 182-183).
22
Capelle, Christian. "Décompositions de graphes et permutations factorisantes." Montpellier 2, 1997. http://www.theses.fr/1997MON20006.
Full textAbstract:
Depuis plusieurs decennies les decompositions de graphes ont ete largement etudiees, en particulier comme des outils destines a mettre en uvre le paradigme diviser pour resoudre. Ici, nous nous interessons a des decompositions dont le point commun est le suivant: identifier des ensembles d'elements d'un graphe qui ont un comportement similaire vis a vis du reste du graphe. Ces ensembles sont appeles ensembles de decomposition. Nous formalisons et etudions un concept central en theorie de la decomposition: la notion de permutation factorisante. Il s'agit d'une permutation sur les sommets ou les arcs du graphe qui respecte la decomposition de ce dernier en ensembles de decomposition. Nous illustrons son interet dans le cadre de plusieurs decompositions: nous montrons que calculer la decomposition par substitution est equivalent a calculer une permutation factorisante. En utilisant la theorie de la decomposition par substitution, nous proposons une nouvelle decomposition: la decomposition en blocs des graphes d'heritage. Les graphes d'heritage (appeles aussi hierarchies d'heritage) sont les graphes orientes sans circuits possedant un plus grand et un plus petit element. Ils modelisent des relations souvent presentes dans les langages a objets ou en representation de connaissances. Nous proposons des algorithmes de calcul de cette decomposition, la aussi bases sur le calcul d'une permutation factorisante
23
Acan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487.
Full text
24
Féres, Junior Jorge 1961. "Permutações que evitam certos padrões." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307510.
Full textAbstract:
Orientador: José Plínio de Oliveira SantosDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica
Made available in DSpace on 2018-08-25T10:24:33Z (GMT). No. of bitstreams: 1 FeresJunior_Jorge_M.pdf: 656533 bytes, checksum: f89557654d48cebb7328f9f5ebbc8d0f (MD5) Previous issue date: 2014
Resumo: Nesta dissertação estudamos permutações que evitam determinados padrões. Mais especificamente, nosso foco é a contagem de tais permutações. Dentre as várias formas de descrever uma permutação, adotamos a ''representação posicional em linha'', apresentando um tratamento sistemático nesta área de padrão proibido, estudando operações, simetrias, estruturas, transformações, e principalmente, técnicas de contagem para este fim
Abstract: In this dissertation, we study permutations avoiding certain patterns. More specifically, our focus is on counting such permutations. Among the many ways to describe a permutation, we adopted the "positional representation in line" presenting a systematic treatment of this area of forbidden pattern, studying operations, symmetries, structures, transformations, and especially counting techniques for this purpose
Mestrado
Matematica Aplicada
Mestre em Matemática Aplicada
25
Elizalde, Torrent Sergi. "Consecutive patterns and statistics on restricted permutations." Doctoral thesis, Universitat Politècnica de Catalunya, 2004. http://hdl.handle.net/10803/5839.
Full textAbstract:
El tema d'aquesta tesi és l'enumeració de permutacions amb subseqüències prohibides respecte a certs estadístics, i l'enumeració de permutacions que eviten subseqüències generalitzades.Després d'introduir algunes definicions sobre subseqüències i estadístics en permutacions i camins de Dyck, comencem estudiant la distribució dels estadístics -nombre de punts fixos' i -nombre d'excedències' en permutacions que eviten una subseqüència de longitud 3. Un dels resultats principals és que la distribució conjunta d'aquest parell de paràmetres és la mateixa en permutacions que eviten 321 que en permutacions que eviten 132. Això generalitza un teorema recent de Robertson, Saracino i Zeilberger. Demostrem aquest resultat donant una bijecció que preserva els dos estadístics en qüestió i un altre paràmetre. La idea clau consisteix en introduir una nova classe d'estadístics en camins de Dyck, basada en el que anomenem túnel.
A continuació considerem el mateix parell d'estadístics en permutacions que eviten simultàniament dues o més subseqüències de longitud 3. Resolem tots els casos donant les funcions generadores corresponents. Alguns casos són generalitzats a subseqüències de longitud arbitrària. També descrivim la distribució d'aquests paràmetres en involucions que eviten qualsevol subconjunt de subseqüències de longitud 3. La tècnica principal consisteix en fer servir bijeccions entre permutacions amb subseqüències prohibides i certs tipus de camins de Dyck, de manera que els estadístics en permutacions que considerem corresponen a estadístics en camins de Dyck que són més fàcils d'enumerar.
Tot seguit presentem una nova família de bijeccions del conjunt de camins de Dyck a sí mateix, que envien estadístics que apareixen en l'estudi de permutacions amb subseqüències prohibides a estadístics clàssics en camins de Dyck, la distribució dels quals s'obté fàcilment. En particular, això ens dóna una prova bijectiva senzilla de l'equidistribució de punts fixos en les permutacions que eviten 321 i en les que eviten 132. A continuació donem noves interpretacions dels nombres de Catalan i dels nombres de Fine. Considerem una classe de permutacions definida en termes d'aparellaments de 2n punts en una circumferència sense creuaments. N'estudiem l'estructura i algunes propietats, i donem la distribució de diversos estadístics en aquests permutacions.
En la següent part de la tesi introduïm una noció diferent de subseqüències prohibides, amb el requeriment que els elements que formen la subseqüència han d'aparèixer en posicions consecutives a la permutació. Més en general, estudiem la distribució del nombre d'ocurrències de subparaules (subseqüències consecutives) en permutacions. Resolem el problema en diversos casos segons la forma de la subparaula, obtenint-ne les funcions generadores exponencials bivariades corresponents com a solucions de certes equacions diferencials lineals. El mètode està basat en la representació de permutacions com a arbres binaris creixents i en mètodes simbòlics.
La part final tracta de subseqüències generalitzades, que extenen tant la noció de subseqüències clàssiques com la de subparaules. Per algunes subseqüències obtenim nous resultats enumeratius. Finalment estudiem el comportament assimptòtic del nombre de permutacions de mida n que eviten una subseqüència generalitzada fixa quan n tendeix a infinit. També donem fites inferiors i superiors en el nombre de permutacions que eviten certes subseqüències.
26
Shi, Tongjia. "Cycle lengths of θ-biased random permutations." Scholarship @ Claremont, 2014. http://scholarship.claremont.edu/hmc_theses/65.
Full textAbstract:
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.
27
Yun, Taedong. "Diagrams of affine permutations and their labellings." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/83702.
Full textAbstract:
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.
28
Mantaci, Roberto. "Statistiques euleriennes sur les groupes de permutations." Paris 7, 1991. http://www.theses.fr/1991PA077243.
Full textAbstract:
Cette these analyse le comportement de certaines statistiques definies sur le groupe symetrique, dites statistiques euleriennes, quand on considere leur restriction a des sous-groupes de s#n. On analyse par exemple la distribution de la statistique des anti-excedances et de celle des descentes sur le groupe alterne et sur d'autres sous-groupes contenant le cycle standard (1 2. . . N). On montre entre autre que les nombres introduits pour decrire ces distributions sont lies aux coefficients binomiaux. On determine aussi un lien entre le degre minimal d'un groupe de permutation et les anti-excedances de ses generateurs avec une description plus precise de ce lien dans le cas des groupes de frobenius
29
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.
Full text
30
Karim, Jehangir Pervaiz. "Searching with lies : the Ulam problem." Thesis, University of Salford, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.301438.
Full text
31
Leahy, Jennifer C. "The permutations of periodic points in quadratic polynominials /." Connect to online version, 2005. http://ada.mtholyoke.edu/setr/websrc/pdfs/www/2005/103.pdf.
Full text
32
Smith, Rebecca Nicole. "Combinatorial algorithms involving pattern containing and avoiding permutations." [Gainesville, Fla.] : University of Florida, 2005. http://purl.fcla.edu/fcla/etd/UFE0009783.
Full text
33
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.
Full textAbstract:
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.
34
Chassaniol, Arthur. "Contributions à l'étude des groupes quantiques de permutations." Thesis, Clermont-Ferrand 2, 2016. http://www.theses.fr/2016CLF22709/document.
Full textAbstract:
Dans cette thèse nous étudions le groupe quantique d’automorphismes des graphes finis, introduit par Banica et Bichon. Dans un premier temps nous montrerons un théorème de structure du groupe quantique d’automorphismes du produit lexicographique de deux graphes finis réguliers, qui généralise un résultat classique de Sabidussi. Ce théorème donne une condition nécessaire et suffisante pour que ce groupe quantique s’exprime comme le produit en couronne libre des groupes quantiques d’automorphismes de ces deux graphes. Dans un deuxième temps, nous expliciterons certaines améliorations de résultats de Banica, Bichon et Chenevier permettant d’obtenir des critères de non symétrie quantique sur les graphes, à l’aide des outils développés par les auteurs susmentionnés.Enfin, pour poursuivre ces recherches, nous développerons une autre méthode utilisant la dualité de Tannaka-Krein et inspirée de l’étude des groupes quantiques compacts orthogonaux par Banica et Speicher. Celle-ci nous permettra, à l’aide d’une étude orbitale approfondie des graphes sommets-transitifs, d’énoncer une condition suffisante pour qu’un graphe ait des symétries quantiques ; condition qui a vocation à être aussi nécessaire mais ceci reste une conjecture à ce stadeIn this thesis we study the quantum automorphism group of finite graphs, introduces by Banica and Bichon. First we will prove a theorem about the structure of the quantum automorphism group of the lexicographic product of two finite regular graphs. It is a quantum generalization of a classical result of Sabidussi. This theorem gives a necessary and sufficient condition for this quantum group to be discribe as the free wreath product of the quantum automorphism groups of these two graphs. Then, we will give some improvement of Banica, Bichon and Chenevier results, to obtain a quantum non-symmetry criteria on graphs, using tools developped by the above authors. Finally, to continue this research, we will describe another method using Tannaka-Krein duality and inspired by the study of orthogonal compact groups by Banica and Speicher. This will enable us, with a thorough orbital study of vertex-transitive graphs, to state a sufficient condition for a graph to have quantum symmetries ; condition which is intended to be also necessary but this remains conjecture at this point
35
Ouchterlony, Erik. "On Young tableau involutions and patterns in permutations /." Linköping : Matematiska institutionen, Linköpings universitet, 2005. http://www.bibl.liu.se/liupubl/disp/disp2005/tek993s.pdf.
Full text
36
Sawatzky, Grant Michael. "Olivier Messiaen's permutations symétriques in theory and practice." Thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/43901.
Full textAbstract:
This study begins by looking at the three compositional techniques that exemplify what Olivier Messiaen called the “charm of impossibility.” Messiaen sought this aesthetic desideratum by way of techniques that in some way impose a limit on the generation of new musical material, while also implying some kind of symmetric structure. In the first chapter, using precise, formal language, I describe each technique as the application of a particular function to the elements of a particular domain. This approach exposes the similarities (as well as certain differences) between these techniques. My explanation of the more well-known techniques—modes of limited transposition, and non-retrogradable rhythms—is somewhat atypical, in that I define them in terms of functions, objects, and cycles/orbits; but this approach is purposeful, because it fosters a clearer understanding of the often misunderstood permutations symétriques.
The second chapter focuses exclusively on symmetric permutations (SPs), surveying some existing explanations of SPs before considering the ways that their applications manifest symmetry. Further, it goes into considerable mathematical detail in order to relate Messiaen’s SP orbits (consisting of m different orderings of n elements) to the larger context of the symmetric group Sn.
The third and final chapter turns to real musical examples, starting with serial procedures that are precursors to the SP technique proper, and then examining ways in which Messiaen used SP to manipulate pitch-class and/or rhythmic series in his compositions between 1950 and 1992. Finally, the conclusion outlines what it is that a rigorous theoretical approach to Messiaen’s music might contribute to the existing Messiaen literature—namely, that successful analysis of this kind can better inform some of the more speculative, philosophical lines of inquiry into Messiaen’s music, which often allude to the mathematical nature of his techniques.
37
Pons, Viviane. "Combinatoire algébrique liée aux ordres sur les permutations." Phd thesis, Université Paris-Est, 2013. http://tel.archives-ouvertes.fr/tel-00952773.
Full textAbstract:
Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur l'étude et les applications de trois ordres sur les permutations : les deux ordres faibles (gauche et droit) et l'ordre fort ou de Bruhat. Dans un premier temps, nous étudions l'action du groupe symétrique sur les polynômes multivariés. En particulier, les opérateurs de emph{différences divisées} permettent de définir des bases de l'anneau des polynômes qui généralisent les fonctions de Schur aussi bien du point de vue de leur construction que de leur interprétation géométrique. Nous étudions plus particulièrement la base des polynômes de Grothendieck introduite par Lascoux et Schützenberger. Lascoux a montré qu'un certain produit de polynômes peut s'interpréter comme un produit d'opérateurs de différences divisées. En développant ce produit, nous ré-obtenons un résultat de Lenart et Postnikov et prouvons de plus que le produit s'interprète comme une somme sur un intervalle de l'ordre de Bruhat. Nous présentons aussi l'implantation que nous avons réalisée sur Sage des polynômes multivariés. Cette implantation permet de travailler formellement dans différentes bases et d'effecteur des changements de bases. Elle utilise l'action des différences divisées sur les vecteurs d'exposants des polynômes multivariés. Les bases implantées contiennent en particulier les polynômes de Schubert, les polynômes de Grothendieck et les polynômes clés (ou caractères de Demazure).Dans un second temps, nous étudions le emph{treillis de Tamari} sur les arbres binaires. Celui-ci s'obtient comme un quotient de l'ordre faible sur les permutations : à chaque arbre est associé un intervalle de l'ordre faible formé par ses extensions linéaires. Nous montrons qu'un objet plus général, les intervalles-posets, permet de représenter l'ensemble des intervalles du treillis de Tamari. Grâce à ces objets, nous obtenons une formule récursive donnant pour chaque arbre binaire le nombre d'arbres plus petits ou égaux dans le treillis de Tamari. Nous donnons aussi une nouvelle preuve que la fonction génératrice des intervalles de Tamari vérifie une certaine équation fonctionnelle décrite par Chapoton. Enfin, nous généralisons ces résultats aux treillis de $m$-Tamari. Cette famille de treillis introduite par Bergeron et Préville-Ratelle était décrite uniquement sur les chemins. Nous en donnons une interprétation sur une famille d'arbres binaires en bijection avec les arbres $m+1$-aires. Nous utilisons cette description pour généraliser les résultats obtenus dans le cas du treillis de Tamari classique. Ainsi, nous obtenons une formule comptant le nombre d'éléments plus petits ou égaux qu'un élément donné ainsi qu'une nouvelle preuve de l'équation fonctionnelle des intervalles de $m$-Tamari. Pour finir, nous décrivons des structures algébriques $m$ qui généralisent les algèbres de Hopf $FQSym$ et $PBT$ sur les permutations et les arbres binaires
38
Bigeni, Ange. "Combinatoire bijective des permutations et nombres de Genocchi." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10233/document.
Full textAbstract:
Cette thèse a pour contexte la combinatoire énumérative et décrit la construction de plusieurs bijections entre modèles combinatoires connus ou nouveaux de suites d'entiers et polynômes, plus particulièrement celle des nombres de Genocchi (et de leurs extensions, les polynômes de Gandhi) qui interviennent dans diverses branches des mathématiques et dont les propriétés combinatoires sont de ce fait activement étudiées, et celles de polynômes q-eulériens associés aux quatre statistiques fondamentales de MacMahon sur les permutations ainsi qu'à des statistiques analogues. On commence par définir les permutations de Dumont normalisées, un modèle combinatoire des nombres de Genocchi médians normalisés q-étendus, notés ¯cn(q) et définis par Han et Zeng, puis l'on construit une première bijection entre ce modèle et l'ensemble des configurations de Dellac, autre interprétation combinatoire de ¯cn(q) mise en évidence par Feigin dans le contexte de la géométrie des grassmanniennes de carquois. En s'appuyant sur la théorie des fractions continues de Flajolet, on en construit finalement un troisième modèle combinatoire à travers les histoires de Dellac, que l'on relie aux premiers modèles sus-cités au moyen d'une seconde bijection. On s'intéresse ensuite à la classe combinatoire des k-formes irréductibles définies par Hivert et Mallet dans l'étude des k-fonctions de Schur, et qui faisaient l'objet d'une conjecture supposant que les polynômes de Gandhi sont générés par les k-formes irréductibles selon la statistique des k-sites libres. On construit une bijection entre les k-formes irréductibles et les pistolets surjectifs de hauteur k − 1 (connus pour générer les polynômes de Gandhi selon la statistique des points fixes) envoyant les k-sites libres des premières sur les points fixes des seconds, démontrant de ce fait la conjecture. Enfin, on établit une nouvelle identité combinatoire entre deux polynômes q-eulériens définis par des statistiques eulériennes et mahoniennes sur l'ensemble des permutations d'un ensemble fini, au moyen d'une dernière bijection sur les permutations, qui envoie une suite finie de statistiques sur une autreThis work is set in the context of enumerative combinatorics and constructs several statistic-preserving bijections between known or new combinatorial models of sequences of integers or polynomials, espacially the sequence of Genocchi numbers (and their extensions, the Gandhi polynomials) which appear in numerous mathematical theories and whose combinatorial properties are consequently intensively studied, and two sequences of q-Eulerian polynomials associated with the four fundamental statistics on permutations studied by MacMahon, and with analog statistics. First of all, we define normalized Dumont permutations, a combinatorial model of the q-extended normalized median Genocchi numbers ¯cn(q) introduced by Han and Zeng, and we build a bijection between the latter model and the set of Dellac configurations, which have been proved by Feigin to generate ¯cn(q) by using the geometry of quiver Grassmannians. Then, in order to answer a question raised by the theory of continued fractions of Flajolet, we define a new combinatorial model of ¯cn(q), the set of Dellac histories, and we relate them with the previous combinatorial models through a second statistic-preserving bijection. Afterwards, we study the set of irreducible k-shapes defined by Hivert and Mallet in the topic of k-Schur functions, which have been conjectured to generate the Gandhi polynomials with respect to the statistic of free ksites. We construct a statistic-preserving bijection between the irreducible k-shapes and the surjective pistols of height k−1 (well-known combinatorial interpretation of the Gandhi polynomials with respect to the fixed points statistic) mapping the free k-sites to the fixed points, thence proving the conjecture. Finally, we prove a new combinatorial identity between two eulerian polynomials defined on the set of permutations thanks to Eulerian and Mahonian statistics, by constructing a bijection on the permutations, which maps a finite sequence of statistics on another
39
Pierrot, Adeline. "Combinatoire et algorithmique dans les classes de permutations." Paris 7, 2013. http://www.theses.fr/2013PA077056.
Full textAbstract:
Cette thèse porte sur l'étude des classes de permutations à motifs exclus. Une analyse combinatoire des permutations via leur décomposition par substitution permet d'obtenir des résultats algorithmiques. La première partie de la thèse étudie la structure des classes de permutations. Plus précisément on donne un algorithme pour calculer une spécification combinatoire pour une classe de permutations données par sa base de motifs exclus. La spécification est obtenue si et seulement si la classe contient un nombre fini de permutations simples, cette condition étant testée par l'algorithme lui-même. Cet algorithme puise sa source dans les travaux de Albert et Atkinson établissant qu'une classe ayant un nombre fini de permutations simples a une base finie et une série génératrice algébrique. Les méthodes développées utilisent la théorie des langages et des automates, les ensembles partiellement ordonnés, l'introduction de motifs obligatoires. La seconde partie de la thèse donne un algorithme polynomial décidant si une permutation donnée en entrée est triable par deux piles connectées en série. L'existence d'un algorithme polynomial résolvant cette question est un problème longtemps resté ouvert, que l'on clôt dans cette thèse en introduisant une nouvelle notion, le tri par sas, en utilisant un codage des procédures de tri par un bi-coloriage du diagramme des permutations. Puis on résout le problème général en montrant qu'une procédure de tri général correspond à plusieurs étapes de tri par sasThis work is dedicated to the study of pattern closed classes of permutations. Algorithmic results are obtained thanks to a combinatorial study of permutation classes through their substitution decomposition. The first part of the thesis focuses on the structure of permutation classes. More precisely, we give an algorithm which derives a combinatorial specification for a permutation class given by its basis of excluded patterns. The specification is obtained if and only if the class contains a finite number of simple permutations, this condition being tested algorithmically. This algorithm takes its root in the theorem of Albert and Atkinson stating that every permutation class containing a finite number of simple permutations has a finite basis and an algebraic generating function, and its developments by Brignall and al. The methods involved make use of languages and automata theory, partially ordered sets and mandatory patterns. The second part of the thesis gives a polynomial algorithm deciding whether a permutation given as input is sortable trough two stacks in series. The existence of a polynomial algorithm answering this question is a problem that stayed open for a long time, which is solved in this thesis by introducing a new notion, the pushall sorting, which is a restriction of the general stack sorting. We first solve the decision problem in the particular case of the pushall sorting, by encoding the sorting procedures through a bicoloring of the diagrams of the permutations. Then we solve the general base by showing that a sorting procedure in the general case corresponds to several steps of pushall sorting which have to be compatible
40
PANAITE, PETRISOR. "Routages-produit de permutations dans les reseaux d'interconnexion." Paris 11, 1996. http://www.theses.fr/1996PA112238.
Full textAbstract:
Dans cette these, nous traitons du routage de permutations dans les reseaux d'interconnexion, modelises ici par des graphes non orientes. Notre etude est basee sur deux nouveaux types de routage de permutations, le routage par facteurs et le routage rubik, dans lesquels chaque etape s'identifie a un 1-facteur oriente et, respectivement, a un ensemble de circuits disjoints de longueur superieure ou egale a 3. Ces types de routage font partie de la famille des routages-produit, ou on peut trouver egalement des modeles connus et etudies dans la litterature comme le routage par couplages. L'interet du routage par facteurs et du routage rubik est qu'ils prennent en compte, respectivement, la notion de routage sans stockage et celle de liens semi-bidirectionnels. Nous traitons aussi bien de graphes non orientes quelconques, que de familles particulieres de graphes comme la grille 2d, le tore 2d, l'hypercube et le graphe butterfly reboucle. Nous donnons des conditions necessaires et (ou) suffisantes pour qu'un graphe soit rearrangeable sous nos modeles, ainsi que des resultats concernant le temps de routage. Nous introduisons aussi la notion de permutation arbitrairement routable. Par ceci, nous entendons une permutation routable dans l'hypercube, sans conflit-sommet, par tout algorithme glouton d'un certain type. Ces permutations ont un interet theorique mais ils peuvent aussi donner lieu a des applications pour le routage simultane de plusieurs permutations et pour le routage de paquets de grande taille. Nous caracterisons la famille des permutations arbitrairement routables et nous prouvons que des permutations frequemment utilisees dans les algorithmes paralleles font partie de cette famille
41
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.
Full text
42
Stadler, Jonathan. "Schur functions, juggling, and statistics on shuffled permutations /." The Ohio State University, 1997. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487947501135397.
Full text
43
Vong, Vincent. "Combinatoire algébrique des permutations et de leurs généralisations." Thesis, Paris Est, 2014. http://www.theses.fr/2014PEST1185/document.
Full textAbstract:
Cette thèse se situe au carrefour de la combinatoire et de l'algèbre. Elle se consacre d'une part à traduire des problèmes algébriques en des problèmes combinatoires, et inversement, utilise le formalisme algébrique pour traiter des questions combinatoires. Après un rappel des notions classiques de combinatoire et d'algèbres de Hopfavec quelques applications, nous abordons l'étude de certaines statistiques définies sur les permutations : les pics, les vallées, les doubles montées et les doubles descentes, qui sont à la base de la bijection de Françon-Viennot, elle-même débouchant sur une étude combinatoire des polynômes orthogonaux. Nous montrons qu'à partir de ces statistiques, il est possible de construire diverses sous-algèbres ou algèbres quotients de FQSym, une algèbre dont une base est indexée par les permutations. Puis, nous étudions deux suites classiques de combinatoire par une démarche non commutative : les polynômes de Gandhi, un raffinement polynomial des nombres de Genocchi, et les nombres d'Euler, une suite recelant de nombreuses propriétés combinatoires. Nous nous attachons à montrer que l'approche non commutative permet, dans la majeure partie des cas, d'obtenir de manière directe des interprétations d'identités combinatoires. Enfin, inversement, certaines questions de nature algébrique peuvent être abordées d'un point de vue combinatoire. Ainsi, à travers l'étude des algèbres dendriformes, des algèbres tridendriformes, et des quadrialgèbres, nous prouvons des questions de liberté à propos de ces algèbres grâce à la combinatoire des arbres étiquetésThis thesis is at the crossroads between combinatorics and algebra. It studies some algebraic problems from a combinatorial point of view, and conversely, some combinatorial problems have an algebraic approach which enables us tosolve them. In the first part, some classical statistics on permutations are studied: the peaks, the valleys, the double rises, and the double descents. We show that we can build sub algebras and quotients of FQSym, an algebra which basis is indexed by permutations. Then, we study classical combinatorial sequences such as Gandhi polynomials, refinements of Genocchi numbers, and Euler numbers in a non commutative way. In particular, we see that combinatorial interpretations arise naturally from the non commutative approach. Finally, we solve some freeness problems about dendriform algebras, tridendriform algebras and quadrialgebras thanks to combinatorics of some labelled trees
44
Murphy, Maximilian M. "Restricted permutations, antichains, atomic classes and stack sorting." Thesis, University of St Andrews, 2003. http://hdl.handle.net/10023/11023.
Full textAbstract:
Involvement is a partial order on all finite permutations, of infinite dimension and having subsets isomorphic to every countable partial order with finite descending chains. It has attracted the attention of some celebrated mathematicians including Paul Erdős and, due to its close links with sorting devices, Donald Knuth. We compare and contrast two presentations of closed classes that depend on the partial order of involvement: Basis or Avoidance Set, and Union of Atomic Classes. We examine how the basis is affected by a comprehensive list of closed class constructions and decompositions. The partial order of involvement contains infinite antichains. We develop the concept of a fundamental antichain. We compare the concept of 'fundamental' with other definitions of minimality for antichains, and compare fundamental permutation antichains with fundamental antichains in graph theory. The justification for investigating fundamental antichains is the nice patterns they produce. We forward the case for classifying the fundamental permutation antichains. Sorting devices have close links with closed classes. We consider two sorting devices, constructed from stacks in series, in detail. We give a comment on an enumerative conjecture by Ira Gessel. We demonstrate, with a remarkable example, that there exist two closed classes, equinumerous, one of which has a single basis element, the other infinitely many basis elements. We present this paper as a comprehensive analysis of the partial order of permutation involvement. We regard the main research contributions offered here to be the examples that demonstrate what is, and what is not, possible; although there are numerous structure results that do not fall under this category. We propose the classification of fundamental permutation antichains as one of the principal problems for closed classes today, and consider this as a problem whose solution will have wide significance for the study of partial orders, and mathematics as a whole.
45
Marcus, Adam Wade. "New combinatorial techniques for nonlinear orders." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24685.
Full textAbstract:
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
46
Johnson, Brad C. "Distribution of increasing/decreasing l-sequences in random permutations." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape10/PQDD_0006/MQ41724.pdf.
Full text
47
Jung, JiYoon. "ANALYTIC AND TOPOLOGICAL COMBINATORICS OF PARTITION POSETS AND PERMUTATIONS." UKnowledge, 2012. http://uknowledge.uky.edu/math_etds/6.
Full textAbstract:
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.
48
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.
Full text
49
Bouaza, Nouredine. "Representations combinatoires et geometriques de permutations d'apres leur graphes." Paris 6, 1987. http://www.theses.fr/1987PA066275.
Full textAbstract:
A toute permutation des entiers 1,2,. . . ,n est associe le graphe de ses inversions. On etudie les principales classes de graphes de permutations connues : graphes sans chaine induite de longueur 3, graphes de comparabilite de treillis planaires, graphes a seuil. On considere les modes d'empilement des objets d-dimensionnels (d = 2,3,4) dans l'espace
50
Bouaza, Nouredine. "Représentations combinatoires et géométriques de permutations d'après leurs graphes." Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb37603203p.
Full text