Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.