# Triangulation proof

1. Oct 4, 2009

### dancergirlie

1. The problem statement, all variables and given/known data

A triangulation of a convex polygon is a decomposition of the polygon into
triangles whose interiors do not overlap and whose vertices lie at vertices of
the polygon. Prove that there are Cn−2 ways to triangulate an n-sided convex
polygon

2. Relevant equations

cn= (1/2)(2n choose n)

3. The attempt at a solution

I tried a proof by induction:

let n=3.
there is only one way to triangulate a triangle, and
cn-2=c1=(1/2)(2 choose 1)=1. So the statement holds for n=3

now assume the statement holds for n=k
So the number of ways to triangulate a k-sided polygon is Ck-2=(1/2)(2(k-2) choose k-2)

Now let n=k+1

This is where I get stuck and I dont' know what to do.... any help/hints would be appreciated.

2. Oct 8, 2009

### tiny-tim

Hi dancergirlie!

(try using the X2 and X2 tags just above the Reply box )

I don't think that formula is right …

For n = 4, there are only 2 solutions, but C4-2 = C2 = (1/2)4C2 = 3.

3. Oct 9, 2009

### tiny-tim

Perhaps I'm misunderstanding the question, but i'm getting …

For n = 5, there are 5 solutions, all "3-fans".

For n = 6, there are 13 solutions, 6 "4-fans", 6 "pairs-of-2-fans", and 1 with a central triangle.

If I'm counting correctly (and of course I may not be ), I don't see how 13 can come out of a "choose" function.

4. Oct 9, 2009

### tiny-tim

Catalan numbers

oops … I did miss one … there are 2 with a central triangle, making 14.

So the number of triangulations of an n-sided polygon for n = 3 4 5 and 6 are 1 2 5 and 14, which look like the Catalan numbers, see http://en.wikipedia.org/wiki/Catalan_number

They're 2nCn/(n+1), not 2nCn/2 as in the original question.

They're generated by Cn+1 = ∑i=0n CiCn-i, which is fairly easy to prove for triangulations of a polygon.

(there's a proof of the more direct equation (n+2)Cn+1 = (4n+2)Cn in the wikipedia article, but I'm afraid I don't understand it at all )