2006-18: Proper Partitions of a Polygon and $k$-Catalan Numbers

DIMACS TR: 2006-18

Proper Partitions of a Polygon and $k$-Catalan Numbers

Author: Bruce E. Sagan

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-18.ps.gz

DIMACS Home Page