关于错位排列问题的探讨

关键词：全错位排列，全错位排列数的通项公式，全错位排列数的递推关系式

一．生活中的错位排列问题

先看题一 4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有 种.

题二 将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有 种不同的放法.

这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题.

再看题三 五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有 种.

题三可以分类解决：

第一类，所有同学都不坐自己原来的位置；

第二类，恰有一位同学坐自己原来的位置；

第三类，恰有两位同学坐自己原来的位置.

对于第一类，就是上面讲的全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题.

设n个元素全错位排列的排列数为Tn，则对于题三，第一类排列数为T5，第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第二类的排列数为

25T4，第三类先确定两个排原位的同学，有C5=10种，所以第三类的排列数为10T3，因此题

三的答案为：T5+5T4+10T3.

由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法.

二．关于全错位排列数的一个递推关系式

1.一般地，设n个编号为1、2、3、… 、i、…、j、…、n的不同元素a1、a2、a3、…、ai、…、aj、…、an，排在一排，且每个元素均不排在与其编号相同的位置，这样的全错位排列数为Tn ，则 T2=1，T3=2，Tn= (n-1) ( Tn-1+Tn-2) ，（n≥3）.

2.递推关系的确立

显然对于n=1，2时有T1=0，T2=1.

当n≥3时，在n个不同元素中任取一个元素ai不排在与其编号相对应的i 位，必排在剩下n-1 个位置之一，所以ai有n-1 种排法.

对ai每一种排法，如ai排在 j位，对应j位的元素aj的排位总有两种情况： 第一种情况：aj恰好排在i位上，如表（1）

表（1）

此时，ai排在j位，aj排在i位，元素ai，aj排位已定，还剩 n-2个元素，每个元素均

有一个不能排的位置，它们的排位问题就转化为n-2 个元素全错位排列数，应有 Tn-2种；

第二种情况：aj不排在i位上，如表（2）

表（2）

此时，ai仍排在j位，aj不排在i位，则aj有n-1个位置可排，除ai外，还有n-1个元素，每个元素均有一个不能排的位置，问题就转化为n-1个元素全错位排列，排列数为Tn-1，由乘法原理和加法原理可得：Tn=(n-1)(Tn-1+Tn-2) ，（n≥3）.

利用此递推关系可以分别算出T4=9，T5=44，所以题三的答案为44+5×9+10×2=109.

三．关于全错位排列数的一个通项公式

1.探索

0 规定An=1（n∈N*），试计算以下各式的值：

210（1）A4； -A4+A4

3210（2）A5； -A5+A5-A5

43210（3）A6. -A6+A6-A6+A6 很容易计算三式的值依次为9，44，265.而这与利用上面的递推关系式得到的T4，T5，T6刚好吻合，即

210T4=A4； -A4+A4

3210T5=A5； -A5+A5-A5

43210T6=A6. -A6+A6-A6+A6

2.猜想

根据上面的探索，我们可以猜想n个元素全错位排列的排列数为

n-2n-30Tn=An（n≥2） （*） -An+⋅⋅⋅+(-1)nAn

为了更容易看清其本质，我们对这个式子进行变形，得到：

n-2n-30Tn=An -An+⋅⋅⋅+(-1)nAn

=n!n!n!111-+⋅⋅⋅+(-1)n⋅=n!⋅[-+⋅⋅⋅+(-1)n⋅] 2!3!n!2!3!n!

3.证明（数学归纳法）

n=2，3时（*）式显然成立；

假设n=k，k-1时（*）式成立，则当n=k+1时，有上面的递推关系式可得：

Tk+1= k(Tk+Tk-1)

=k{k!⋅[111111-+⋅⋅⋅+(-1)k⋅]+(k-1)!⋅[-+⋅⋅⋅+(-1)k-1⋅]} 2!3!k!2!3!(k-1)!

111111-+⋅⋅⋅+(-1)k⋅]+[-+⋅⋅⋅+(-1)k-1⋅]} 2!3!k!2!3!(k-1)!= k·(k-1)!·{k⋅[

= k!·[1k+1k+1k+1k+k·(-1)⋅] -+⋅⋅⋅+(-1)k-1⋅k!2!3!(k-1)!

=k!·[k+1k+1k+1)1-+⋅⋅⋅+(-1)k-1⋅+（k+1）·(-2!3!(k-1)!

k+1k+1k+11)+（k+1）·(--+⋅⋅⋅+(-1)k-1⋅2!3!(k-1)!

k+1k+1k+1k-1k⋅11--()1⋅k] k!k!1k+1] --()1⋅kk!(k+!)11k+1k+1= k!·[k⋅k= k!·[2!-3!+⋅⋅⋅+(-1)⋅(k-1)!+（k+1）·(-1)⋅k!+-()1⋅(k+!)1= (k+1)!·[1

2!-1

3!+⋅⋅⋅+(-1)k-1⋅1k11

(k-1)!+(-1)⋅k!+(-1)k+1⋅(k+1)!].

∴n=k+1时（*）式也成立.

由以上过程可知n个元素全错位排列的排列数为：

Tn=An-2n-3n0

n-An+⋅⋅⋅+(-1)A=n!n

n2!-!

3!+⋅⋅⋅+(-1)n⋅n!

n! =n!⋅[1

2!-1

3!+⋅⋅⋅+(-1)n⋅1

n!]（n≥2）.

四. 关于全错位排列数的另一个递推关系式

由T2=1，T3=2，T4=9，T5=44，T6=265可得：

T3=3T2－1；

T4=4T3+1；

T5=5T4－1；

T6=6T5+1.

于是猜想Tn=nTn-1+(-1)n.

证明：由上面已证明的全错位排列数公式可知

右边=n·(n-1)!⋅[111

2!-3!+⋅⋅⋅+(-1)n-1⋅(n-1)!]+(-1)n

= n!⋅[1-1+⋅⋅⋅+(-1)n-11n!

2!3!⋅(n-1)!]+(-1)n·n! =n!⋅[1

2!-11

3!+⋅⋅⋅+(-1)n⋅n!]=左边.

]