Quasi-symmetric functions and up–down compositions

详细信息    查看全文

• 作者：Evan Fuller^a ; ^{fullere@mail.montclair.edu"" rel=""nofollow} ; Jeffrey Remmel^b ; ^{remmel@math.ucsd.edu"" rel=""nofollow}
• 关键词：Alternating permutation ; Euler number ; Quasi-symmetric function ; Involution
• 刊名：Discrete Mathematics
• 出版年：2011
• 出版时间：28 August 2011
• 年：2011
• 卷：311
• 期：16
• 页码：1754-1767
• 全文大小：277 K

文摘

Carlitz (1973) [5] and Rawlings (2000) [13] studied two different analogues of up–down permutations for compositions with parts in {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≥2, we consider classes of compositions that can be divided into an initial set of blocks of size s followed by a block of size j where 0≤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=w₁w_m, where the weight of w is , are always the quotients of sums of quasi-symmetric functions. Moreover, we give a direct combinatorial proof of our results via simple involutions.