Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to use the vertex coalescing method like the one mentioned here, page 10, to count: Number of dissections of a polygon using non-intersecting diagonals into even number of regions.

I am trying to frame a recursion, and I think I have this:

Let $a_{k, n}$ be the number of dissections of an $n$-vertex polygon into $k$ regions. Then, For a given number of regions: call it $a_{k, n+1}$, the number of dissections that merge into the same number of regions $k$ for $n$ vertices = (degree of a fixed vertex - $1$) summed over all members of $a_{k, n}$.

Triangles are also coalesced to reduce the number of regions, so I think there is some relation between $a_{k, n+1}$ and $a_{k-1, n}$.

Any idea on how to go about this problem?

Edit: Any other approaches to solving this problem are also welcome.

share|cite|improve this question
I don't see your relation easily. You want to remove one vertex and one diagonal? – Hagen von Eitzen Dec 19 '12 at 8:00
I want to remove one edge, or coalesce two vertices together, going from n+1 to n. – Mikhail Dec 19 '12 at 8:13
The problem is that there are many cases to consider, e.g. removing a vertex without diagonal may decrease the number of regions or not ... – Hagen von Eitzen Dec 19 '12 at 11:06

Your Answer


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

Browse other questions tagged or ask your own question.