Permutations with Restricted Patterns and Dyck Paths

✍ Scribed by C. Krattenthaler

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 190 KB
• Volume: 27
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.2001.0747

✦ Synopsis

We exhibit a bijection between 132-avoiding permutations and Dyck paths. Using this bijection, it is shown that all the recently discovered results on generating functions for 132-avoiding permutations with a given number of occurrences of the pattern 12 k follow directly from old results on the enumeration of Motzkin paths, among which is a continued fraction result due to Flajolet. As a bonus, we use these observations to derive further results and a precise asymptotic estimate for the number of 132-avoiding permutations of 1 2 n with exactly r occurrences of the pattern 12

k. Second, we exhibit a bijection between 123-avoiding permutations and Dyck paths. When combined with a result of Roblet and Viennot, this bijection allows us to express the generating function for 123-avoiding permutations with a given number of occurrences of the pattern k -1 k -2 1k in the form of a continued fraction and to derive further results for these permutations.  2001