This material has been published in Adv. Appl. Math. 27 (2001), 510-530, the only definitive repository of the content that has been certified and accepted after peer review. Copyright and all rights therein are retained by Academic Press. This material may not be copied or reposted without explicit permission.

Christian Krattenthaler

Permutations with restricted patterns and Dyck paths

(18 pages)

Abstract. 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 occurences 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 occurences 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 occurences of the pattern (k-1)(k-2)... 1k in form of a continued fraction and to derive further results for these permutations.

The following versions are available:

Back to Christian Krattenthaler's home page.