puzzle: N persons sitting on round table. No of ways of handshakes without crossing any other handshakes

Question

We have n persons sitting on a round table. Any person can do a handshake with any other person. In how many ways these n people can make handshakes so that no two handshakes crosses each other.

I found this puzzle in a technical interview forum, but no answer. One way i could think of was find all the permutations of handshakes and then check each permutation whether it satisfies or not.

Can anyone please sugget any other solution which is more efficient.

@edit: Clarification from comments: N would be even.

Answer 1

I would try a divide and conquer solution. if person 1 shakes hand with person x, it splits the rest of the people into two groups, that can be treated as sitting at two round tables.

Answer 2

The solution is quite easy given as a Python function (Python 3.3+):

@lru_cache(maxsize=None) # memoize
def num_handshakes(n):
    if n % 2 == 1: return 0
    elif n == 0: return 1
    res = 0
    for i in range(0, n, 2):
        res += num_handshakes(i) * num_handshakes(n-2-i)
    return res

Example:

>>> num_handshakes(8)
14

This basically implements @Buhb's divide-and-conquer approach. Another solution, once we know the answer is related to the Catalan numbers:

from math import factorial as fac
def catalan(n):
    return fac(2*n) // fac(n+1) // fac(n)

def num_handshakes(n):
    if n % 2 == 1: return 0
    return catalan(n//2)

Answer 3

I would try a divide and conquer solution. if person 1 shakes hand with person x, it splits the rest of the people into two groups, that can be treated as sitting at two round tables.

@Buhb is right. That recurrence relation is

f(n) = sum( f(i-2) + f(n-i) for i in range(2, n))

Or in code

def f(n):
    if n == 0:
        # zero people can handshake
        return 1

    if n == 1:
        # it takes two to tango
        return 0

    ways = 0

    # what if person 1 shakes with person i ?
    for i in range(2, n+1):
        # splits table into independent sets 2 .. i-1 and i+1 .. n
        ways += f(i-2) * f(n-i)

    return ways

An odd number of people can't handshake, but the first few even-placed values of f are 1, 2, 5, 14, 42

Searching the encyclopedia of integer sequences, this looks like famous Catalan numbers http://oeis.org/A000108

Are the sequences really the same, or do they just start similarly? They are the same. Corroborated my a maths book—our recurrence relation that defines f holds for the Catalan numbers too https://en.wikipedia.org/wiki/Catalan_number#Properties