问题：已知一个长度为 $n$ 的 $1 \sim n$ 的排列。设 $f(i)$ 表示有多少个长度为 $n$ 的排列，满足有恰好 $i$ 个位置与已知排列相同。显然，$f(0)$ 就是错排问题的答案。

$n$ 个元素的错排问题 $d(n)$ 可以这么求：

$$f(0) = d(n) = n! - {n! \over 1!} + {n! \over 2!} - {n! \over 3!} + \dots$$

$n!$ 后面的部分实际上在容斥至少有若干个位置相同的情况。

由此似乎可以得出一个递推式子计算 $f(i)$：

$$f(n) = 1 \\ f(i) = {{n!} \over {(n-i)!}} - f(i+1)$$

但这是错的。为什么呢？

另一种计算方式为：

$$f(i) = {n \choose i} \times d(n-i)$$

其中 $d(n)$ 仍然定义为 $n$ 个元素的错排方案数。特别地，$d(0)=1$。

这好像是对的。为什么呢？