错位排列及有关例题

求n个数（不相同）错位排列的个数。

何为错位排列？定义如下：对于n的一个排列a1,a2,a3...an。

如何求解错位排列？

考虑动态规划的解法。

前i个元素时如何进行状态转移？

（一）首先由于要求错位排列，第i个元素肯定不会放在自己的位置上，故第i个元素的位置有i-1种选择。

（二）对于剩下的i-1个元素，选择其中的一个元素k。这时候k有两种选择：

　　1. 放在第i个元素的位置上，宏观上相当于i与k的位置互换了。而剩下的i-2个元素依然要求错位排列。

　　2. 不放在第i个元素的位置上，则相当于剩下的i-1个元素全部进行错位排列。

综上，我们可以得到：f[i] = (i-1) * ( f[i-1] + f[i-2] );

\(F_{n} = F_{n-1} + F_{n-2}\)

错位排列及有关例题

原文：https://www.cnblogs.com/qixingzhi/p/9285830.html