# 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 $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.

2. 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

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 $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!

4. 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 \\
Q_1 &=& 1 \\ Q_2 &=& 2 \\ Q_3 &=& 5 \\ Q_4 &=& 14 \\ Q_5 &=& 42
\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$