联村联户民情日记-阎良飞机城论坛

排列组合问题之
全错位排列问题

（一个通项公式和两个递推关系）


一、问题引入：

问题
1
、
4
名同学各写 一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，
则四张贺卡的不同分配方式共有多少种？
问题
2
、
将编号为
1
，
2
，3
，
4
的四个小球分别放入编号为
1
，
2
，< br>3
，
4
的四个盒
子中，要求每个盒子放一个小球，且小球的编号与盒子 的编号不能相同，则共有多少种不同
的放法？
这两个问题的本质都是每个元素都不在 自己编号的位置上的排列问题，我们把这种限制
条件的排列问题叫做
全错位排列问题
。
问题
3
、
五位同学坐在一排，现让五位同学重新坐，至多有两位同学 坐自己原来的位
置，则不同的坐法有多少种？

解析：
可以分类解决：第一类，所有同学都不坐自己原来的位置；
第二类，恰有一位同学坐自己原来的位置；
第三类，恰有两位同学坐自己原来的位置。
对于第一类，就是全错位排列问题；对于第二、 第三类有部分元素还占有原来的位置，
其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题
。
设
n
个元素全错位排列的排列数为T
n
，则对于问题
3
，第一类全错位排列的排列数为
T
5
；
第二类先确定一个排原来位置的同学有
5
种可能，其余四个同学全错位排 列，所以第
2
二类的排列数为
5T
4
；
第三类先确定两个排 原位的同学，有
C
5
10
种可能，其余三个同学
全错位排列，所以 第三类的排列数为
10T
3
，因此问题
3
的答案为：
T5
5T
4
10T
3
109
。

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

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

T
n


n1

T
n1
T
n2



n3


①定义：一般 地，设
n
个编号为
1
、
2
、
3
、… 、< br>i
、…、
j
、…、
n
的不同元素
a
1
、
a
2
、
a
3
、…、
a
i
、… 、
a
j
、…、
a
n
，排成一排，且每个元素均不排在与其编 号相同的位
置，这样的全错位排列数为
T
n
，则
T
21
；
T
3
2
；
T
n


n1

T
n1
T
n2

，
n3

。

②递推关系的确立：
显然当
n1
、
2
时，有
T
1
0
，T
2
1
。

当
n3
时，在
n
个不同元素中任取一个元素
a
i
不排在与其编号相对应的
i 位，必排在
剩下
n1
个位置之一，所以
a
i
有n1
种排法。
对
a
i
每一种排法，如
a< br>i
排在
j
位，对应
j
位的元素
a
j
的排位总有两种情况：
第一种情况：
a
j
恰好排在
i位上。此时，
a
i
排在
j
位，
a
j
排 在
i
位，元素
a
i
，
a
j
排位
已 定。还剩
n2
个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为
n 2

个元素全错位排列数，应有
T
n2
种。
第二种情 况：
a
j
不排在
i
位上。此时，
a
i
仍排 在
j
位，
a
j
不排在
i
位，则
a
j
有
n1
个
位置可排。除
a
i
外，还有
n1
个元素，每个元素均有一个不能排的位置，问题就转化为
n1
n
个元 素全错位排列数，应有
T
n1
种。
由乘法原理和加法原理可得：
T
n


n1

T
n1
T
n2

，

n3

。

利用此递推 关系可以分别算出
T
4
9
，
T
5
44
。
排列组合问题之全错位排列问题（共3页）

1

问题
3
的答案为：
4459102109
。

三、全错位排列数的通项公式之一：
é
11
n
1
ù

T
n
=n!
ê
-+...+-1×
ú


n2


n!
ûë
2!3!
()
0
㈠探索：规定
A
n
1nN
，试计算以下各式的值：

210
321043210
①
A
4
； ②
A
5
； ③
A
6
。
A
4
A
4
A
5
A
5
A
5
A
6
A
6
A
6
A
6< br> 很容易计算三式的值依次为
9
，
44
，
265。
而这与利用上面的递推关系式得到的
T
4
，
T
5，
T
6
刚好吻合。即

T
21
A
0
321043210
4

A
4
A
44
；
T
5

A
5
A
5
A
5
A
5
；
T
6

