×

zbMATH — the first resource for mathematics

Chains of maximum length in the Tamari lattice. (English) Zbl 1326.06006
Summary: The Tamari lattice \(\mathcal T_n\) was originally defined on bracketings of a set of \(n+1\) objects, with a cover relation based on the associativity rule in one direction. Although in several related lattices the number of maximal chains is known, quoting Knuth, “The enumeration of such paths in Tamari lattices remains mysterious.”
The lengths of maximal chains vary over a great range. In this paper, we focus on the chains with maximum length in these lattices. We establish a bijection between the maximum length chains in the Tamari lattice and the set of standard shifted tableaux of staircase shape. We thus derive an explicit formula for the number of maximum length chains, using the Thrall formula for the number of shifted tableaux. We describe the relationship between chains of maximum length in the Tamari lattice and certain maximal chains in weak Bruhat order on the symmetric group, using standard Young tableaux. Additionally, recently Bergeron and Préville-Ratelle introduced a generalized Tamari lattice. Some of the results mentioned above carry over to their generalized Tamari lattice.

MSC:
06A07 Combinatorics of partially ordered sets
05A15 Exact enumeration problems, generating functions
05E05 Symmetric functions and generalizations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. · Zbl 1110.05001
[2] Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, J. Combin. Theory Ser. A 116 (2009), no. 1, 55 – 75. · Zbl 1161.06001 · doi:10.1016/j.jcta.2008.05.005 · doi.org
[3] Mireille Bousquet-Mélou, Éric Fusy, and Louis-François Préville-Ratelle, The number of intervals in the \?-Tamari lattices, Electron. J. Combin. 18 (2011), no. 2, Paper 31, 26. · Zbl 1262.05005
[4] Jason Bandlow and Kendra Killpatrick, An area-to-inv bijection between Dyck paths and 312-avoiding permutations, Electron. J. Combin. 8 (2001), no. 1, Research Paper 40, 16. · Zbl 0981.05006
[5] François Bergeron and Louis-François Préville-Ratelle, Higher trivariate diagonal harmonics via generalized Tamari posets, J. Comb. 3 (2012), no. 3, 317 – 341. · Zbl 1291.05213 · doi:10.4310/JOC.2012.v3.n3.a4 · doi.org
[6] Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945 – 3975. · Zbl 0886.05126
[7] A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305 – 313. · Zbl 0030.16701
[8] Paul Edelman and Curtis Greene, Balanced tableaux, Adv. in Math. 63 (1987), no. 1, 42 – 99. · Zbl 0616.05005 · doi:10.1016/0001-8708(87)90063-6 · doi.org
[9] Haya Friedman and Dov Tamari, Problèmes d’associativité: Une structure de treillis finis induite par une loi demi-associative, J. Combinatorial Theory 2 (1967), 215 – 242 (French). · Zbl 0158.01904
[10] Markus Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. in Appl. Math. 30 (2003), no. 4, 607 – 632. · Zbl 1020.05008 · doi:10.1016/S0196-8858(02)00501-8 · doi.org
[11] Mark D. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math. 99 (1992), no. 1-3, 79 – 113. · Zbl 0760.05093 · doi:10.1016/0012-365X(92)90368-P · doi.org
[12] Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas, Permutahedra and generalized associahedra, Adv. Math. 226 (2011), no. 1, 608 – 640. · Zbl 1233.20035 · doi:10.1016/j.aim.2010.07.005 · doi.org
[13] Samuel Huang and Dov Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. Combinatorial Theory Ser. A 13 (1972), 7 – 13. · Zbl 0248.06003
[14] Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0302.68010
[15] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math. 27 (2001), no. 2-3, 510 – 530. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000). · Zbl 0994.05001 · doi:10.1006/aama.2001.0747 · doi.org
[16] George Markowsky, Primes, irreducibles and extremal lattices, Order 9 (1992), no. 3, 265 – 290. · Zbl 0778.06007 · doi:10.1007/BF00383950 · doi.org
[17] Nathan Reading, Cambrian lattices, Adv. Math. 205 (2006), no. 2, 313 – 353. · Zbl 1106.20033 · doi:10.1016/j.aim.2005.07.010 · doi.org
[18] Richard P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), no. 4, 359 – 372. · Zbl 0587.20002 · doi:10.1016/S0195-6698(84)80039-6 · doi.org
[19] Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. · Zbl 0928.05001
[20] Dov Tamari, The algebra of bracketings and their enumeration, Nieuw Arch. Wisk. (3) 10 (1962), 131 – 146. · Zbl 0109.24502
[21] R. M. Thrall, A combinatorial problem, Michigan Math. J. 1 (1952), 81 – 88. · Zbl 0049.01001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.