Maximal chains of subwords and up-down sequences of permutations

AbstractThe free monoid generated by two letters is a poset for the relation “u is a subword of v.” Two bijections between permutations and maximal chains starting from the empty word, involving the classical up-down sequence and the so-called odd-even height sequence, are given. For arbitrary alphabet, symmetric polynomials in s variables appear, generalizing the Eulerian polynomials and refining polynomials studied by Carlitz, Gessel, Riordan, and Stanley. The skewhook property of Foulkes is extended