×

Some combinatorial interpretations of \(q\)-analogs of Schröder numbers. (English) Zbl 0934.05008

Recall that the Schröder numbers \(R_n\) are defined by the recurrence relation \(R_0=1\), \(R_{n+1}= R_n+ \sum^n_{k=0} R_kR_{n-k}\). The paper studies two \(q\)-analogues of the Schröder numbers, \(S_n(q)\) and \(\overline S_n(x,q)\), where these \(q\)-analogues are defined by the recurrences \[ S_0(q)= 1,\quad S_{n+1}(q)= S_n(q)+ \sum^n_{k=0} S_k(q) S_{n-k}(q) q^{n- k+1}, \] and \[ \overline S_1(x,q)= 2xq,\quad \overline S_{n+1}(x,q)= 2xq\overline S_n(x,q)+\overline S_n(xq,q)+ \sum^{n-1}_{k= 0}\overline S_k(xq,q)\overline S_{n-k}(x, q). \] Recall that Schröder paths are paths from \((0,0)\) to \((n,n)\) using steps \((0,1)\), \((1,0)\) and \((1,1)\), and Schröder paths are enumerated by the Schröder numbers. It turns out that the generating function \(S_n(q)\) counts Schröder paths by area. The number of permutations of \(1,2,\dots, n\) avoiding the patterns 4231 and 4132 is \(R_{n-1}\), and the generating function \(S_{n-1}(q)\) counts permutations of \(1,2,\dots, n\) avoiding the patterns 4231 and 4132 by the number of inversions. The generating function of 1-colored parallelogram polyominoes having parameter \(2n\) according to their width and area is equal to \(\overline S_{n-1}(x,q)\).

MSC:

05A15 Exact enumeration problems, generating functions
05A30 \(q\)-calculus and related topics
05B50 Polyominoes
Full Text: DOI

References:

[1] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, A methodology for plane tree enumeration, Discrete Math.180 (1998) 45–64. · Zbl 0904.05004 · doi:10.1016/S0012-365X(97)00122-2
[2] R.J. Baxter, Exactly, Solved Models in Statistical Mechanics, Academic Press, New York, 1982. · Zbl 0538.60093
[3] J. Bonin, L. Shapiro, and R. Simion, Someq-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Stat. Planning and Inference34 (1993) 35–55. · Zbl 0783.05008 · doi:10.1016/0378-3758(93)90032-2
[4] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons, Discrete Math.154 (1996) 1–25. · Zbl 0858.05006 · doi:10.1016/0012-365X(95)00003-F
[5] M. Bousquet-Mélou, Percolation models and animals, Europ. J. Combin.17 (1996) 343–369. · Zbl 0849.60089 · doi:10.1006/eujc.1996.0029
[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. · Zbl 0953.82027 · doi:10.1023/B:JOSS.0000026731.35385.93
[7] R. Brak, A. Owczarek, and T. Prellberg, Exact scaling behaviour of partially convex vesicles, J. Stat. Phys.76 (1994) 1101–1128. · Zbl 0839.60099 · doi:10.1007/BF02187057
[8] A.R. Conway, R. Brak, and A.J. Guttmann, Directed animals on two-dimensional lattices, J. Phys. A26 (1993) 3085–3091. · doi:10.1088/0305-4470/26/13/013
[9] M. Delest and J.M. Fédou, Enumeration of skew Ferrers diagrams, Discrete Math.112 (1993) 65–79. · Zbl 0778.05002 · doi:10.1016/0012-365X(93)90224-H
[10] M.E. Fisher, Walks, wall, wetting and melting, J. Stat. Phys.34 (1984) 667–729. · Zbl 0589.60098 · doi:10.1007/BF01009436
[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 Applications22 (1988) 361–388. · Zbl 0669.05002
[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). · Zbl 1102.82316
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.