A
6
A< br>6
A
6
A
6
A
6
。
㈡猜想：
根据上面的探索，我们可以猜想
n
个元素全错位排列数为 < br>T
=A
n-2n-3
0
nn
-A
n
+... +
(
-1
)
n
A
n


n2







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

T
n-2n-3
()
n
0
n
n!
n
=A
n< br>-A
n
+...+-1
A
n

=
n!
-
n!
+...+
(
-1


=n!
é
2!3!
)
n!
ê
11
n
1
ù
ë
2!
-
3!
+...+< br>(
-1
)
×
n!
ú
û
。

㈢证明（数学归纳法）：
当
n2
，
3
时，



式显然成立。
假设
nk
，
k1
时，



式成立。
则当
nk1
时，由上面的递推关系式可得：

T
k1
k

T
k
T
k1


ì

=k
ï
í
ï
k!
é< br>ê
1
-
1
+...+
(
-1
)
k< br>1
ù
()
é
+k-1!
ê
1
-
1< br>+...+
(
-
)
k-1
1
ù
ü
(
)
ú
ï
î
ë
2!3!
k!
ú
û< br>ê
1
ý
ï

ë
2!3!
k-1
!< br>ú
û
þ
ì
ï
é

=k
(
k-1
)
!
í
11
k
1
ù
é
k- 1
ù
ü
ï
ï
k
ê
î
ë
2!
-
3!
+...+
(
-1
)
k!
ú
û< br>+
ê
1
ê
ë
2!
-
1
3!
+...+
(
-1
)
1
(
k-1
)
!ú
ú
ý

û
ï
þ
é
!
ê(
)
k-1

=k
k+1
ê
-
k+ 1
+...+-1
k+1
()
+k
(
-1
)
k
1
ù
ú

ë
2!3!
k-1
!
k!
ú
û
é

=k!
ê
k+1
ê
-
k+1
+...+
(
-1
)
k-1
k+1
ù
()
+
(
)
(
)
k
1
(
)
k
1
ú
ë
2!3!
k-1
!
k+1-1
k!
--1
k!< br>ú
û

é
k-1

=k!
ê
k+ 1k+1
k
1
k
k+1
ù
ê
-
k+1ë
2!3!
+...+
(
-1
)
(
k-1)
!
+
(
k+1
)
(
-1
)
k!
-
(
-1
)
(
k+1
)
!
ú
ú
û

é

=k!
ê
k+1
ê
-
k+1
+...+-1
k-1
k+1
+k+1-1
k
1
+-
k+1
k+1
ù
ú
ë
2!3!
(
)
(
k-1
)
!
(
)
(
)
k!
(
1
)
(
k+1
)
!
ú
û

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

2

(
)
é

=k+1!
ê
11
(
)
k-1
1
ê
-+...+-1
()
+
(
-1
)
k
1
+
(
-1
)
k+1
1
ù
()
ú

ë
2!3!
k-1
!
k!
k+1
!
ú
û
所以，当
nk1
时，



式也成立。
由以上过程可知
n
个元素全错位排列的排列数为：

T
n-2 n-3
()
n
0
n!
-
n!
+...+
(
-1
)
n
n!
n
=A
n
-A
n< br>+...+-1
A
n

=

=n!
é
2!3!
n!

ê
1
ë
2!
-
1
3!
+...+
(
-1
)
n×
1
ù
n!
ú
û


n2



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

TnT
n
n

n1


1


由
T
2
1
，
T
3
2
，
T
4
9
，
T
5
44
，
T< br>6
265
可得：

T
3
3T
2
1
；
T
4
4T
3
1
；
T< br>5
5T
4
1
；
T
6
6T
5< br>1

于是猜想：
T
n
nT
n1


1

n

证明：由上面已证明的全错位排列数通项公式可知：
(
)
é
右边
= nn-1!
ê
11
(
)
n-1
1
ù
ê-+...+-1×
()
ú
+
(
-1
)
n
ë
2!3!
n-1
!
ú
û
é
n-< br>ù

=n!
ê
1
ê
ë
2!
-< br>1
3!
+...+
(
-1
)
1
×
1
(
n-1
)
!
ú
ú
+
(
-1)
n
n!

û
n!


=n!< br>é
ê
1
ë
2!
-
1
3!
+...+
(
-1
)
n
×
1
ù
n!
ú
û
=
左边
所以
T
n
nT
n1

1

n
。

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

3