算法-安排n对夫妇围圆桌就坐的方法数，使得就坐时男女相间并且没有丈夫和妻子相邻

Question

求安排n对夫妇围圆桌就坐的方法数量，使得就坐时男女相间并且没有丈夫和妻子相邻。

假设有3对夫妻：aA bB cC
那么只有一种可能
aC bA cB
因为a后面不能是B也不能是A，就只能是C
那么剩下BA供bc选项，b只能选A
剩下就是cB
例如如图所示

Answer 1

先让N个丈夫坐下，然后将N个妻子往后挪一下然后依次插进去应该就满足条件了吧

如果将循环的位置视为一种，即所有人坐好，然后依次往下挪则视为同一种情况的话
即1234和2341视为一种
总共的方法为(n-1)!*(n-2)!

反之如果座位循环挪动视为不同的方法时总共方法为：
(n-1)!(n-2)!2n

具体说明如下：
首先对N个丈夫排序，如果不算循环的话有(n-1)!个方法
然后将N个妻子插进去，对于第一个妻子有N-2个选择
然后选择一个丈夫两边没有别人妻子的人的妻子，该妻子会有N-2个选择
如此循环直到找不到这样的妻子，然后找丈夫边上只有一个别人妻子的人的妻子，该妻子的选择也是递减下去的。
然后再如此循环，然后就剩下丈夫边上都坐满了的，选择也是递减的，然后就差不多固定了
所以总的就是(n-1)!*(n-2)!

Answer 2

这是组合数学中Manage问题，运用广义容斥原理来做。

Answer 3

好，这个问题够淫荡，我喜欢

Answer 4

同意2n(n-1)!(n-2)!, 我的思路是这样的：男女拍成两队，夫妻双方相对而站，从两队中取出任意一人的可能是2n种，假如第一次取出为男，那么第二次取出女子可能数目是(n-1),然后再从男队中取出的可能数目为(n-2),(-2的意思是去掉第1次取出的男和与第二次取出女相对的男)，同理再次从女队中取出是也是(n-2)种，以此类推，可以找到规律，并得解。

Answer 5

先让N个丈夫连续坐下，然后妻子找到丈夫的位置与代替丈夫，丈夫的新位置是已经坐下的人数加一

可以这么想，

1、对于第一个男人，供他选择的舞伴有9个（因为不能则其配偶），选择其中之一，并将该女人的配偶作为第二个进行选择的男人；
2、对于第二个男人，供他选择的舞伴有9个（因为他的配偶已被第一个男人选走，他可以在剩下的9个女人中任意选取），选择其中之一，并将该女人的配偶作为第三个进行选择的男人；
3、对于第三个男人，供他选择的舞伴有8个（因为他的配偶已被第二个男人选走，而且第一个男人也选走了一个，所以可以在剩下的8个女人中任意选取），选择其中之一，并将该女人的配偶作为第四个进行选择的男人；
4、对于第四个男人，供他选择的舞伴有7个（因为他的配偶已被第三个男人选走，而且最前两个男人选走了两个，所以可以在剩下的7个女人中任意选取），选择其中之一，并将该女人的配偶作为第五个进行选择的男人；
5、依次类推。。。
对于第九个男人，供他选择的舞伴有2个，选择其中之一，并将该女人的配偶作为第十个进行选择的男人；
6、对于第十个男人，只有一个选择了
那么可以得到10对夫妻跳舞的组合有9×9×8×7×...×2×1种选择；
7、通过简单归纳，可以得到对于100对夫妻跳舞的组合方式有
99×99×98×97×...×2×1；
8、对于N对夫妻跳舞的组合方式有
(N-1)(N-1)(N-2)(N-3)...2*1=(N-1)(N-1)!

Answer 6

N对夫妻跳舞问题

给你一个传送门，原理一样一样的