Euler-Mahonian statistics on ordered set partitions. (English) Zbl 1189.05021
Summary: An ordered partition with \(k\) blocks of \([n]:=\{1,2,\cdots, 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 Steingrímsson’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 Françon – 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 Steingrímsson.
MSC:
05A18 | Partitions of sets |
05A15 | Exact enumeration problems, generating functions |
05A30 | \(q\)-calculus and related topics |