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函数或超几何函数的表达式.