Triangulation of Convex Polygon: Prove Cn-2 Ways

[dancergirlie]

Homework Statement

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

Homework Equations

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

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.

 

[tiny-tim]

Hi dancergirlie!

(try using the X² and X₂ tags just above the Reply box )

I don't think that formula is right …

For n = 4, there are only 2 solutions, but C_4-2 = C₂ = (1/2)⁴C₂ = 3.

 

[tiny-tim]

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

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.

 

[tiny-tim]

Catalan numbers

If I'm counting correctly (and of course I may not be ) …

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 ²ⁿC_n/(n+1), not ²ⁿC_n/2 as in the original question. ​

They're generated by C_n+1 = ∑_i=0ⁿ C_iC_n-i, which is fairly easy to prove for triangulations of a polygon.

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