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

Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once.)

I don't even understand what this question is asking. My best guess is that people can shake hands over the table (i.e. with someone on the opposite to them on the table) but that seems like something they'd mention in the brackets at the end.

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$