错排问题

存在一个排列 ({P_i}) ，求有多少个排列 ({S_i}) 满足 (forall P_i ot = S_i) 。

错排公式

令 (f(n)) 为有 (n) 个元素的错排个数，显然 (f(1) = 0, f(2) = 1) 。

我们会有一个递推公式：

[f(n) = (n - 1)(f(n - 2) + f(n - 1)) ]

考虑新加进来一个元素，肯定不能放到它原来的位置，那么就是放到其他 (n - 1) 个位置中的一个。然后考虑另外一个被占位置的元素，如果它填到当前这个位置那么会剩下 (n - 2) 需要错排那么就是 (f(n - 2)) ，不填到当前这个位置那么就剩下所有数都一起错排就是 (f(n - 1)) 。

这个显然是满足要求的一个计数，那么我们就可以枚举“犯了几个错误”，也就是至少有几个会在原位。

[f(n) = sum_{i=0}^{n} (-1)^{i} frac{n!}{i!} ]

我们在之前那个问题上扩展一点，我们可以使得其中 (k) 个不存在限制。（也就是这个 (k) 个位置可以不满足 (P_i ot = S_i) ）

这个可以用一个神奇的 (dp) 去计数，令 (dp_{i, j}) 为前 (i) 个数，有 (j) 个不存在限制。

显然对于 (j = 0) 的时候我们可以和错排一样转移：

[dp_{i, 0} = (i - 1) (dp_{i - 1, 0} + dp_{i - 2, 0}) ]

那么对于 (j ge 1) 的时候考虑新填一个元素造成的局面：

[dp_{i, j} = dp_{i - 1, j - 1} + dp_{i - 1, j} ]

前面就是新填的元素放到自己位置，那么就和 (dp_{i - 1, j - 1}) 的局面是一样的了，后面就是放到其他任意一个位置那么不难发现这个和 (dp_{i - 1, j}) 的局面是一样的。

这样就可以结束这个扩展问题了。（注意前面边界问题就行了）

其实应该可以更优秀地解决这个问题，因为可以发现 (dp_{i, j}) 和 (displaystyle {j choose i}) 的递推形式是一样的，所以我们可以 (O(n)) 推出第一行并且预处理阶乘及其逆元，那么我们可以用一个组合数直接算上去就行了。

至于是否有更好的实现，我并不是很清楚。。。

ps: 本文来自 zhou888 在今天考试中推的神奇 (dp) ，很有启发～