Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


The enumeration of generalized Tamari intervals

Authors: Louis-François Préville-Ratelle and Xavier Viennot
Journal: Trans. Amer. Math. Soc. 369 (2017), 5219-5239
MSC (2010): Primary 06A07
Published electronically: March 17, 2017
MathSciNet review: 3632566
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For any finite path $ v$ on the square grid consisting of north and east unit steps, starting at (0,0), we construct a poset Tam$ (v)$ that consists of all the paths weakly above $ v$ with the same number of north and east steps as $ v$. For particular choices of $ v$, we recover the traditional Tamari lattice and the $ m$-Tamari lattice.

Let $ \overleftarrow {v}$ be the path obtained from $ v$ by reading the unit steps of $ v$ in reverse order, replacing the east steps by north steps and vice versa. We show that the poset Tam$ (v)$ is isomorphic to the dual of the poset Tam $ (\overleftarrow {v})$. We do so by showing bijectively that the poset Tam$ (v)$ is isomorphic to the poset based on rotation of full binary trees with the fixed canopy $ v$, from which the duality follows easily. This also shows that Tam$ (v)$ is a lattice for any path $ v$. We also obtain as a corollary of this bijection that the usual Tamari lattice, based on Dyck paths of height $ n$, can be partitioned into the (smaller) lattices Tam$ (v)$, where the $ v$ are all the paths on the square grid that consist of $ n-1$ unit steps.

We explain possible connections between the poset Tam$ (v)$ and (the combinatorics of) the generalized diagonal coinvariant spaces of the symmetric group.

References [Enhancements On Off] (What's this?)

  • [1] D. Armstrong, Rational Catalan combinatorics 1,2,3,4, available on personal website: armstrong/activity.html, 2012-2013.
  • [2] Drew Armstrong, Nicholas A. Loehr, and Gregory S. Warrington, Rational parking functions and Catalan numbers, Ann. Comb. 20 (2016), no. 1, 21-58. MR 3461934
  • [3] Drew Armstrong, Brendon Rhoades, and Nathan Williams, Rational associahedra and noncrossing partitions, Electron. J. Combin. 20 (2013), no. 3, Paper 54, 27 pp. MR 3118962
  • [4] Francois Bergeron, Adriano Garsia, Emily Sergel Leven, and Guoce Xin, Compositional $ (km,kn)$-shuffle conjectures, Int. Math. Res. Not. IMRN no. 14 (2016), 4229-4270. MR 3556418
  • [5] François Bergeron, Algebraic combinatorics and coinvariant spaces, CMS Treatises in Mathematics, Canadian Mathematical Society, Ottawa, ON; A K Peters, Ltd., Wellesley, MA, 2009. MR 2538310
  • [6] 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. MR 3029440
  • [7] M. T. L. Bizley, Derivation of a new formula for the number of minimal lattice paths from $ (0,0)$ to $ (km,kn)$ having just $ t$ contacts with the line $ my=nx$ and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuar. 80 (1954), 55-62. MR 0061567
  • [8] Mireille Bousquet-Mélou, Guillaume Chapuy, and Louis-François Préville-Ratelle, The representation of the symmetric group on $ m$-Tamari intervals, Adv. Math. 247 (2013), 309-342. MR 3096799
  • [9] Mireille Bousquet-Mélou, Éric Fusy, and Louis-François Préville-Ratelle, The number of intervals in the $ m$-Tamari lattices, Electron. J. Combin. 18 (2011), no. 2, Paper 31, 26 pp. MR 2880681
  • [10] F. Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, Sém. Lothar. Combin. 55 (2005/07), Art. B55f, 18 pp (French, with English and French summaries). MR 2264942
  • [11] Grégory Chatel and Viviane Pons, Counting smaller trees in the Tamari order, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2013, pp. 433-444 (English, with English and French summaries). MR 3091011
  • [12] Marie-Pierre Delest and Gérard Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1984), no. 1-2, 169-206. MR 774044
  • [13] Wenjie Fang and Louis-François Préville-Ratelle, The enumeration of generalized Tamari intervals, European J. Combin. 61 (2017), 69-84. MR 3588709
  • [14] 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). MR 0238984
  • [15] Eugene Gorsky, Mikhail Mazin, and Monica Vazirani, Affine permutations and rational slope parking functions, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), Discrete Math. Theor. Comput. Sci. Proc., AT, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2014, pp. 887-898 (English, with English and French summaries). MR 3466430
  • [16] Eugene Gorsky and Andrei Negut, Refined knot invariants and Hilbert schemes, J. Math. Pures Appl. (9) 104 (2015), no. 3, 403-435 (English, with English and French summaries). MR 3383172
  • [17] James Haglund, The $ q$,$ t$-Catalan numbers and the space of diagonal harmonics, University Lecture Series, vol. 41, American Mathematical Society, Providence, RI, 2008. With an appendix on the combinatorics of Macdonald polynomials. MR 2371044
  • [18] Mark Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), no. 2, 371-407. MR 1918676
  • [19] Mark D. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), no. 1, 17-76. MR 1256101
  • [20] Tatsuyuki Hikita, Affine Springer fibers of type $ A$ and combinatorics of diagonal coinvariants, Adv. Math. 263 (2014), 88-122. MR 3239135
  • [21] Jean-Louis Loday and María O. Ronco, Hopf algebra of the planar binary trees, Adv. Math. 139 (1998), no. 2, 293-309. MR 1654173
  • [22] Jean-Louis Loday and María O. Ronco, Order structure on the algebra of permutations and of planar binary trees, J. Algebraic Combin. 15 (2002), no. 3, 253-270. MR 1900627
  • [23] L.-F. Préville-Ratelle and X. Viennot, An extension of Tamari lattices, FPSAC 2015, Daejeon, Korea (DMTCS) (2015), 133-144.
  • [24] Richard P. Stanley, , and 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. MR 1676282
  • [25] Robert Steinberg, Differential equations invariant under finite reflection groups, Trans. Amer. Math. Soc. 112 (1964), 392-400. MR 0167535
  • [26] Dov Tamari, The algebra of bracketings and their enumeration, Nieuw Arch. Wisk. (3) 10 (1962), 131-146. MR 0146227
  • [27] X. Viennot, Canopy of binary trees, intervals in associahedra and exclusion model in physics, Workshop: Recent trends in Algebraic and Geometric Combinatorics, ICMAT, Madrid, Nov 2013, slides of the talk at:

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 06A07

Retrieve articles in all journals with MSC (2010): 06A07

Additional Information

Louis-François Préville-Ratelle
Affiliation: Instituto de Mathemática y Física, Universidad de Talca, 2 norte 685, Talca, Chile

Xavier Viennot
Affiliation: CNRS, LABRI, Université de Bordeaux, Bordeaux, France

Received by editor(s): June 17, 2014
Received by editor(s) in revised form: August 22, 2015, August 27, 2015, and June 20, 2016
Published electronically: March 17, 2017
Additional Notes: The first author was supported by the government of Chile under Proyecto Fondecyt 3140298.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society