## 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