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,\dots ,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.