Results 1 to 4 of 4

Math Help - Write a recurrence relation

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    28

    Post Write a recurrence relation

    There are 2n points marked on a circle. We want to divide them into pairs and connect the points in each pair by a segment (chord) such that these segments do not intersect.

    Let Q_{n} be the number of ways to do this.
    Write a recurrence relation for Q_{n}.

    I worked Q_{n} out up to n=5:
    Q_{0} = 0
    Q_{1} = 1
    Q_{2} = 2
    Q_{3} = 5
    Q_{4} = 14
    Q_{5} = 42

    I had worked Q_{n} out to be 2Q_{n-1} + 2Q_{n-2} but this failed when I worked out n=5.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    This induces the Catalan number, the answer is \frac{1}{n+1}\left(\begin{array}{cc}2n\\n\end{arra  y}\right)
    see
    Catalan number - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    For the recurrence relation, you may choose the point numbered 1.
    1 must be connected with some point. you may assume it is 2k(why?). Thus the 2n points are divided into two parts, one is 1,2,...2k, the another is 2n,2n-1,...2k+1. For any x in the first part,y in the second part, x,y cannot be connected since 1,2k is connected. So in this situation, there will be C_{k}C_{n-k} answers. So C_{n}=C_{1}C_{n-1}+C_{2}C_{n-2}+...+C_{n-1}C_{1}
    Of course, if you want to deduce the previous formula from this recurrence relation, it is extremely tough. You may challenge it!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,689
    Thanks
    617
    Hello, DaRush19!

    There are 2n points marked on a circle.
    We want to divide them into pairs and connect the points in each pair
    by a segment (chord) such that these segments do not intersect.

    Let Q_{n} be the number of ways to do this.
    Write a recurrence relation for Q_{n}.

    I worked out Q_{n} up to n=5\!:

    . . \begin{array}{ccc}Q_0 &=& 0 \\ <br />
Q_1 &=& 1 \\ Q_2 &=& 2 \\ Q_3 &=& 5 \\ Q_4 &=& 14 \\ Q_5 &=& 42 <br />
\end{array}
    I've verified your values up to n = 4.
    . . Is it possible that: Q_5 \,=\,41 ?

    If so, the recurrence seems to be: . Q_n \;=\;3Q_{n-1} - 1

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 3rd 2011, 07:21 AM
  2. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 16th 2010, 01:56 AM
  3. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 19th 2009, 03:57 AM
  4. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 8th 2008, 09:47 AM
  5. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 2nd 2007, 11:14 PM

Search Tags


/mathhelpforum @mathhelpforum