Permutations with restricted patterns and Dyck paths

Details Permutations with restricted patterns and Dyck paths Permutations with restricted patterns and Dyck paths

2000-02-24

arxiv.org/abs/math/0002200v1

Adv. Appl. Math. 27 (2001), 510-530

Mathematics

Combinatorics

17 pages, AmS-TeX

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Permutations with restricted patterns and Dyck paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Permutations with restricted patterns and Dyck paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Permutations with restricted patterns and Dyck paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-358691