1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Triangulation proof

  1. Oct 4, 2009 #1
    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

    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. jcsd
  3. Oct 8, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi dancergirlie! :smile:

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

    I don't think that formula is right …

    For n = 4, there are only 2 solutions, but C4-2 = C2 = (1/2)4C2 = 3. :confused:
  4. Oct 9, 2009 #3


    User Avatar
    Science Advisor
    Homework Helper

    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 :redface:), I don't see how 13 can come out of a "choose" function.
  5. Oct 9, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    Catalan numbers

    oops … I did miss one :blushing: … 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. :rolleyes:

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

    (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 :redface:)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook