A recursion on maximal chains in the Tamari lattices

详细信息    查看全文

• 作者：Luke Nelson ^{lenelson@asu.edu nelson85225@gmail.com}
• 关键词：Tamari lattice ; Number of maximal chains ; Enumeration ; Recursion ; Tableaux
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：340
• 期：4
• 页码：661-677
• 全文大小：640 K
• 卷排序：340

文摘

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 nnth Tamari lattice TnTn range in length from n−1n−1 to n2. In this note, we treat vertices in the lattice as Young diagrams and identify maximal chains as certain tableaux. For each i≥−1i≥−1, we define Ci(n)Ci(n) as the set of maximal chains in TnTn of length n+in+i. We give a recursion for #Ci(n)#Ci(n) and an explicit formula based on predetermined initial values. The formula is a polynomial in nn of degree 3i+33i+3. For example, the number of maximal chains of length nn in TnTn is #C0(n)=n3. The formula has a combinatorial interpretation in terms of a special property of maximal chains.