Proper Partitions of a Polygon and \(k\)-Catalan Numbers

Abstract

Let \(P\) be a polygon whose vertices have been colored (labeled) cyclically with the numbers \(1, 2, \ldots, c\). Motivated by conjectures of Propp, we are led to consider partitions of \(P\) into \(k\)-gons which are proper in the sense that each \(k\)-gon contains all \(c\) colors on its vertices. Counting the number of proper partitions involves a generalization of the \(k\)-Catalan numbers. We also show that in certain cases, any proper partition can be obtained from another by a sequence of moves called flips.