Computing generating functions of ordered partitions with the transfer-matrix method

Abstract

An ordered partition of $[n]:=\{1,2,\ldots, n\}$ is a sequence of disjoint and nonempty subsets, called blocks, whose union is $[n]$. The aim of this paper is to compute some generating functions of ordered partitions by the transfer-matrix method. In particular, we prove several conjectures of Steingrímsson, which assert that the generating function of some statistics of ordered partitions give rise to a natural $q$-analogue of $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind.

Keywords

• determinants
• ordered partitions
• euler-mahonian statistics
• $q$-stirling numbers of second kind
• transfer-matrix method
• [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]