错排问题

错排问题是当 n 个编号元素放在 n 个编号位置,错排的方法数记着 f(n)

因为之前面试的时候被问到了,感觉比较有意思,然后好像还挺常见的,所以就记一下好了。

其实就是动态规划,写出转移方程就好了。

  1. f(n - 1) 然后在放第 n 个元素,此时,对 f(n - 1) 的任何一种情况,第 n 个元素和前 n - 1 个元素交换,都可以的。所以这里有 (n - 1)f(n - 1)
  2. 当 n - 1 个元素里有一个元素在正确位置,此时为 (n - 1)f(n - 2) 个,此时只要第 n 个元素和其中的正确元素交换,就是一个错排。
  • $f(1) = 0$
  • $f(2) = 1$
  • $f(n) = (n - 1) [f(n - 2) + f(n - 1)]$