由一道高考试题谈全错位排列问题

摘 要：错位排列问题是排列组合问题中常见类型之一，解决方法常运用容斥原理但这个方法对大多数中学生来说相对陌生，不符合中學阶段常规思维.本文从中学课堂常规思路出发，步步探究，给出全错位排列问题的一套完整解决方案，以期对开拓学生数学思维有所帮助.

关键词：贺卡问题；全错位排列；递推公式；通项公式

作者简介：王常庆（1972-），男，山东郓城人，本科，中学高级教师，研究方向：中学数学教学.

一、问题的提出

题目 同室4人各写一张贺卡，然后收集起来，每人再从中各抽一张，但不能抽取自己写的那一张，问共有几种不同的抽法？

象这种“每个元素都不在限定的位置上”的排列问题，通常叫做全错位排列问题.全错位排列作为排列组合中的一类典型题目，难度较高. 笔者从常规思路出发，整理出一套完整的解决方案，现把研究过程及每一阶段的成果展示出来，供大家参考.

二、问题的解决

法一（顶针法） 假设A、B、C、D四人所写的贺卡分别为a、b、c、d，若先由A抽，共有3种抽法（b、c、d），若抽到b，则接下来由B抽，也有3种抽法（a、c、d），最后由C、D二人抽，均只有1种抽法，故由分步计数原理知共有3×3×1×1=9种抽法.

法二（列表法/枚举法） 把A、B、C、D四人依次抽到的贺卡情况具体列表如下，共有9种方案，如表1：

法三（树图法） 为防止发生重复或遗漏，可分步画图，如图1：

三、问题的探究

为方便探究，先对这类全错位排列问题进行定义.

设n个编号为1，2，3，…，i，…，j，…，n的不同元素a1，a2，a3，…，ai，…，aj，…，an排成一列，且每个元素均不排在与其编号相同的位置，这样的排列称为全错位排列，排列数记为Tn.

探究1 尝试变更元素个数n，依上述解决方法，易得T1=0，T2=1，T3=2.

探究2 变更元素个数为5时，其全错位排列数T5的求法如下：

（1）顶针法：若先由A抽，共有4种抽法；若抽到b，再由B抽，B抽到a与抽不到a，直接影响其他人的抽法，故而分为两类：

①若B抽到a，其余3人再抽取相当于一个独立 “3人组”，共有2种抽法；

②若B抽不到a，则B有3种抽法（c、d、e），设B抽到c，接下来由C抽，也有3种抽法，共有3×3=9种抽法.故题目最终结论为4×（2+3×3）=44种抽法.

（2）列表法、树图法均可解决，但工程庞大，不易操作.

探究3 由以上探究过程可知，当元素个数变更为5个时，其全错位排列数的求解已是不易，若是元素个数变更为6个、7个甚至更多时，又该如何计算呢？下面仍先以“4人贺卡问题”为例解析如下：

先不考虑4张贺卡的具体归属，由4人随意抽取，共有A44=24种抽法.其中包括以下不合题意的情况：

（1）4人中恰有1人取到自己写的贺卡（以下简称自取），其余3人再抽取，相当于一个独立的“3人组”，所以共有C14T3=4×2=8种抽法；

（2）4人中恰有2人自取，其余2人再抽，相当于一个独立的“2人组”，共有C24T2=6×1=6种抽法；

（3）4人全部自取，共有1种抽法（不可能出现恰有3人自取情况）.

故“4人组”贺卡的抽法共有T4 =A44-2×C14-1×C24-1=9种.

下面可用同样的方法完成T5的求解：

T5=A55-C15T4-C25T3-C35T2-1=44种.

小结 按上述解法，只要知道了T1，T2，T3，…的结果，依次递推下去，便可求出任意n个元素的全错位排列数Tn （n∈N*）. 当然，随着人数n的增加，分类越来越多，计算量也越来越大.

探究4 为进一步寻求规律、简化计算，笔者受到“斐波那契数列”的启发，把已求得的几个全错位排数Tn及相应元素个数n（n∈N*）列表如下（表2）

由这两个递推公式，易得到T6=265及T7=1854，将Tn的计算向前推进了一大步.

探究5 上述递推公式是通过不完全归纳法得到的，其正确性有待于证实.下面尝试利用计数原理、数学归纳法的有关知识进行证明.

1递推公式1的证明（利用计数原理）

首先易得T1=0，T2=1.

当n≥2时，总数为n+1个元素的全错位排列可分两步进行：

第一步，先从n+1个不同元素中任取一个元素ai，因其不能排在与其编号相对应的i 位，必排在剩下n 个位置之一，所以ai有n 种排法；

第二步，针对ai每一种排法，如果ai排在 j位，原对应j位的元素aj的排位又有两种情况：

第1种情况，若aj恰好排在i位上，如表3

此时，除ai外的其他n个元素（包括aj）均有一个不能排的位置（aj不排在i位上），问题就转化为其余这n个元素全错位排列，排列数为Tn.

故综合上述步骤，由乘法原理和加法原理可得：Tn+1=n （Tn-1+Tn） （n≥2， n∈N*）.

2递推公式2的证明（利用数学归纳法）

首先，易得T1=0，T2=1，显然当n=2时，Tn=n Tn-1+（-1）n 成立；

其次，假设当n=k时（k≥2， k∈N*），Tn=n Tn-1+（-1）n 成立，即Tk=k Tk-1+（-1）k.

从而k Tk-1 =Tk -（-1）k=Tk+（-1）k+1.

又由递推公式1可得Tk+1=k （Tk-1+Tk）.

从而Tk+1=kTk-1+kTk=Tk+（-1）k+1+kTk=（k+1 ）Tk+（-1）k+1.即Tk+1=（k+1 ）T（k+1）-1+（-1）k+1.故当n=k+1时，Tn=n Tn-1+（-1）n亦成立.

综合上述步骤可知，Tn=n Tn-1+（-1）n对于任意自然数n（n≥2， n∈N*）均成立.

探究6 上述公式虽已获得证明，但毕竟只是递推公式，如果能够利用构造数列的思想，导出{Tn}的通项公式，方才圆满.

解析 将Tn=n Tn-1+（-1）n的两边同时除以n！ 得

Tn n！ = nTn-1 n！ + （-1）nn！ = Tn -1 （n-1）！ + （-1）nn！.

从而有Tnn！-Tn-1（n-1）！=（-1）nn！.

于是，T22！-T11！=（-1）22！，T33！-T22！=（-1）33！，…，Tnn！-Tn-1（n-1）！=（-1）nn！.

将这n-1个等式累加得Tnn！-T11！=∑ni=2（-1）ii！.

又T1=0，故有Tnn！=∑ni=2（-1）ii！.

从而有Tn=n！∑ni=2（-1）ni！（n≥2， n∈N*）.

在解决排列组合问题时，经常涉及到全错位或部分错位的排列问题，在元素不是很多时，我们可以用枚举或树枝图的方法，也可利用排除的方法对问题进行讨论；但当元素较多时可尝试寻求排列数的递推公式或通项公式，以期对解决这一类问题提供方便.

参考文献：

[1]李宇襄组合数学[M].北京：北京师范大学出版社，2012.

[2]龚兵全错位排列[J].中学生数学，2011（17）：26

[3]程孝刚对错位排列问题的探究[J]高中数学教与学，2009（08）：42-43.