Annals of Combinatorics 3 (1999) 171-190

Some Combinatorial Interpretations of q-Analogs of Schröder Numbers

E. Barcucci1, A. Del Lungo2, E. Pergola1, and R. Pinzani1

1Dipartimento di Sistemi e Informatica, Universitàdi Firenze, Via Lombroso 6/17, 50134, Firenze, Italy
{barcucci, elisa, pinzani}

2Dipartimento di Matematica, Universitô di Siena, Via del Capitano 15, 53100 Siena, Italy

Received November 1, 1998

AMS Subject Classification: 05A15, 05A30, 05B50

Abstract. We introduce two definitions of Schröder number q-analogs and show some combinatorial interpretations of these q-numbers. We use the following combinatorial objects for these interpretations: Schröder paths, 1-colored parallelogram polyominoes and permutations with forbidden subsequences (4231, 4132). We enumerate these objects according to various parameters by means of a recent q-counting technique. We prove that the first q-Schröder number enumerates of Schröder paths with respect to area and the number of permutation inversions, while the second one counts the 1-colored parallelogram polyominoes according to their width and area. Finally, we illustrate some relations among the parameters characterizing the combinatorial objects.

Keywords: q-analog numbers, Schröder numbers, combinatorial interpretations, polyominoes, permutations, paths hard squares, hard hexagons


1.  E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, A methodology for plane tree enumeration, Discrete Math. 180 (1998) 45–64.

2.  R.J. Baxter, Exactly, Solved Models in Statistical Mechanics, Academic Press, New York, 1982.

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. Planning and Inference 34 (1993) 35–55.

4.  M. Bousquet-Mèlou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996) 1–25.

5.  M. Bousquet-Mèlou, Percolation models and animals, Europ. J. Combin. 17 (1996) 343–369.

6.  R. Brak, J.W. Essam, and A. Owczarek, New results for directed vesicles and chains near an attractive wall, J. Stat. Phys. 93 (1998) 155–192.

7.  R. Brak, A. Owczarek, and T. Prellberg, Exact scaling behaviour of partially convex vesicles, J. Stat. Phys. 76 (1994) 1101–1128.

8.  A.R. Conway, R. Brak, and A.J. Guttmann, Directed animals on two-dimensional lattices, J. Phys. A 26 (1993) 3085–3091.

9.  M. Delest and J.M. Fèdou, Enumeration of skew Ferrers diagrams, Discrete Math. 112 (1993) 65–79.

10.  M.E. Fisher, Walks, wall, wetting and melting, J. Stat. Phys. 34 (1984) 667–729.

11.  I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, John Wiley \& Sons, New York, 1983.

12.  D. Gouyou-Beauchamps and B. Vauquelin, Deux propriètès combinatoires des nombres de Schröder, Theoretical Informatics and Applications 22 (1988) 361–388.

13.  O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, Thèse de l'Universitè de Bordeaux I, 1996.

14.  T. Prellberg and R. Brak, Critical exponents from non-linear functional equations for directed cluster models, J. Stat. Phys. (1994).

15.  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.

16.  J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph. D. Thesis, MIT, Cambridge, 1990.

Get the DVI| PS | PDF file of this abstract.