大家好，欢迎来到IT知识分享网。
“全错位排列问题”递推公式证明
华图教育 王品乐
问题描述：
位置
1
2
3
……
元素
……
如上表所示，为 个元素的原始序列，现打乱其顺序，使得每一个元素都不在原位置上（称为“全错位排列”），则一共可以产生多少种新的全错位排列？
简单枚举：
记 个元素所对应的全错位排列数为 ，则
时， ，
时， ，即
时， ，即 或
时，会发现随着 的增大，相应的全错位排列数会激增，使用列举的方法进行求解显然是不明智的。
递推公式证明：
假设我们已经解决了 到 ，那么当序列新增了一个元素 ，显然全错位排列要求 不能放在第 个位置上，假设 放在从1到 中的第 个位置上，那么在新序列中第 个位置上的元素可能有以下两种情况：
①第 个位置上的元素为
此时 和 都不在原位置上，因此只需剩余的元素都是全错位排列，新序列就构成了全错位排列。那么除去 和 还剩下 个元素，则这 个元素一共有 种全错位排列，因为位置 的选择共有 种，因此该情况下一共有 种全错位排列。
②第 个位置上的元素不是
该种情况相当于，前 个元素做好了全错位排列，共有 种。 与其中任意元素交换位置，新生成的序列也是一个全错位排列。这种情况下位置 的选择共有 种，因此该情况下一共有 种全错位排列。
综合以上两种情况， ，显然这个公式适用于 的情况，而 、 之前已经列举得出，代入递推公式可得 、 、 ……
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/88322.html
