Standard Paths in Another Composition Poset

Jan Snellman

Abstract


Bergeron, Bousquet-Mélou and Dulucq [Ann. Sci. Math. Québec 19 (1995), 139–151] enumerated paths in the Hasse diagram of the following poset: the underlying set is that of all compositions, and a composition $\mu$ covers another composition $\lambda$ if $\mu$ can be obtained from $\lambda$ by adding $1$ to one of the parts of $\lambda$, or by inserting a part of size $1$ into $\lambda$.

We employ the methods they developed in order to study the same problem for the following poset, which is of interest because of its relation to non-commutative term orders : the underlying set is the same, but $\mu$ covers $\lambda$ if $\mu$ can be obtained from $\lambda$ by adding $1$ to one of the parts of $\lambda$, or by inserting a part of size $1$ at the left or at the right of $\lambda$. We calculate generating functions for standard paths of fixed width and for standard paths of height $\le 2$.


Full Text: PDF