n对夫妻站一排,丈夫和妻子不相邻的排法有多少?

n对夫妻站一排,丈夫和妻子不相邻的排法有多少?
n对夫妻站一排,丈夫和妻子不相邻的排法有多少?

n对夫妻站一排,丈夫和妻子不相邻的排法有多少?
给两种解法.
1. 用容斥原理.
以A[i]表示第i对夫妻相邻的排法集合, A[i,j]表示第i和j对夫妻都相邻的排法集合, A[i,j,k]等依此类推.
由容斥原理, 每对夫妻都不相邻的排法总数为:
(2n)!-∑{1 ≤ i ≤ n} |A[i]|+∑{1 ≤ i < j ≤ n} |A[i,j]|-∑{1 ≤ i < j < k ≤ n} |A[i,j,k]|+...
易得|A[i]| = (2n-1)!·2, 原因是第i对夫妻排在一起, 可作为整体与另外2n-2个人一起进行排列.
此外夫妻还有2种排列方式.
而i的选取共有C(n,1)种, 因此第一个和式为C(n,1)·(2n-1)!·2.
类似的|A[i,j]| = (2n-2)!·2^2, 这次是两对夫妻作为整体与另外2n-4个人一起进行排列.
此外每对夫妻还有2种排列方式.
i,j的选取共有C(n,2)种, 因此第二个和式为C(n,2)·(2n-2)!·2^2.
依此类推, 排法总数为:
(2n)!-C(n,1)·(2n-1)!·2+C(n,2)·(2n-2)!·2^2-... = ∑{0 ≤ k ≤ n} C(n,k)·(-2)^k·(2n-k)!.
2. 用递推.
设n对夫妻的不相邻排法总数为a[n].
易得a[1] = 0, a[2] = 4·2 = 8.
对于n > 2. 排列情况可分为三类.
第一类: 当去掉排在第一的人与其配偶, 剩下的n-1对仍不相邻.
被去掉的夫妻可以是任意一对, 有n种可能, 排在第一的可能是双方之一, 有两种可能.
剩下的一方有2n-2个可选的空挡, 因此这种情况的总数为a[n-1]·n·2·(2n-2).
第二类: 当去掉排在第一的人与其配偶(设为第x对), 会出现一对相邻夫妻(设为第y对).
且再去掉这对后, 剩下的n-2对夫妻不相邻.
被去掉的第x对夫妻有n种可能, 第y对夫妻有n-1种可能.
第y对夫妻可作为整体排在2n-3个空档之一, 二者的顺序有2种.
第x对夫妻则分别排在第一位以及第y对夫妻之间, 有2种可能.
因此这种情况的总数为a[n-2]·n·(n-1)·(2n-3)·2·2.
第三类: 当去掉排在第一的人与其配偶(设为第x对), 会出现一对相邻夫妻(设为第y对).
但再去掉这对后, 又会出现一对相邻夫妻(设为第z对), 位置关系可示意为x,...,z,y,x,y,z,...
我们去掉第x对夫妻, 并将剩下的人变为y,...,z,y,z,..., 易见这样剩下的n-1对夫妻不相邻.
不过并非所有的n-1对不相邻的情况都形如y,...,z,y,z,..., 要排除n-1对夫妻中的"第一类情况".
即y,...,z,y,z,...的情况数为a[n-1]-a[n-2]·(n-1)·2·(2n-4).
而被去掉的第x对夫妻有n种可能及2种顺序.
因此这种情况的总数为(a[n-1]-a[n-2]·(n-1)·2·(2n-4))·n·2.
a[n] = a[n-1]·n·2·(2n-2)+a[n-2]·n·(n-1)·(2n-3)·2·2+(a[n-1]-a[n-2]·(n-1)·2·(2n-4))·n·2
= 2n((2n-1)a[n-1]+(2n-2)a[n-2]).
即有递推公式a[n] = 2n((2n-1)a[n-1]+(2n-2)a[n-2]).
由a[1] = 0, a[2] = 8可求得任意项.
简单形式的通项公式恐怕不会有.
实际上可将通项写为a[n] = ∫{0,+∞} (x²-2x)^n·e^(-x) dx.
这也算是个通项公式, 只是不初等.
此外还有用Bessel函数或超几何函数的表达式.

(2n)!-2×n!
2n个人的全排列，减去一对夫妻看作一人的全排列，又有左右之分，所以应减去2×n!

先将丈夫排列，n!种。
有n+1空档(包括两头)，任选1个妻子，只有n-1个空档可插(本人丈夫两边空档不可插)；插入后
有了n+2空档，第2位妻子，有n个空档可插；插入后
有了n+3空档，第3位妻子，有n+1个空档可插；插入后
有了n+4空档，第4位妻子，有n+2个空档可插；插入后
…………
当第n-1位妻子插入后，有2n个空档，

全部展开

先将丈夫排列，n!种。
有n+1空档(包括两头)，任选1个妻子，只有n-1个空档可插(本人丈夫两边空档不可插)；插入后
有了n+2空档，第2位妻子，有n个空档可插；插入后
有了n+3空档，第3位妻子，有n+1个空档可插；插入后
有了n+4空档，第4位妻子，有n+2个空档可插；插入后
…………
当第n-1位妻子插入后，有2n个空档，
最后一位妻子只有2n-2个空档可插，
于是，妻子插入的方法有
(2n-2)(2n-3)……(n-1)=(2n-2)!/(n-2)!
丈夫和妻子排列，满足要求的不同排法有
n!(2n-2)!/(n-2)!=n(n-1)*(2n-2)!

收起