people people sit around a round table. At the same moment everyone shakes hands with exactly one other person, and no two handshakes may cross over the table. Seats are numbered, so rotations of a pattern count as different.
Implement handshakes(people: int) -> int: the number of ways this can happen.
handshakes(4) # 2 (0-1, 2-3) or (0-3, 1-2); (0-2, 1-3) would cross
handshakes(6) # 5
handshakes(3) # 0 someone would be left out
With 0 people there is exactly 1 way (nobody does anything).
Constraints: 0 <= people <= 1000. Python ints don't overflow, so return the exact count. Plain recursion without memoisation is exponential and far too slow near 1000.
Show hint
person 0 shakes hands with some j; that handshake splits the others into the people strictly between them and the people on the other side, two independent smaller tables that can't reach each other, so ways(n) = sum over j of ways(j - 1) * ways(n - j - 1) (only odd j leave both sides even): the Catalan recurrence.