Standard paths in another composition poset

Jan Snellman

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

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$.

Détail

DOI : 10.37236/1829

Classification : 06A07, 05A15
Mots-clés : enumeration of paths, composition posets, Hasse diagram, standard paths