0
$\begingroup$

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.

  • 0
    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 ...2012-12-19

0 Answers 0