Handshakes without crossing
Ten people sit around a round table. They split into five pairs, and each pair shakes hands across the table, so that no two pairs of arms cross.
How many such arrangements are there?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Look at person 1. Whom can they shake hands with, if nobody's arms may cross theirs?
Person 1's handshake splits the table into two groups, each of which must pair up on its own.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Fix person 1. Their handshake cuts the table into two sides, and no handshake may cross it, so each side must pair up within itself, in a smaller copy of the same problem. That gives a recursion: the Catalan numbers.
Step 1: the recursion. Let be the number of arrangements for people, with . If person 1 shakes hands with someone leaving people on one side and on the other (each side must have an even number of people), then
Step 2: compute.
So there are 42 arrangements. In closed form, , and .