×

Combinatorial statistics on non-crossing partitions. (English) Zbl 0803.05003

Author’s abstract: Four statistics, \(ls\), \(rb\), \(rs\), and \(lb\), previously studied on all partitions of \(\{1,2,\dots,n\}\), are applied to non-crossing partitions. We consider single and joint distributions of these statistics and prove equidistribution results. We obtain \(q\)- and \(p,q\)-analogues of Catalan and Narayana numbers which refine the rank symmetry and unimodality of the lattice of non-crossing partitions. Two unimodality conjectures, one of which pertains to Young’s lattice, are stated. We exhibit relations between statistics on non-crossing partitions and established permutation statistics applied to restricted permutations. All our proofs are combinatorial, relying on the construction of bijective correspondences and on structural properties of the lattice of non-crossing partitions.

MSC:

05A18 Partitions of sets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., Combinatorial Theory (1979), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0415.05001
[2] Andrews, G., Catalan numbers, \(q\)-Catalan numbers and hypergeometric series, J. Combin. Theory Ser. A, 44, 267-273 (1987) · Zbl 0607.05006
[3] J. Bonin, L. Shapiro, and R. Simon\(q\)J. Statist. Plann. Inference; J. Bonin, L. Shapiro, and R. Simon\(q\)J. Statist. Plann. Inference
[4] Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht
[5] Edelman, P., Chain enumeration and non-crossing partitions, Discrete Math., 31, 171-180 (1980) · Zbl 0443.05011
[6] Edelman, P., Multichains, non-crossing partitions and trees, Discrete Math., 40, 171-179 (1982) · Zbl 0496.05007
[7] P. Edelman and R. SimionDiscrete Math.; P. Edelman and R. SimionDiscrete Math. · Zbl 0795.05013
[8] Foata, D.; Zeilberger, D., Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math., 83, 31-59 (1990) · Zbl 0738.05001
[9] Fürlinger, J.; Hofbauer, J., \(q\)-Catalan numbers, J. Combin. Theory Ser. A, 40, 248-264 (1985) · Zbl 0581.05006
[10] Garsia, A.; Remmel, J., \(Q\)-counting rook configurations and a formula of Frobenius, J. Combin. Theory Ser. A, 41, 246-275 (1986) · Zbl 0598.05007
[11] Gould, H. W., The \(q\)-Stirling numbers of the first and second kinds, Duke Math. J., 28, 281-289 (1961) · Zbl 0201.33601
[12] Greene, C.; Kleitman, D., Proof techniques in the theory of finite sets, (Rota, G.-C, Studies in Combinatorics. Studies in Combinatorics, MAA Studies in Mathematics, Vol. 17 (1978), MAA: MAA Washington, DC) · Zbl 0409.05012
[13] Knuth, D., (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA)
[14] Kreweras, G., Sur les partitions noncroisées d’un cycle, Discrete Math., 1, 333-350 (1972) · Zbl 0231.05014
[15] Milne, S., Restricted growth functions, rank row matchings of \(p\) lattices, and \(q\)-Stirling numbers, Adv. Math., 43, 173-196 (1982) · Zbl 0482.05012
[16] Rawlings, D., The ABC’s of classical enumeration, Ann. Sci. Math. Québec, 10, 207-235 (1986) · Zbl 0608.05006
[17] Riordan, J., An Introduction to Combinatorial Analysis (1978), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ
[18] Simion, R.; Schmidt, F., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002
[19] Simion, R.; Ullman, D., On the structure of the lattice of non-crossing partitions, Discrete Math., 98, 193-206 (1991) · Zbl 0760.05004
[20] Stanley, R. P., (Enumerative Combinatorics, Vol. 1 (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Monterey, CA) · Zbl 0608.05001
[21] D. Stanton; D. Stanton
[22] Virnnoy, G., Une théorie combinatoire des polynômes orthogonaux généraux, (Université du Québec à Montréal Lecture Notes (1983)), II-30-II-34
[23] Wachs, ]M; White, D., \(pq\)-Stirling numbers and set partition statistics, J. Combin. Theory Ser. A, 56, 27-46 (1991) · Zbl 0732.05004
[24] West, J., Permutations with Forbidden Subsequences and Stock-Sortable Permutations, (Ph.D. Thesis (1990), MIT)
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.