Partitions, Kostka Polynomials and Pairs of Trees

Abstract

Bennett et al. presented a recursive algorithm to create a family of partitions from one or several partitions. They were mainly interested in the cases when we begin with a single square partition or with several partitions with only one part. The cardinalities of those families of partitions are the Catalan and ballot numbers, respectively. In this paper we present a non-recursive description for those families and prove that the generating function of the size of those partitions is a Kostka number. We also present bijections between those sets of partitions and sets of trees and forests enumerated by the Catalan an ballot numbers, respectively.