设有n个元素进行错位排序。
考虑第n个元素，它不能放在自己原来的位置上，所以有n-1种选择。假设第n个元素放在了第k个元素的位置上。分两种情况讨论：如果第k个元素放在了第n个元素的位置上，那么剩下的n-2个元素需要进行错位排序，共有D(n-2)种方法。如果第k个元素没有放在第n个元素的位置上，那么第k个元素也有n-1种选择，剩下的n-1个元素需要进行错位排序，共有D(n-1)种方法。综上，错位排序的递推公式为：D(n) = (n-1) * (D(n-1) + D(n-2))。初始条件为：D(0) = 1（0个元素错位排序只有一种方式，即不排），D(1) = 0（1个元素无法进行错位排序）。以上即为错位排序公式的推导过程。
