Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps
✍ Scribed by Miklós Bóna
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 318 KB
- Volume
- 80
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function H(x) of all 1342-avoiding permutations of length n as well as an exact formula for their number S n (1342). While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of length n equals that of labeled plane trees 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 (Can. J. Math. 33 (1963), 249 271). Moreover, H(x) turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Noonan and Zeilberger (Adv. Appl. Math. 17 (1996), 381 407). We also prove that n -S n (1342) converges to 8, so in particular, lim n Ä (S n (1342)ÂS n (1234))=0.
1997 Academic Press H(x)= 32x &8x 2 +20x+1&(1&8x) 3Â2 .