[组合] 5对夫妻随机分组（两人一组）恰有一对夫妻同组

12673zf

很老的题目了，10个人5对夫妻，两个人一组，分成5组。如果限定一组里一男一女，那么恰有一对夫妻同组的分法是45，5×3×3，很容易。如果不限定一组必须有男有女，可以同性，那么恰有一对夫妻同组有多少分法呢？求解。

业余的业余

貌似是个 derangement 问题。

先确定同组的夫妻，有 $5$ 种可能。剩下的就等同于 4个人，4个帽子，每个人都拿到的不是自己的帽子的典型的derangement 问题了。

一下摘自维基

错排问题是组合数学中的问题之一。考虑一个有$\displaystyle n$个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 $n$个元素的错排数记为$D_{n}$。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。

最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。


目录
1        定義
2        历史
3        研究错排问题的方法
3.1        枚举法
3.2        递推数列法
4        多项式模拟
5        简化公式
6        参考资料
定義
記$D_{n}$為$\{1,2,\dots ,n\}$上沒有不動點的排列(即$\phi :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\},\phi (i)\neq i, \forall 1\leq i\leq n$)的個數，$D_{n}$的值如下：（由$n=1$起：）

$0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... $
不難發現，這個數列有一個規律，$D_{n}=nD_{n-1}+(-1)^{n}$

kuing

回复 2# 业余的业余

他现在问的是如果允许同性的情况如何，这时剩下的四对就不是错排了。

kuing

\(\require{cancel}\)不过，虽然不是错排，但仍然可以用推导错排的方法来解决，比如用容斥原理，类似于《撸题集》P.780 题目 5.6.20 那样。

只需解决：4 对夫妻分 4 组（每组 2 人，允许同性），没有一对夫妻同组的分法。

计算其反面：存在夫妻同组，类似于《撸题集》里那样，用集合 `A`, `B`, `C`, `D` 表示各对夫妻同组，然后由容斥原理
\[
\abs{A\cup B\cup C\cup D}=x_1-x_2+x_3-x_4,
\]其中
\begin{align*}
x_1&=\abs A+\abs B+\abs C+\abs D=\xcancel{4C_6^2C_4^2=360},\\
x_2&=\abs{A\cap B}+\abs{A\cap C}+\abs{A\cap D}+\abs{B\cap C}+\abs{B\cap D}+\abs{C\cap D}=\xcancel{6C_4^2=36},\\
x_3&=\abs{A\cap B\cap C}+\abs{A\cap B\cap D}+\abs{A\cap C\cap D}+\abs{B\cap C\cap D}=4,\\
x_4&=\abs{A\cap B\cap C\cap D}=1,
\end{align*}所以|A∪B∪C∪D|=327，因此没有一对夫妻同组的分法是 C_8^2C_6^2C_4^2-327=2193。

这样，原问题，即 5 对夫妻恰有 1 对同组的就是 5×2193=10965。

kuing

回复 4# kuing

搞错了，差点忘了，平均分组要除以组数的阶乘

正确的应该是
\begin{align*}
x_1&=\abs A+\abs B+\abs C+\abs D=4\cdot\frac{C_6^2C_4^2}{3!}=60,\\
x_2&=\abs{A\cap B}+\abs{A\cap C}+\abs{A\cap D}+\abs{B\cap C}+\abs{B\cap D}+\abs{C\cap D}=6\cdot\frac{C_4^2}{2!}=18,\\
x_3&=\abs{A\cap B\cap C}+\abs{A\cap B\cap D}+\abs{A\cap C\cap D}+\abs{B\cap C\cap D}=4,\\
x_4&=\abs{A\cap B\cap C\cap D}=1,
\end{align*}所以 $\abs{A\cup B\cup C\cup D}=45$，因此没有一对夫妻同组的分法是
\[\frac{C_8^2C_6^2C_4^2}{4!}-45=60,\]原问题的 5 对夫妻恰有 1 对同组的就是 `5\times60=300`。

这才比较符合直觉，不然刚才的数字实在太大了，所以就感觉不对劲……

kuing

今天状态实在太差了，刚才修正过程中依然计算错一个数字……

一般地：`n` 对夫妻分 `n` 组（每组 2 人，允许同性），没有一对夫妻同组的分法数为
\[\sum_{k=0}^n(-1)^kC_n^k\frac{(2n-2k)!}{2^{n-k}(n-k)!}.\]
或者进一步化简为
\[\sum_{k=0}^n(-1)^kC_n^k\cdot1\cdot3\cdot5\cdots(2n-2k-1).\]
让 `n` 取 1~10 上式的值为 `\{0, 2, 8, 60, 544, 6040, 79008, 1190672, 20314880, 387099936\}`，可以列一列 3 对的时候是不是 8 种分法，这个要是再错，我就不玩了

业余的业余

回复 3# kuing

看走眼了