错排问题

定义考虑一个有𝑛个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 𝑛个元素的错排数记为𝐷𝑛或!𝑛。例子伯努利-欧拉的装错信封的问题。形式化定义记𝐷𝑛为{1,2,…,𝑛}上没有不动点的排列(即𝜙:{1,2,…,𝑛}→{1,2,…,𝑛},𝜙(𝑖)≠𝑖,∀1≤𝑖≤𝑛的个数，𝐷𝑛的值如下：（由𝑛=1起）0,1,2,9,44,265,1854,14833,133496,1334961,14684570,176214841,2290792932...规律𝐷𝑛=𝑛𝐷𝑛−1+(−1)𝑛递推数列法显然𝐷1=0,𝐷2=1。当𝑛≥3时，不妨设n排在了第k位，其中𝑘≠𝑛，也就是1≤𝑘≤𝑛−1。那么我们现在考虑𝑘的情况。•当k排在第𝑛位时，除了𝑛和𝑘以外还有𝑛−2个数，其错排数为𝐷𝑛−2。•当𝑘不排在第𝑛位时，那么将第𝑛位重新考虑成一个新的“第𝑘位”，这时的包括𝑘在内的剩下𝑛−1个数的每一种错排，都等价于只有𝑛−1个数时的错排（只是其中的第k位会换成第n位）。其错排数为𝐷𝑛−1。 所以当n排在第𝑘位时共有𝐷𝑛−2+𝐷𝑛−1种错排方法，又𝑘有从1到𝑛−1共𝑛−1种取法，我们可以得到：𝐷𝑛=(𝑛−1)(𝐷𝑛−1+𝐷𝑛−2)生成函数一根据规律 𝐷𝑛=𝑛𝐷𝑛−1+(−1)𝑛可以得到如下：𝐷(𝑥)=𝑥𝐷(𝑥)+𝑒−𝑥=𝑒−𝑥1−𝑥=1−𝑥+𝑥22!+...+(−1)𝑛𝑥𝑛𝑛!+...1−𝑥二从置换环的角度考虑，错排就是指置换环中不存在自环的排列。也就是说不存在长度为 1 的置换环。后者的指数生成函数是∑𝑛≥2𝑥𝑛𝑛=−ln(1−𝑥)−𝑥因此错排数的指数生成函数就是 exp(−ln(1−𝑥)−𝑥)。减掉非错排的情况非错排：存在𝑝𝑖=𝑖的排列只存在一个：𝐶1𝑛𝐷𝑛−1,只存在二个：𝐶2𝑛𝐷𝑛−2,只存在三个：𝐶3𝑛𝐷𝑛−3,…只存在n个：𝐶𝑛𝑛𝐷𝑛−𝑛,所以，𝐷𝑛=𝑛!−(𝐶1𝑛𝐷𝑛−1+𝐶2𝑛𝐷𝑛−2+𝐶3𝑛𝐷𝑛−3+...+𝐶𝑛𝑛𝐷𝑛−𝑛)=∑𝑛𝑘=0(𝑛𝑘)(𝑛−𝑘)!那一定是你程序写错了通向公式令𝐷𝑛=𝑛!𝑀𝑛𝑀𝑛−𝑀𝑛−1=(−1)𝑛1𝑛!𝐷𝑛=𝑛!(12!−13!+14!−...+(−1)𝑛1𝑛!)多项式模拟𝐷𝑛最接近 𝑛!𝑒 的整数考虑指数函数在 0 处的泰勒展开：𝑒−1=1+(−1)11!+(−1)22!+(−1)33!+...+(−1)𝑛𝑛!+𝑒−𝑐(𝑛+1)!(𝑐−1)𝑛=𝐷𝑛𝑛!+𝑅𝑛其中|𝑅𝑛|≤𝑒0(𝑛+1)!=1(𝑛+1)!所以|𝑛!𝑒−𝐷𝑛|≤𝑛!(𝑛+1)!=1𝑛+1得𝐷𝑛=⌊𝑛!𝑒+0.5⌋