Permutations with restricted patterns and Dyck paths

We exhibit a bijection between 132-avoiding permutations and Dyck paths, Us ing 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 e numeration of Motzkin paths, among which is a continued fraction result due to Flajolet. As a bonus, we use these observations to derive further resul ts and a precise asymptotic estimate for the number of 132-avoiding permuta tions of (1, 2,..., n) with exactly r occurrences of the pattern 12...k. Se cond, we exhibit it bijection between 123-avoiding permutations and Dyck pa ths. When combined with a result of Roblet and Viennot, this bijection allo ws us to express the generating function for 123-avoiding permutations with a given number of occurrences of the pattern (k - 1)(k - 2)... k in the fo rm of a continued fraction and to derive further results for these permutat ions. (C) 2001 Academic Press.