Quasi-symmetric functions and up–down compositions

Carlitz (1973) [5] and Rawlings (2000) [13] studied two different analogues of up–down permutations for compositions with parts in {1,…,n}{1,…,n}. Cristea and Prodinger (2008/2009) [7] studied additional analogues for compositions with unbounded parts. We show that the results of Carlitz, Rawlings, and Cristea and Prodinger on up–down compositions are special cases of four different analogues of generalized Euler numbers for compositions. That is, for any s≥2s≥2, we consider classes of compositions that can be divided into an initial set of blocks of size ss followed by a block of size jj where 0≤j≤s−10≤j≤s−1. We then consider the classes of such compositions where all the blocks are strictly increasing (weakly increasing) and there are strict (weak) decreases between blocks. We show that the weight generating functions of such compositions w=w1⋯wmw=w1⋯wm, where the weight of ww is ∏i=1mzwi, are always the quotients of sums of quasi-symmetric functions. Moreover, we give a direct combinatorial proof of our results via simple involutions.