Browsing by Author "Abuto, Chakiso"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Pattern Avoiding Permutations
    (Addis Ababa University, 2011-06-21) Abuto, Chakiso; Zeleke, Melkamu(Professor)
    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