全错位排列递推公式的简易推导(齐麟-晋级).pdf

全错位排列递推公式的简易证明
华图教育 齐麟
错位排列作为排列组合中的一类典型题目，自身难度较高，考生往往只是知其然而不知
其所以然，即只了解全错位排列的递推公式，而不能理解其含义以及灵活的运用。本文结合
图示的方法，对全错位排列公式进行简易的证明。
首先，我们先来认识错位排列：
1.部分错位排列：
【例】5 个人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法。
用排除法：
先考虑 5 个人的全排列，有A5 种不同的排法，然后除去甲排第一（有A4 种）与乙排第
5 4
二（也有A4 种），但两种情况又有重复部分，因此多减了一部分，必须加上多减部分，这样
4
得到共有： A5 －2 A4 ＋ A3 ＝78 种。
5 4 3
2.全错位排列：
【例】5 个人站成一排，其中 A 不站第一位，B 不站第二位，C 不站第三位，D 不站第
四位，E 不站第五位，共有多少种不同的站法。
【分析】仿照以上解法，我们有
故 5 人的全错位排列方式共有 44 种。
因此我们可以由容斥原理得到 n 个元素的全错位排列公式：
D =n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
n
错位排列的递推公式
简单计算后我们有： D  0 ； D  1； D  2 。
1 2 3
计算四元素全错位排列时我们可以这样考虑：
假定元素为 A、B、C、D；对应的位置为 a、b、c、d。对于元素 A，我们可将其
放在 b、c、d 三个位置，容易看出，这三个位置对于元素 A 来说是等价的；假定 A 现
在放在了 b 位置。
A B C D
此时，元素 B 有两种选择：①放在 a 位置；②不放在 a 位置；当元素 B 放在