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

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# 爪机专用
好像没怎么见过部分错排的，全错排就不少…

lemondian

kuing 发表于 2013-9-24 01:26
楼上的这个方法显然具有一般性，具体地可以归纳出如下公式：

$n$ 个人将各自的名片放入 $n$ 个箱子里，混 ...

我在看到一个这样的：
探究n个不同元素中有确定的m个元素不在指定的对应m个位置上.
【解析】首先,定义 f(n,m)(n≥m)表示n个不同元素中有确定的m个元素不在指定的对应 m 个位置上的排法总数。易知f(n,1)是指n个不同元素中有某个元素不在指定的某个位置上,即可先安排这个元素在另外n-1个位置中的某一个,再将其余n-1个元素全排列,故f(n,1)=(n-1)·(n-1)!, 得f(1,1)=0.
猜想 f(n,m)=f(n,m-1)-f(n-1,m-1).
证明 先设n个元素$a_1,a_2,…,a_n$中有m-1个元素$a_1,a_2,…,a_{m-1}$不在指定的对应m-1个位置, 则对于第m个元素$a_m$,可分为两类:一类是元素$a_m$在第m个位置,则前$n-1$个不同元素中有确定的 m-1个元素不在指定的对应m-1个位置上,其排法总数为$f(n-1,m-1)$;另一类是元素$a_m$也不在第m个位置,则n个不同元素中有确定的m个元素不在指定的对应m个位置上,其排法总数为$f(n,m)$,故由分类加法原理得$f(n, m-1)=f(n-1, m-1)+f(n, m)$,
即 $f(n, m)=f(n, m-1)-f(n-1, m-1)$.
最后还得到这个：
\[
f(n, m)=\sum_{r=0}^{m-1}(-1)^r C_{m-1}^r f(n-r, 1)
\]
我试了一下，好象不对呀，与你的对不上，哪的地方有问题呢？

kuing

lemondian 发表于 2025-4-5 21:32
我在看到一个这样的：

似乎他这个的定义与我上面的不是一回事。

你看他写到 f(n,1)=(n-1)(n-1)!，为什么要乘以其余元素的全排列？这显然就不是 1# 题目的意思。

lemondian

kuing 发表于 2013-9-24 01:26
楼上的这个方法显然具有一般性，具体地可以归纳出如下公式：

$n$ 个人将各自的名片放入 $n$ 个箱子里，混 ...

这个结论有没有严格的证明呀？比如数学归纳法什么的

kuing

lemondian 发表于 2025-4-6 09:22
这个结论有没有严格的证明呀？比如数学归纳法什么的

如果 5# 的过程你看得懂，那你应该明白一般化是完全一样的道理。
非要写过程，无非将 5# 的过程以 99% 相似度再重复一遍，所以没必要再写。

abababa

这是不是那个伯努力装错信封问题？编号为$1,\cdots,n$的$n$封信，装入编号为$1,\cdots,n$的$n$个信封，若每封信和信封的编号都不同，问有多少种装法。

每封信都要被装入一个信封，每个信封都要装入一封信，即在一个装法中，信与信封构成双射。

设集合$S$表示$n$封信随意装入$n$个信封的所有装法，集合$A_i$表示第$i$封信恰好装入第$i$个信封的所有装法，于是全部装错的装法为
\begin{align*}
\abs{\bigcap_{i=1}^{n}A_i^c}
&=\abs{S}-\sum_{i=1}^{n}\abs{A_i}+\sum_{i<j}\abs{A_i \cap A_j}-\cdots+(-1)^n\abs{\bigcap_{i=1}^{n}A_i}\\
&=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\cdots+(-1)^n\binom{n}{n}(n-n)!\\
&=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right)\\
&=n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}
\end{align*}

kuing

abababa 发表于 2025-4-6 15:34
这是不是那个伯努力装错信封问题？编号为$1,\cdots,n$的$n$封信，装入编号为$1,\cdots,n$的$n$个信封，若每 ...

认真审题……这题信封小于信

lemondian

kuing 发表于 2025-4-6 13:52
如果 5# 的过程你看得懂，那你应该明白一般化是完全一样的道理。
非要写过程，无非将 5# 的过程以 99% 相 ...

@kuing:
我得到这个问题的递推公式：

$f(n,m)=(n-1)f(n-1,m-1)+(m-1)f(n-2,m-2)$.

那么，如何由递推公式，得到你的公式呢？