免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

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

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

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

昨晚在人教群看到的这个,似乎比原先的错排问题要难,不会做,先转上来。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
$\href{https://kuingggg.github.io/}{\text{About Me}}$

看见组合和概率就烦

TOP

回复 2# Tesla35
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

好像还是可以类似地用容斥原理……
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

果然!

先计算反面,即 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.\]
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

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

$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$ 时的情形,此时上式就变成完全错排公式,可见上式是更一般的错排公式。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

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

TOP

修改了一下标题,已解决
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

K神可以写成篇论文了,部分错排好像比较少见…额…很有可能是我孤陋寡闻…
睡自己的觉,让别人说去!!!

TOP

回复 9# 睡神

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

TOP

回复 10# 爪机专用
好像没怎么见过部分错排的,全错排就不少…
睡自己的觉,让别人说去!!!

TOP

返回列表 回复 发帖