Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I have a regular n-gon. I want to draw some noncrossing diagonals to subdivide it into smaller polygons. In how many ways can I do this? The vertices are unlabeled, so I don't distinguish between rotations or reflections of a given subdivision.

A triangle has 1 subdivision (do nothing!); a square has 2, a pentagon has 3, and a hexagon has at least 9 -- I'm not certain that I haven't missed any.

In fact, what I would really like is not just a count, but an algorithm for generating such subdivisions. There are obvious algorithms that generate some subdivisions multiple times, but what I'd really like is an algorithm that only generates distinct subdivisions, and that generates all of them.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

I think this could be A001004 in Sloane's Encyclopedia. It's hard to be sure without checking the references given there; the sequence is defined as "Number of symmetric dissections of a polygon.", which may or may not be what you mean. (In particular, the OEIS claims the next term is 20 and I'm afraid to try to check that.)

share|improve this answer
    
I would have sworn that I had checked this on OEIS, but I guess I was remembering something else. Following the reference, it does indeed appear to be what I am looking for. Actually, the site it points to (algo.inria.fr/bsolve) has a lot of interesting enumerations. Now I'll just have to chase down further references (the paper gives a few) to see how this was obtained, and if it contains the algorithm I want. –  Gabe Cunningham Oct 24 '09 at 23:45
    
Taking a look at the paper, this result was obtained by enumerating cell clusters of various types. A cell cluster is the result of gluing together several regular polygons along their boundary, and a subdivision of an n-gon is equivalent to a cell cluster that has an outer boundary of n sides. Anyway, I get the counts I want -- in fact, I even get a table for the number of subdivisions of an n-gon into k polygons -- but no algorithm. Guess I'll have to think some more about the latter. –  Gabe Cunningham Oct 27 '09 at 13:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.