拼图:N人坐在圆桌上.没有穿过任何其他握手的握手方式

Question

我们有n个人坐在圆桌旁.任何人都可以与任何其他人握手.这些人可以通过多少方式进行握手,这样就不会有两次握手相互交叉.

我在技术访谈论坛中发现了这个难题,但没有答案.我能想到的一种方法是找到握手的所有排列,然后检查每个排列是否满足.

任何人都可以请求任何其他更有效的解决方案.

@edit:评论澄清:N会是均匀的.

Answer 1

我会尝试分而治之的解决方案.如果人1与人x握手,则将其余人分成两组,可以视为坐在两个圆桌旁.

Answer 2

作为Python函数(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

例:

>>> num_handshakes(8)
14

这基本上实现了@ Buhb的分而治之的方法.另一个解决方案,一旦我们知道答案与加泰罗尼亚语数字有关:

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

我会尝试分而治之的解决方案.如果人1与人x握手,则将其余人分成两组,可以视为坐在两个圆桌旁.

@Buhb是对的.那种复发关系是

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

或者在代码中

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

奇数个人不能握手,但f的前几个偶数值是1,2,5,14,42

搜索整数序列的百科全书,这看起来像着名的加泰罗尼亚数字http://oeis.org/A000108

这些序列真的是一样的,还是只是以相同的方式开始？他们是一样的.证实了我的数学书 - 我们的复发关系,定义了加泰罗尼亚数字的f代码https://en.wikipedia.org/wiki/Catalan_number#Properties