Counting smaller elements in the Tamari and m-Tamari lattices
Counting smaller elements in the Tamari and m-Tamari lattices
复制标题
计算 Tamari 和 m-Tamari 晶格中较小的元素
DOI：
10.1016/j.jcta.2015.03.004
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
V. Pons
中科院分区：
文献类型：
--
作者：
G. Châtel;V. Pons
我们引入了新的组合对象，即区间偏序，它对 Tamari 格的区间进行编码。然后，我们找到了 Chapoton 描述的 Tamari 区间函数方程中出现的双线性算子的组合解释。因此，我们检索这个函数方程并证明从每棵树 T 上的双线性算子递归计算的多项式计算了 Tamari 阶中小于 T 的树的数量。然后我们证明类似的 (m+1) 线性算子也可以用在 m-Tamari 区间的函数方程中。我们解释如何用 (m+1)-ary 树或某一类二叉树来解释 m-Tamari 格。然后，我们使用区间偏序集来恢复 m-Tamari 区间的函数方程，并证明一个广义公式，用于计算 m-Tamari 格中小于或等于给定树的元素数量。
We introduce new combinatorial objects, the interval-posets, that encode intervals of the Tamari lattice. We then find a combinatorial interpretation of the bilinear operator that appears in the functional equation of Tamari intervals described by Chapoton. Thus, we retrieve this functional equation and prove that the polynomial recursively computed from the bilinear operator on each tree T counts the number of trees smaller than T in the Tamari order. Then we show that a similar (m+ 1)-linear operator is also used in the functional equation of m-Tamari intervals. We explain how the m-Tamari lattices can be interpreted in terms of (m+ 1)-ary trees or a certain class of binary trees. We then use the interval-posets to recover the functional equation of m-Tamari intervals and to prove a generalized formula that counts the number of elements smaller than or equal to a given tree in the m-Tamari lattice.