It is well known that the Catalan numbers count triangulations of a polygon. If one colors the vertices of the polygon and considers triangulations which are proper (in a sense similar to that of proper colorings in Graph Theory) then James Propp conjectured similar enumeration formulas. We prove Propp's conjectures and also discuss how one can move from one proper partition to another by a sequence of moves called flips.
Probability and Combinatorics
Tuesday, December 6, 2005 - 4:00pm
Bruce Sagan
Michigan State and Rutgers