Original title: Třídy permutací se zakázanými vzory
Translated title: Pattern-avoiding permutation classes
Authors: Opler, Michal ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
Document type: Bachelor's theses
Year: 2015
Language: eng
Abstract: [eng] [cze]
For a permutation π, the major index of π is the sum of all indices i such that πi > πi+1. In this thesis, we study the distribution of the major index over pattern-avoiding permutations of length n. We focus on the number Mm n (Π) of permutations of length n with major index m and avoiding the set of patterns Π. First, we are able to show that for a singleton set Π = {σ} other than some trivial cases, the values Mm n (Π) are monotonic in the sense that Mm n (Π) ≤ Mm n+1(Π). Our main result is a study of the asymptotic behaviour of Mm n (Π) as n goes to infinity. We prove that for every fixed m, Π and n large enough, Mm n (Π) is equal to a polynomial in n and moreover, we are able to determine the degrees of these polynomials for many sets of patterns. 1 Major index permutace π je součet všech indexů i takových, že πi > πi+1. V této práci zkoumáme distribuci major indexu na permutacích neobsahujích zakázané vzory. Zajímá nás hodnota Mm n (Π), což je počet permutací délky n s major indexem m a množinou zakázaných vzorů Π. Podařilo se nám ukázat, že pro jednoprvkovou množinu Π = {σ} krom okrajových triviálních pří- padů, se hodnoty Mm n (Π) chovají monotónně, nebo-li Mm n (Π) ≤ Mm n+1(Π). Hlavním výsledkem je rozbor asymptotického chování hodnot Mm n (Π) pro n jdoucí k nekonečnu. Ukážeme, že pro každé pevné m, Π a dostatečně velké n jsou hodnoty Mm n (Π) rovny polynomu v proměnné n a navíc jsme schopni určit stupně těchto polynomů pro různé množiny zakázaných vzorů. 1
Keywords: major index; pattern-avoidance; permutations; major index; permutace; zakázané vzory

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/61768

Permalink: http://www.nusl.cz/ntk/nusl-330927


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses