“全错位排列问题”递推公式证明，今天小编就来聊一聊关于数学排列组合递推法?接下来我们就一起去研究一下吧!
数学排列组合递推法
“全错位排列问题”递推公式证明
华图教育 王品乐
问题描述：
位置
1
2
3
……
元素
……
如上表所示，为 个元素的原始序列，现打乱其顺序，使得每一个元素都不在原位置上（称为“全错位排列”），则一共可以产生多少种新的全错位排列？
简单枚举：
记 个元素所对应的全错位排列数为 ，则
时， ，
时， ，即
时， ，即 或
时，会发现随着 的增大，相应的全错位排列数会激增，使用列举的方法进行求解显然是不明智的。
递推公式证明：
假设我们已经解决了 到 ，那么当序列新增了一个元素 ，显然全错位排列要求 不能放在第 个位置上，假设 放在从1到 中的第 个位置上，那么在新序列中第 个位置上的元素可能有以下两种情况：
①第 个位置上的元素为
此时 和 都不在原位置上，因此只需剩余的元素都是全错位排列，新序列就构成了全错位排列。那么除去 和 还剩下 个元素，则这 个元素一共有 种全错位排列，因为位置 的选择共有 种，因此该情况下一共有 种全错位排列。
②第 个位置上的元素不是
该种情况相当于，前 个元素做好了全错位排列，共有 种。 与其中任意元素交换位置，新生成的序列也是一个全错位排列。这种情况下位置 的选择共有 种，因此该情况下一共有 种全错位排列。
综合以上两种情况， ，显然这个公式适用于 的情况，而 、 之前已经列举得出，代入递推公式可得 、 、 ……
,
