A recursion on maximal chains in the Tamari lattices

作者：Nelson Luke^*

来源：Discrete Mathematics, 2017, 340(4): 661-677.

DOI：10.1016/j.disc.2016.11.030

• Tamari lattice
• Number of maximal chains
• Enumeration
• Recursion
• Tableaux

The Tamari lattices have been intensely studied since their introduction by Dov Tamari around 1960. However oddly enough, a formula for the number of maximal chains is still unknown. This is due largely to the fact that maximal chains in the nth Tamari lattice range in length from n - 1 to (n/2). In this note, we treat vertices in the lattice as Young diagrams and identify maximal chains as certain tableaux. For each i >= - 1, we define c(i)(n) as the set of maximal chains in 77, of length n + i. We give a recursion for #C-i(n) and an explicit formula based on predetermined initial values. The formula is a polynomial in n of degree 3i+3. For example, the number of maximal chains of length n in T-n is #C-0(n) = (n/3) The formula has a combinatorial interpretation in terms of a special property of maximal chains.

• 出版日期2017-4