British Mathematical Olympiad - December 2001 - Round 1 - Question 4

Number the people around the table $1,\ldots,12$.

As an example, the number of ways that persons $1,\ldots,12$ can engage in handshakes with no arms crossing given that person $1$ is shaking hands with person $6$ is the number of ways that persons $2,\ldots,5$ can handshake with no arms crossing multiplied by the number of ways that persons $7,\ldots,12$ can handshake with no arms crossing. This thought process generalised yields the following recurrence relation, letting $C_n$ be the number of ways that $n$ pairs can handshake, we have \begin{equation} C_{n+1} = \sum_{i=0}^n C_{i}C_{n-i}, \end{equation} where $C_0 = 1$. This is the recurrence relation of the Catalan numbers and has a well known closed form $C_n = \frac{1}{n+1} {{2n}\choose{n}}$ which can be derived by using its generating function. Thus for us $C_6 = 132$.

Let $S_{2n}$ = ways for for 2n people to shake n pairs, without crossing.

Example, for 4 people ABCD, we have 2 ways: (AB,CD),(AD,BC)

$S_2 = 1$
$S_4 = 2S_2 = 2$
$S_6 = 2S_4 + S_2 S_2 = 4+1 = 5$
$S_8 = 2S_6 + 2S_2 S_4 = 10 + 4 = 14$
$S_{10} = 2S_8 + 2S_2 S_6 + S_4 S_4= 28+10+4 = 42$
$S_{12} = 2S_{10} + 2S_2 S_8 + 2S_4 S_6= 84+28+20 = 132$