A Weight-Preserving Bijection Between Schröder Paths and Schröder Permutations

Jason Bandlow^{1}, Eric S. Egge^{2}, and Kendra Killpatrick^{1}

{bandlow, killpatr}@math.colostate.edu

eggee@member.ams.org

Annals of Combinatorics 6 (3) p.235-248 September, 2002

Abstract:

In 1993 Bonin, Shapiro, and Simion showed that the Schröder numbers count certain kinds of lattice paths; these paths are now called Schröder paths. In 1995 West showed that the Schröder numbers also count permutations which avoid the patterns 4231 and 4132. Using some technical machinery, Barcucci, Del Lungo, Pergola, and Pinzani showed in 1999 that a certain q-analog of the Schröder numbers, called the Schröder polynomial, is the generating function for a statistic called the area statistic on Schröder paths and is also the generating function for the inversion number on permutations which avoid 4231 and 4132. In this paper we give a constructive bijection from Schröder paths to permutations which avoid 4231 and 4132 that takes the area statistic on Schröder paths to the inversion number on permutations which avoid 4231 and 4132.

References:

1. J. Bandlow and K. Killpatrick, An area-to-inv bijection between Dyck paths and 312- avoiding permutations, Elect. J. Combin. 8 (1) (2001) #R40.

2. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Some combinatorial interpretations of q-analogs of Schröder numbers, Ann. Combin. 3 (1999) 171每190.

3. J. Bonin, L. Shapiro, and R. Simion, Some q-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Stat. Plann. Inference 34 (1993) 35每55.

4. L. Carlitz, Sequences, paths, ballot numbers, Fibonacci Quart. 10 (1972) 531每549.

5. L. Carlitz and J. Riordan, Two element lattice permutation numbers and their qgeneralization, Duke J. Math 31 (1964) 371每388.

6. J. F“urlinger and J. Hofbauer, q-Catalan numbers, J. Combin. Theory, Ser. A 40 (1985) 248每 264.

7. A. Garsia and J. Haglund, A proof of the q; t-Catalan positivity conjecture, preprint.

8. A. Garsia and M. Haiman, A remarkable q;t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5 (3) (1996) 191每244.

9. J. Haglund, Conjectured statistics for the q;t-Catalan numbers, preprint.

10. D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000) 121每130.

11. D.G. Rogers and L.W. Shapiro, Some correspondences involving the Schröder numbers and relations, In: Combinatorial Mathematics, D.A. Holton and J.Seberry, Eds., Lecture Notes in Mathematics, Vol. 686, Springer-Verlag, 1978, pp. 267每274.

12. R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

13. J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995) 247每262.