
arXiv: math/0002200
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 form of a continued fraction and to derive further results for these permutations.
17 pages, AmS-TeX
132-avoiding permutations, Permutations, words, matrices, Continued fractions and generalizations, Applied Mathematics, Exact enumeration problems, generating functions, Motzkin paths, Dyck paths, continued fraction, Permutations with restricted patterns, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Chebyshev polynomials, 05A05 (Primary) 05A15 05A16 (Secondary)
132-avoiding permutations, Permutations, words, matrices, Continued fractions and generalizations, Applied Mathematics, Exact enumeration problems, generating functions, Motzkin paths, Dyck paths, continued fraction, Permutations with restricted patterns, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Chebyshev polynomials, 05A05 (Primary) 05A15 05A16 (Secondary)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 90 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
