Abuto, Chakiso (2011) Pattern Avoiding Permutations. Masters thesis, Addis Ababa University.
![[img]](http://thesisbank.jhia.ac.ke/style/images/fileicons/application_pdf.png) |
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 |