This material has been published in
Adv. Appl. Math.
37
(2006), 404-431, the only definitive repository of the content that has been
certified and accepted after peer review. Copyright and all rights therein
are retained by Elsevier Publ. This material may not be copied or reposted
without explicit permission.
Christian Krattenthaler
Growth diagrams, and increasing and decreasing
chains in fillings of Ferrers shapes
(29 pages)
Abstract.
We put recent results by Chen, Deng, Du, Stanley and Yan on
crossings and nestings of matchings and set partitions in the
larger context of the enumeration of fillings of Ferrers shape
on which one imposes restrictions on their increasing and decreasing
chains. While Chen et al. work with Robinson-Schensted-like
insertion/deletion algorithms, we use the growth diagram construction
of Fomin to obtain our results. We extend the results by Chen et al.,
which, in the language of fillings, are results about
0-1-fillings, to arbitrary fillings. Finally, we point out that,
very likely, these results are part of a bigger picture which also
includes recent results of Jonsson on 0-1-fillings of stack
polyominoes, and of results of Backelin, West and Xin and of
Bousquet-Mélou and
Steingrímsson on the enumeration of
permutations and involutions with restricted patterns.
In particular, we show that our growth diagram bijections do
in fact provide alternative proofs of the results by
Backelin, West and Xin and by Bousquet-Mélou and
Steingrímsson.
The following versions are available:
Back to Christian Krattenthaler's
home page.