2
$\begingroup$

Problem 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)

The solution given in the book A Mathematical Olympiad Primer by Geoff Smith makes use of the Catalan Sequence. However, I don't see the linkage between the Catalan Sequence and the question. Does anyone know how they are linked?

$\endgroup$
1
$\begingroup$

Say $n$ pairs of people are seated around the table, and call the solution $u_n$ so you want $u_6$. Start by choosing whom person 1 shakes with; you'll need an even number of people either side of the shake, so the other person is $2k$ positions along clockwise, $0\le k\le n-1$. Thus $u_n=\sum_k u_k u_{n-1-k}$, the same recursion relation as in the Catalan sequence. Now you just need to check $u_0=u_1=1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.