解决“错位排列”问题的一般方法

张仁海

问题同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送来的贺年卡，则四张贺年卡不同的分配方式有（）.

A.6种B.9种C.11种D.23种

这个问题等价于：将1，2，3，4这四个正整数分别填入编号为1，2，3，4的四个空位，且每个空位上所填数字与其序号均不相同，问有多少种不同的填法？我们称这样的排列为错位排列.这是一个很复杂的排列问题.下面，我们就来研究解决这类问题的一般方法.

我们把这类问题推广到一般情形：

将n个正整数1，2，3，…，n分别填入编号为1，2，3，…，n的n个空位，且每个空位上所填数字与其序号均不相同，并把所有这样排列的个数记为cn（借助“错”字拼音的首字母）.

显然，c1=0，c2=1.下面，我们来计算c3.需分两步完成：

第一步，填数字1在2和3号位中任选一个位置将数字1填入，有2种填法.不妨将其填入2号位.

第二步，填数字2.又分两类来完成：

① 若将数字2填入1号位，则只需将数字3错位填入3号位上，有c1种填法；

② 若不将数字2填入1号位，则须将数字2和3填入1号和3号位，这等价于将数字2和3错位填入2号和3号位（因为数字2不能填入1号位，也不能填入2号位），有c2种填法.由分类计数原理可知，填数字2有（c1+c2）种填法.最后，由分步计数原理得，c3=2（c2+c1）=2×（0+1）=2.

我们再来计算c4.仍需分两步完成：

第一步，填数字1.在2、3、4号位中任选一个位置将数字1填入，有3种填法.不妨将其填入2号位.

第二步，填数字2，又分两类来完成：

① 若将数字2填入1号位，则只需将数字3和4错位填入3号和4号位上，有c2种填法；

② 若不将数字2填入1号位，则须将数字2，3，4填入1号，3号，4号位，这等价于将数字2，3，4错位填入2号，3号，4号位（因为数字2不能填入1号位，也不能填入2号位），有c3种填法.由分类计数原理可知，填数字2有（c2+c3）种填法.

最后，由分步计数原理得，

c4=3（c3+c2）=3×（2+1）=9.

这就是开头的那道高考题的解，故此题选B.

同理可得：c5=4（c4+c3）=4×（2+9）=44.

观察：c3=2（c2+c1），c4=3（c3+c2），c5=4（c4+c3），….

猜想：cn=（n-1）（cn-1+cn-2）（n≥3）.

证明将n（n≥3）个正整数1，2，3，…，n错位填入编号为1，2，3，…，n的n个空位，需分两步完成：

第一步，填数字1，在2～n号位中任选一个k号位，将数字1填入，有n-1种填法.

第二步，填数字k，又分两类来完成：

①若将数字k填入1号位，则只需将数字2，3，…，k-1，k+1，…，n这n-2个正整数错位填入2，3，…，k-1，k+1，…，n有cn-2种填法；

②若不将数字k填入1号位，则须将数字2，3，…，k，…，n这n-1个正整数错位填入序号为1，2，3，…，k-1，k+1，…，n这n-1个空位，这等价于将数字2，3，…，k，…，n这n-1个正整数错位填入序号为2，3，…，k，…，n这n-1个空位中（因为数字k不能填入1号位，也不能填入k号位），有cn-1种填法.由分类计数原理可知，填数字k有cn-1+cn-2种填法.

最后，由分步计数原理得，

cn=（n-1）（cn-1+cn-2）（n≥3）.

因此，错位排列数的一个递推公式为：

c1=0，c2=1，cn=（n-1）（cn-1+cn-2）（n∈N*，n≥3）.

由此递推公式可知，错位排列数构成数列：

0，1，2，9，44，265，1 854，…，（n-1）（cn-1+cn-2），….

其排列规律是，从第3项起，以后的每一项都等于它前面两项和的项数减1倍.

一般情况下，在高中阶段，只要记住这个数列的前5项就足够了.

例1编号为1，2，3，4，5的五个人，分别坐在座号为1，2，3，4，5的座位上：

（1）没有一人号码一致的坐法有多少种？

（2）恰有两人号码一致的坐法有多少种？

（3）至多有两人号码一致的坐法有多少种？

解由错位排列数的递推公式知：

（1）没有一人号码一致的坐法有c5=44种.

（2）恰有两人号码一致的坐法有C25c3=10×2=20（种）.

（3）分三类：① 没有一人号码一致的坐法有c5=44种；

② 恰有一人号码一致的坐法有C15c4=5×9=45（种）；

③ 恰有两人号码一致的坐法有C25c3=10×2=20（种）.

由分类计数原理得，至多有两人号码一致的坐法有：44+45+20=109种.

例2某地进行换届选举，要从甲、乙、丙、丁4人中选出3人担任3种不同的职务，规定上界任职的甲、乙、丙3人不能连任原职，则不同的任职结果有种.

解分两类：

① 不含丁：因为甲、乙、丙不能任原职，这相当于3个元素的错位排列，所以有c3=2种；

② 含丁：因为甲、乙、丙不能任原职，故必有一人排空（无职位），而丁又不能排空（有职位），这相当于4个元素的错位排列，所以有c4=9种.

由分類计数原理，共有2+9=11（种）.

例3为了迎接青奥会的召开，某校举行了一次体育知识竞赛，其中一道题是连线题，要求将4种不同的消防工具与它们的4种不同的用途一对一连线.规定：每连对一条得5分，连错一条得-2分.某参赛者随机用4条线把消防工具与用途一对一全部连接起来.

（1）求该参赛者恰好连对一条的概率；

（2）设X为该参赛者此题的得分，求X的分布列与数学期望.

解（1）该参赛者恰好连对一条，有C14种可能，其他3条没连对，这相当于三个数的错位排列，有c3种可能，故有C14c3=4×2=8种不同的排法，而该参赛者连线的所有可能情况有A44=24种，故该参赛者恰好连对一条的概率为P=C14c3A44=824=13.

（2）X的所有可能取值为-8，-1，6，20.

P（X=-8）=c4A44=924，P（X=-1）=C14c3A44=4×224=824，

P（X=6）=C24c2A44=6×124=624，P（X=20）=1A44=124.

∴X的分布列为

X-8-1620

P924824624

124

∴X的数学期望为E（X）=（-8）×924+（-1）×824+6×624+20×124=-1.