Fall 2016, problem 22

First some notation:

• Identify the points with the numbers $0$, $1$, ... $2n -1$ in counterclockwise order starting at some arbitrarily chosen point $0$.
• Call a partition of the $2n$ points into disjoint couples a coupling.
• Define $N_n$ as the number possible couplings of $2n$ points
• Define $R_n$ as the number of couplings of $2n$ points , where the chords don't intersect in the sense of the problem statement. Also define $R_0 := 1$.
• $P_n := \frac{R_n}{N_n}$ is the probability we are looking for.

The denominator of the probability:

The number of ways to pick $n$ couples from $2n$ points without repetition, counting order is: $$\binom{2n}{2} \binom{2n - 2}{2} \binom{2n-4}{2} \times.... \times \binom{2}{2} = \frac{(2n)!}{2^n}$$ In counting this way we count every coupling exactly $n!$ times. Therefore: $$N_n = \frac{(2n)!}{2^n n!}$$

The numerator of the probability

Determining $R_n$ requires more effort. First note, that the point 0 can only be connected to a point $p \in {1, 3, 5, .., 2n -1}$, for otherwise there would be an odd number of points on either side of the chord $\overline{0p}$, so at least one chord would connect the two sides, thereby intersecting $\overline{0p}$.

If we assume for the moment, that $0$ is connected to a fixed point $2 k -1$, where $1 \leq k \leq n$, we can only couple the points on either side of $\overline{0(2k-1)}$ among themselves, otherwise an intersection would ensue. The numer of ways, to do this is $R_{\frac{2k - 2}{2}} R_{\frac{2n - 2 - (2k - 2)}{2}} = R_{k - 1} R_{n - 1 - (k -1)}$. To calculate $R_n$ we need to sum over the ways to choose $k$:

$$R_n = \sum_{k = 1}^{n} R_{k - 1} R_{n - 1 - (k -1)} = \sum_{k = 0}^{n-1} R_{k} R_{(n - 1) - k} \quad (Eq.1)$$

Solving the recursion:

All that remains is to solve the recursive equation $(Eq.1)$ with the initial condition $R_0 = 1$. We use the method of generating functions. Define the power series $$f(x) := \sum_{j = 0}^{\infty} R_j x^j$$ We assume that $f$ has a nonzero convergence radius, which will be justified a posteriori. The Cauchy product formula gives:

$$f(x)^2 = \sum_{m = 0}^{\infty} \left ( \sum_{k = 0}^{m} R_k R_{m - k} \right ) x^m$$

On the other hand:

$$ \frac{f(x) - 1}{x} = \sum_{m = 0}^\infty R_{m + 1} x^m$$

So one glance at $(Eq. 1)$ tells us that:

$$x f(x)^2 - f(x) + 1 = 0 \implies f(x) = \frac{1}{2 x} (1 \pm \sqrt{1 - 4 x}) \quad (Eq.2)$$.

We use the Taylor series: $$\sqrt{1 - x} = \sum_{m = 0}^\infty \frac{(2m)!}{(1 - 2m) (m!)^2 4^m} x^m$$

At this point we know, that we are indeed operating with a convergent power series. In (Eq.2) we must choose the minus sign, to get a power series for $f$, which has no negative powers of $x$:

$$f(x) = \sum_{m=0}^\infty \frac{1}{2} \frac{(2m + 2)!}{(2m + 1) ((m+1)!)^2} x^m $$

We see now, that

$$R_n = \frac{1}{2} \frac{(2n + 2)!}{(2n + 1) ((n+1)!)^2} $$

And putting it all together, we have at last:

$$P_n = \frac{1}{2} \frac{(2n + 2)!}{(2n + 1) ((n+1)!)^2} \frac{2^n n!}{(2n)!} = \frac{2^n}{(n+1)!}$$