排列组合问题之全错位排列问题 （一个通项公式和两个递推关系）

一、问题引入：

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

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

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

问题3、五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有多少种？

解析：可以分类解决：第一类，所有同学都不坐自己原来的位置； 第二类，恰有一位同学坐自己原来的位置； 第三类，恰有两位同学坐自己原来的位置。

对于第一类，就是全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题。 设n个元素全错位排列的排列数为Tn，则对于问题3，第一类全错位排列的排列数为

T5；第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第

2二类的排列数为5T4；第三类先确定两个排原位的同学，有C5?10种可能，其余三个同学

全错位排列，所以第三类的排列数为10T3，因此问题3的答案为：T5?5T4?10T3?109。 由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法。

二、全错位排列数的递推关系式之一：

Tn??n?1??Tn?1?Tn?2? ?n?3?

①定义：一般地，设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?。 ②递推关系的确立：

显然当n?1、2时，有T1?0，T2?1。

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

对ai每一种排法，如ai排在j位，对应j位的元素aj的排位总有两种情况： 第一种情况：aj恰好排在i位上。此时，ai排在j位，aj排在i位，元素ai，aj排位已定。还剩n?2个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为n?2 个元素全错位排列数，应有Tn?2种。

第二种情况：aj不排在i位上。此时，ai仍排在j位，aj不排在i位，则aj有n?1个位置可排。除ai外，还有n?1个元素，每个元素均有一个不能排的位置，问题就转化为n?1n个元素全错位排列数，应有Tn?1种。

由乘法原理和加法原理可得：Tn??n?1??Tn?1?Tn?2?，?n?3?。 利用此递推关系可以分别算出T4?9，T5?44。

排列组合问题之全错位排列问题（共3页）

1

问题3的答案为：44?5?9?10?2?109。

三、全错位排列数的通项公式之一：

n1??11 Tn?n!???????1??? ?n?2?

n!??2!3!0? ㈠探索：规定An?1n?N，试计算以下各式的值：

??210321043210 ①A4； ②A5； ③A6。 ?A4?A4?A5?A5?A5?A6?A6?A6?A6 很容易计算三式的值依次为9，44，265。而这与利用上面的递推关系式得到的T4，

T5，T6刚好吻合。即

T?A21032104321044?A4?A4；T5?A5?A5?A5?A5；T6?A6?A6?A6?A6?A6。 ㈡猜想：

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

Tn?2n?3n0n?An?An?????1?An ?n?2? ???

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

Tn?2n?31?nA0n?An?An?????n ?n!2!?n!3!?????1?nn!n! ?n!??1?2!?13!?????1?n?1?n!??。

㈢证明（数学归纳法）：

当n?2，3时，???式显然成立。 假设n?k，k?1时，???式成立。

则当n?k?1时，由上面的递推关系式可得： Tk?1?k?Tk?Tk?1?

?k????11k1??k!?k??11k?11??????2!?3!?????1?k!???1?!??2!?3!?????1??k?1?!???? ? ?k?k?1?!????k??????1?k??1?2!?11?3!k!?????1?1?????1?k?11????2!3!?k?1?!??? ?? ?k!??k?1?k?1?????1?k?1k?1?k?2!3!?k?1?!??1?k1?k!? ? ?k!??k?1k??2!?13!?????1?k?1k?1?k?1?!??k?1???1?k1k!???1?k1?k!? ? ?k!??k?1?k?1?????1?k?1k?1??2!3!?k?1?!?k?1???1?k1kk?1?k!???1??k?1?!? ? ?k!??k?1k?1k?1k?1?2!?3!?????1??k?1?!??k?1???1?k1k?1k?1?k!???1??k?1?!? ? ??k?1?!??1?1k?11??2!3!?????1??k?1?!??1?k1k!???1?k?11??k?1?!?

? 所以，当n?k?1时，???式也成立。

排列组合问题之全错位排列问题（共3页）

2

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

Tn?2An?3n0!n!nn!n?An?n?????1?An ?n2!?3!?????1?n! ?n!??1?2!?13!?????1?n?1?n!?? ?n?2?

四、全错位排列数的递推关系式之二：

Tnn?nTn?1???1?

由T2?1，T3?2，T4?9，T5?44，T6?265可得： T3?3T2?1；T4?4T3?1；T5?5T4?1；T6?6T5?1 于是猜想：Tnn?nTn?1???1?

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

右边?n?n?1?!??1?1?????1?n?1?1?n?2!3!?n?1?!?????1?

?n!??1?1?????1?n?1?1?nn!?2!3!?n?1?!?????1?n!

?n!?n?1?2!?13!?????1??1?n!???左边

所以Tnn?nTn?1???1?。

排列组合问题之全错位排列问题（共3页）

3