错排（错排列）

定义

考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。

递推公式

第一步

把第n个元素放在一个位置，比如位置k,一共有n−1种放法。

第二步

放编号为k的元素，此时有两种情况。

1. 把它放到位置n
2. 第k个元素不把它放到位置n

讨论情况1，当第k个元素放在位置n后，还剩有 n−2个元素，它们进行错排有D(n-2)种方法。

再讨论情况2，当第k个元素不放在位置n，这是，对于未排的 n−1个元素，有D(n-1)种方法。

此时可得到公式

Q.E.D.