错排问题

· · 个人记录

错排问题是多种排列组合问题中的一种。属于组合。（所以说会在初赛中出现）

我们先看一下 2021 SCP（洛谷）的模拟试题好了：

有 5 个从 1 到 5 标号的小球和 5 个同样标号的盒子，
现将小球随机放入盒子，每个盒子仅放 1 个小球，
问每个盒子中的小球都与盒子标号不同的概率是 （ ）。

选项就不放了，反正算出来都一样的就是因为懒好吧

这就是错排问题了。错排问题就是考虑有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。

我们一般把错排问题记成D。

好的，那么先来分析一下这个问题。假设编号1-5的小球都在各自的盒子里，我们定义m为小球总数，也就是5。

你拿起了随机一个小球。这个小球的编号是n，可是根据题意，你不能把它放进编号为n 的盒子里了。（也就是说你重新又把它放回去干嘛？）不过，n这个盒子不能放，不就代表着你可以随便放到另外n-1个盒子里的任意一个嘛！于是你找了一个编号为k的盒子，把小球放了进去。

等等！那原来在盒子k里的球不就被挤出来了？啊，不过这也没有关系的。现在你手里拿的是球k。你要将它放到新的一个盒子里。

但这时候你犯难了。是将球k放到哪个位置好啊？是原来的n呢？还是新的一个盒子里？

那不就分了两种情况咯，分类讨论就好了：

放到原来的n。那盒子和球的状态就变成了k球在n盒子中，n球在k盒子中。嗯，这样就是处于大家都和平相处（）的情况了。n号球和k号球不在自己原来的位子上，那么这俩盒子和球就满足错排条件，可以踢出去了。剩下的m-2个球和盒子可以看作回到了问题的起点。结合上一个步骤（即拿起随机一个小球放到随机一个位置），这一种情况共有(m-1)\times D(m-2)种方法（m-1是你拿起的一个球）。

你就是不选这个空着的盒子n，就是喜欢来点不一样的。那这样的话……你既不能放到n，也不能放到k，这是不是就相当于把手里这个球加上剩下的m-2个球，也就是m-1个球进行错排呢？所以，现在就变成了求m-1个球的错排操作数！结合上一步，也可以很容易求得公式 (m-1) \times D(m-1)！

综上所述，把两种情况相加，得出来的错排公式就为

D(m) = (m-1) \times D(m-2)+(m-1) \times D(m-1) = D((m-1) \times (D(m-1)+D(m-2))

最后我们来考虑考虑初值的问题。若是只有一个小球和一个盒子，不管怎么放，永远都不可能达到错排的效果。所以 D(1)=0.

而有两个小球和两个盒子的话，只可能有一种错排的情况，即两个球互换盒子。所以 D(2)=1。

你学废了吗？

学不废没关系，众所周知这种东西背结论就好了

回到原来的问题，求每个盒子中的小球都与盒子标号不同的概率。按照错排公式算出5个盒子5个小球即错排问题的总数为44，最后除以5的全排列总数：

\dfrac{44}{A^5_5}=\dfrac{44}{5!}=\dfrac{44}{5 \times 4 \times 3 \times 2 \times 1}

约分后，得到答案为11/30