Dtyjlui

I have just come across this problem:

Given $2n$ points on a circle. Alex wants to join the points by $n$ segments so that each segment joins two points and there are no two segments intersect with each other. How many ways are there for Alex to do so?

I am preparing for an exam but I have no idea of how to solve this problem. Can you help me?

Any help is much appreciated!

Let $A_n$ be this number. Observe that for a given $n$, and for a given fixed given point, the only points to which you can join are at even distance of this point, otherwise the amount of point in between is not even and there is a point you cannot link. Linking these two points cuts the circle in two sub part with even number of points that needs to be linked with no intersection. Hence you get that
begin{align*}
A_n = sum_{k=0}^{n-1} A_k A_{n-1-k}
end{align*}

Now to solve this recursion you can use the generating function of $A_n$ :
begin{align*}
S(x)&=sum_{n=0}^{infty} A_n x^n\
&=1+sum_{n=1}^{infty} sum_{k=0}^{n-1} A_k A_{n-1-k} x^n\
&=1+xsum_{k=0}^infty A_k x^ksum_{n=k+1}^infty A_{n-1-k} x^{n-k-1}\
&=1+x S^2(x)
end{align*}

This is the generating function of the Catalan number and hence $A_n={2nchoose n}-{2nchoose n+1}$

Here are two approaches. No doubt there are many others.

1. Work out the answer by hand for the first few values of $n$, then look for the sequence at oeis.org.




2. Find a nice recurrence, using the fact that joining two points divides the problem neatly into two subproblems. I'm not sure I did it right but I get
   $$a_{n+1}=sum_{k=0}^na_ka_{n-k}$$
   or something like that. Now it looks like a straightforward exercise to find a closed formula for the ordinary generating function
   $$y=sum_{n=0}^infty a_nx^n$$
   and then work out the coefficients.

P.S. Yeah, that seems to work. From the recurrence, we get
$$frac{y-1}x=y^2$$
or
$$xy^2-y+1=0.$$
By the quadratic formula,
$$y=frac{1-(1-4x)^{frac12}}{2x}.$$
By the binomial theorem,
$$(1-4x)^{frac12}=sum_{n=0}^inftybinom{frac12}n(-4x)^n=1+sum_{n=1}^infty(-1)^nbinom{frac12}n2^{2n}x^n$$
so
$$y=sum_{n=1}^infty(-1)^{n-1}binom{frac12}n2^{2n-1}x^{n-1}=sum_{n=0}^infty(-1)^nbinom{frac12}{n+1}2^{2n+1}x^n,$$
so
$$a_n=(-1)^nbinom{frac12}{n+1}2^{2n+1}$$
which simplifies to
$$a_n=frac{(2n)!}{n!(n+1)!}=frac{binom{2n}n}{n+1}.$$
That looks familiar. It's a Catalan number, isn't it?