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.