M. Ishikawa, A. Kasraoui and J. Zeng

Euler-Mahonian Statistics On Ordered Set Partitions

Abstract. An ordered partition with $k$ blocks of $[n]:=\{1,2,\ldots, n\}$ is a sequence of $k$ disjoint and nonempty subsets, called blocks, whose union is $[n]$. Clearly the number of such ordered partitions is $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind. A statistic on ordered partitions of $[n]$ with $k$ blocks is called an Euler-Mahonian statistic if its generating polynomial is $[k]_q!S_q(n,k)$, which is a natural $q$-analogue of $k!S(n,k)$. Motivated by Steingrimsson's conjectures dating back to 1997, we consider two different methods to produce Euler-Mahonian statistics on ordered set partitions: (a) we give a bijection between ordered partitions and weighted Motzkin paths by using a variant of Francon-Viennot's bijection to derive many Euler-Mahonian statistics by expanding the generating function of $[k]_q!S_q(n,k)$ as an explicit continued fraction; (b) we encode ordered partitions by walks in some digraphs and then derive new Euler-Mahonian statistics by computing their generating functions using the transfer-matrix method. In particular, we prove several conjectures of Steingrimsson.
Back to List of publications.