“全错位排列问题”递推公式证明

“全错位排列问题”递推公式证明

华图教育 王品乐

问题描述：

位置

1

2

3

……

元素

……

如上表所示，为 个元素的原始序列，现打乱其顺序，使得每一个元素都不在原位置上（称为“全错位排列”），则一共可以产生多少种新的全错位排列？

简单枚举：

记 个元素所对应的全错位排列数为 ，则

时， ，

时， ，即

时， ，即 或

时，会发现随着 的增大，相应的全错位排列数会激增，使用列举的方法进行求解显然是不明智的。

递推公式证明：

假设我们已经解决了 到 ，那么当序列新增了一个元素 ，显然全错位排列要求 不能放在第 个位置上，假设 放在从1到 中的第 个位置上，那么在新序列中第 个位置上的元素可能有以下两种情况：

①第 个位置上的元素为

此时 和 都不在原位置上，因此只需剩余的元素都是全错位排列，新序列就构成了全错位排列。那么除去 和 还剩下 个元素，则这 个元素一共有 种全错位排列，因为位置 的选择共有 种，因此该情况下一共有 种全错位排列。

②第 个位置上的元素不是

该种情况相当于，前 个元素做好了全错位排列，共有 种。 与其中任意元素交换位置，新生成的序列也是一个全错位排列。这种情况下位置 的选择共有 种，因此该情况下一共有 种全错位排列。

综合以上两种情况， ，显然这个公式适用于 的情况，而 、 之前已经列举得出，代入递推公式可得 、 、 ……