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

DOI:
https://doi.org/10.1090/tran/7004

Published electronically:
March 17, 2017

MathSciNet review:
3632566

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

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

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

- [1]
D. Armstrong,
*Rational Catalan combinatorics 1,2,3,4*, available on personal website: http://www.math.miami.edu/ 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 -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 to having just contacts with the line 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 -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 -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 ,-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 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: http://www.xavierviennot.org/xavier/exposes/files/Madrid/nov13v2.pdf.

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

Email:
preville-ratelle@inst-mat.utalca.cl

**Xavier Viennot**

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

Email:
viennot@xavierviennot.org

DOI:
https://doi.org/10.1090/tran/7004

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