algorithm - 谜题:N个人坐在圆 table 上。没有交叉任何其他握手的握手方式

Question

我们有n个人坐在一张圆 table 上。任何人都可以与任何其他人握手。这 n 个人有多少种握手方式可以使两次握手不会交叉。

我在一个技术面试论坛上发现了这个谜题，但没有答案。我能想到的一种方法是找到握手的所有排列，然后检查每个排列是否满足。

任何人都可以建议任何其他更有效的解决方案。

@edit:来自评论的澄清:N 应该是偶数。

Answer 1

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