DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

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

Masao Ishikawa, Anisse Kasraoui, Jiang Zeng

Abstract


An ordered partition of [n]:={1,2,…, 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.

Full Text: PDF

Valid XHTML 1.0 Transitional