错排问题

定义

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

例子

伯努利-欧拉的装错信封的问题。

形式化定义

记为上没有不动点的排列(即的个数，的值如下：（由起）

规律

递推数列法

显然。

当时，不妨设n排在了第k位，其中，也就是。那么我们现在考虑的情况。

• 当k排在第位时，除了和以外还有个数，其错排数为。
• 当不排在第位时，那么将第位重新考虑成一个新的“第位”，这时的包括在内的剩下个数的每一种错排，都等价于只有个数时的错排（只是其中的第k位会换成第n位）。其错排数为。 所以当n排在第位时共有种错排方法，又有从到共种取法，我们可以得到：

生成函数

一

根据规律 可以得到如下：

二

从置换环的角度考虑，错排就是指置换环中不存在自环的排列。也就是说不存在长度为 的置换环。后者的指数生成函数是

因此错排数的指数生成函数就是 。

减掉非错排的情况

非错排：存在的排列

只存在一个：,

只存在二个：,

只存在三个：,

…

只存在n个：,

所以，

那一定是你程序写错了

通向公式

令

多项式模拟

最接近 的整数

考虑指数函数在 0 处的泰勒展开：

其中

所以

得