# Thread: Write a recurrence relation

1. ## 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 $\displaystyle Q_{n}$ be the number of ways to do this.
Write a recurrence relation for $\displaystyle Q_{n}$.

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

I had worked $\displaystyle Q_{n}$ out to be $\displaystyle 2Q_{n-1} + 2Q_{n-2}$ but this failed when I worked out n=5.

2. This induces the Catalan number, the answer is $\displaystyle \frac{1}{n+1}\left(\begin{array}{cc}2n\\n\end{arra y}\right)$
see
Catalan number - Wikipedia, the free encyclopedia

3. 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 $\displaystyle C_{k}C_{n-k}$ answers. So $\displaystyle 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!

4. Hello, DaRush19!

There are $\displaystyle 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 $\displaystyle Q_{n}$ be the number of ways to do this.
Write a recurrence relation for $\displaystyle Q_{n}$.

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

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

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