Show simple item record

dc.contributor.advisorAlbert, Michael
dc.contributor.authorLi, Jinge
dc.date.available2017-10-16T23:19:40Z
dc.date.copyright2017
dc.identifier.citationLi, J. (2017). The enumeration of subclasses of the 321-avoiding permutations (Thesis, Master of Science). University of Otago. Retrieved from http://hdl.handle.net/10523/7601en
dc.identifier.urihttp://hdl.handle.net/10523/7601
dc.description.abstractThis thesis is dedicated to the enumeration of subclasses of 321-avoiding permutations, using a combination of theoretical and experimental investigations. The thesis is organised as follows: Chapter 1 provides the necessary definitions and preliminaries, discusses the current state of research on the subject of enumerating Av(321) and its subclasses, then gives an introduction on the basic problem of containment check for 321-avoiding permutations, the process of which is used throughout our work. The main results of this study are explained in Chapter 2 and 3. Chapter 2 focuses on the implementation aspects of enumerating 321-avoiding classes, where the main goal is to develop efficient algorithms to generate all permutations up to a certain length contained in classes of the form Av(321, π). The permutation counts are then used to guess the generating function by fitting a rational function to the computed data. In Chapter 3, we deal with the more theoretical problem of enumerating 321-avoiding polynomial classes given a structural description. In particular, we propose a method which computes the grid class of such a class given its basis. We then use this information to enumerate the class using an improved version of a known algorithm.
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.publisherUniversity of Otago
dc.rightsAll items in OUR Archive are provided for private study and research purposes and are protected by copyright with all rights reserved unless otherwise indicated.
dc.subjectpermutation
dc.subjectpatterns
dc.subjectenumeration
dc.titleThe enumeration of subclasses of the 321-avoiding permutations
dc.typeThesis
dc.date.updated2017-10-16T22:27:49Z
dc.language.rfc3066en
thesis.degree.disciplineComputer Science
thesis.degree.nameMaster of Science
thesis.degree.grantorUniversity of Otago
thesis.degree.levelMasters
otago.openaccessOpen
 Find in your library

Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record