定义: n 个元素排成一列, 若每个元素所处位置的序号都与它的编号不同, 则称这个排列为 n 个不同元素的一个错排.

理解: 首先把第 1 个元素放到第 k 位一共有 (n-1) 种选择, 第 k 位的元素有两种选择. 第一种是把第 k 位的元素放到第 1 位, 则剩下的元素一共有 D(n-2)种排法, 第 2 种是把第 k 位放到其他位置, 则剩下的元素 (包括 k) 一共有 D(n-1)种排法. 后面的元素也按这种方式排列, 所以递归式如下.

公式: D(n)=(n-1)*(D[n-2]+D[n-1]), 其中 D[1]=0,D[2]=1.

放一段 C++ 代码 (递推) 以供测试:

using namespace std;

int main()
{
    int D[100];
    D[1] = 0;
    D[2] = 1;
    int n;
    cin >> n;
    for (int i = 3; i <= n; i++)
    {
        D[i] = (i - 1)*(D[i - 2] + D[i - 1]);
    }
    cout << D[n] << endl;
}