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

Answer 4

What a bout backtracking?

1. Start withe one handshake and search for still possible handshakes. if no more non crossing handshakes are possible, backtrack. Continue until no more branches of your search-tree can be extended by a non crossing handshake.
2. All vertices of the resulting search-tree are non crossing handshakes.

Because your table is round (symmetry), you can optimize the problem by assuming that person 0 is always part of the top most handshake.

Answer 5

I think this may be a solution for even n=2m.

Number the people around the circle from 1 to 2m.

In round j, 1≤j≤m, person j shakes hands with person j+1, and all other handshakes are "parallel" to this (so, j−1 with j+2, j−2 with j+3, and so on - throughout, the labels are interpreted modulo n, as necessary). At the end of these m rounds, everyone has shaken hands with everyone an odd number of people away.

In round m+j, 1≤j≤m, j shakes with j+2 and all other handshakes are parallel (so j−1 with j+3, j−2 with j+4, etc.). This handles all the pairs an even number of people apart. So the total is 2m rounds.

As noted in the problem statement, 2m−1 rounds is impossible, so 2m is the answer.

The odd case is even easier. In round j, person j sits out while j−1 greets j+1, j−2 greets j+2, etc., again using n rounds.

Answer 6

Here Result follow the Catalan number Series. here is My code in c++

#include <bits/stdc++.h>
using namespace std;
long c[17] ;
void sieve(){
    c[0] = 1;
    c[1] = 1;
    for(int i =2;i<=15;i++){
        for(int j =0;j<i;j++){
            c[i] += c[j]*c[i-j-1];
        }
    }
}

int main(void){
    sieve();
    int t;
    scanf("%d",&t);
    while(t--){
        int n ;
        scanf("%d",&n);
        if(n%2!=0){
            cout<<"0"<<endl;
        }
        else{
            n = n>>1;
            cout<<c[n]<<endl;
        }
    }

    return 0;
}

Answer 7

people can make handshakes with (n-1)+(n-2)+.....+1 ways It's for linear

n ways for round table

Answer 8

Since there are n people and 2 people would handshake at a time, and also if lets say A handshakes with B and B handshakes with A we cannot count it twice ie. AB and BA both cannot be counted which ultimately means that arrangement is not there ie. Permutations are not the case but Combination is...

So, applying combination formula it becomes : nC2 => (n*(n-1))/2 after solving.

So we can straight away apply this formula to the problem to get the answer.