来自人教群昨晚的错排问题的变式(已解决)

kuing

爱好者-三千(5379*****) 22:50:57
ABCDEFG 7個人 把各自的名片放入7個箱子裏面  一共有7張名片  混亂順序後  ABCD 4個人出來在這7個箱子裏面每個人選一張出來  求ABCD 4人都沒抽到自己的名片的方法數？
爱好者-三千(5379*****) 22:51:02
有个学生问的
不会挖。。。

爱好者-三千(5379*****) 23:23:22
答案465

昨晚在人教群看到的这个，似乎比原先的错排问题要难，不会做，先转上来。

Tesla35

看见组合和概率就烦

kuing

回复 2# Tesla35

kuing

好像还是可以类似地用容斥原理……

kuing

果然！

先计算反面，即 ABCD 至少一个人抽到自己的名片的方法数。

为方便表达，就以集合 $A$ 表示 A 抽到自己的名片，其余同理，由容斥原理，有
\[\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,\\
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},\\
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},\\
x_4&=\abs{A\cap B\cap C\cap D},
\end{align*}
由对称性知每个 $x_k$ 里每项的值都相同，所以可以化简为
\begin{align*}
x_1&=C_4^1\abs A,\\
x_2&=C_4^2\abs{A\cap B},\\
x_3&=C_4^3\abs{A\cap B\cap C},\\
x_4&=C_4^4\abs{A\cap B\cap C\cap D},
\end{align*}
$\abs A$ 表示 A 抽到自己的名片的方法总数，所以只要 A 拿好自己的名片，其他三个随便排列即可，即 $\abs A=A_6^3$；
$\abs{A\cap B}$ 表示 AB 都抽到自己的名片的方法总数，所以只要 AB 都拿好自己的名片，其他两个随便排列即可，即 $\abs{A\cap B}=A_5^2$；
如此类推，所以
\begin{align*}
x_1&=C_4^1A_6^3=480,\\
x_2&=C_4^2A_5^2=120,\\
x_3&=C_4^3A_4^1=16,\\
x_4&=C_4^4=1,
\end{align*}
代入即可计算出
\[\abs{A\cup B\cup C\cup D}=375,\]
而基本事情总数为 $A_7^4=840$，所以 ABCD 都抽不到自己名片的方法数为
\[840-375=465.\]

kuing

楼上的这个方法显然具有一般性，具体地可以归纳出如下公式：

$n$ 个人将各自的名片放入 $n$ 个箱子里，混乱顺序后，其中 $m$ 个人出来在这 $n$ 个箱子里每人抽出一张，则这 $m$ 个人都没抽到自己的名片的方法数为
\[
A_n^m-\sum_{k=1}^m(-1)^{k-1}C_m^kA_{n-k}^{m-k},
\]
这里规定 $A_n^0=1$（不知课本里有没有规定过这个，不管了，反正这里定这里用）。
公式还可以化简一下，由于 $A_n^m$ 可以写成 $(-1)^0C_m^0A_{n-0}^{m-0}$，而和式前面的负号写进去后 $(-1)^{k-1}$ 变成 $(-1)^k$，所以上式可以化简写成
\[\boxed{\displaystyle\sum_{k=0}^m(-1)^kC_m^kA_{n-k}^{m-k}.}\]

而熟知的完全错排问题即是当 $m=n$ 时的情形，此时上式就变成完全错排公式，可见上式是更一般的错排公式。

kuing

用软件来验证一下上述公式是否也能得出1楼题目的结果：
输入：
f[n_, m_] := Sum[(-1)^k*m!/(k!*(m - k)!)*(n - k)!/(n - m)!, {k, 0, m}]
f[7, 4]
输出：
465

kuing

修改了一下标题，已解决

睡神

K神可以写成篇论文了，部分错排好像比较少见…额…很有可能是我孤陋寡闻…

爪机专用

回复 9# 睡神

我也觉得很可能是旧东西，排列组合我玩得少不知道而已，所以就这样好了，写文章就不必了。

睡神

回复 10# 爪机专用
好像没怎么见过部分错排的，全错排就不少…