Pattern Avoiding Permutations

Abuto, Chakiso (2011) Pattern Avoiding Permutations. Masters thesis, Addis Ababa University.

[img] PDF (Pattern Avoiding Permutations)
Chakiso, Abuto.pdf - Accepted Version
Restricted to Repository staff only

Download (429kB) | Request a copy

Abstract

We present in this report the methods that provide better upper bounds for the number ) of permutations of length n avoiding the pattern q. We consider permutations that avoid the pattern q of length three, four and monotone patterns only. We use Milk Bna result to show that <288 . Similarly, We obtain the generating function H(x) of all 1342-avoiding permutations of length n as well as an exact formula for their number (1342).While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of length n equals that of labeled plane trees (0,1) of a certain type on n vertices recently enumerated by Cori, Jacquard and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte in 1963. Finally, we will see that the Stanley–Wilf conjecture which states that: for all positive integers n, where is a constant

Item Type: Thesis (Masters)
Subjects: Q Science > Q Science (General)
Q Science > QA Mathematics
Divisions: Africana
Depositing User: Selom Ghislain
Date Deposited: 26 Sep 2018 11:01
Last Modified: 26 Sep 2018 11:01
URI: http://thesisbank.jhia.ac.ke/id/eprint/5592

Actions (login required)

View Item View Item