錯排問題
簡單來說，錯排問題就是問有多少個長度為\(n\)的排列\(p\)，使得對于所有的\(i\in [1,n]\)都有\(i \neq p_i\)，
遞推式
錯排的一個遞推式就是\(f(n)=(n-1)(f(n-1)+f(n-2))\)
這個遞推式復雜度顯然是線性的，
關于這個遞推式的推導請自行百度，這里不再贅述，
容斥法解錯排問題
第一次看到錯排問題的時候，并沒有推匯出上面的遞推式，而是用了一種容斥的方法，自認為更加簡單易懂吧，
既然是每個數字都不能放在對應的位置，那么按照容斥的一般套路，我們強制有\(i\)個數字放在了對應位置，其他數字不管他，顯然這\(i\)個數字有\(C(_n^i)\)種方案，其他數字有\((n-i)!\)種排列方式，
所以式子就很顯然了:
\[f(n)=\sum\limits_{i=0}^n(-1)^iC(_n^i)(n-i)! \\ =\sum\limits_{i=0}^n(-1)^i\frac{n!}{i!} \]復雜度同樣也是線性的，
其實可以發現，用容斥繼續推下去的話，依然可以推出上面的遞推式，所以這兩種解法本質上是等價的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137712.html
標籤：其他
上一篇：演算法總結