loladc符文-不是我的错

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

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


一、问题引入：

问题
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
。

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

T
n
n!





1< br>




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
A
21 0
321043210
4
4
A
4
A
4
；
T
5

A
5
A
5
A
5A
5
；
T
6

A
6
A
6
A
6
A
6
A
6
。

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

T
n2n3
n
0
n
A
n
A
n


1

A
n


n2






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

T
n2n3
1

n
A
0
n
A
n
A
n



n< br>

n!
2!

n!
3!


1

n
n!
n!


n !


1

2!

1
3!



1

n

1

n!


。

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

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


k




11
k< br>1


k!k

11
k1
1






2!

3!



1

k!



1

!


2!

3!




1


k1

!







k

k1
< br>!




k



< br>
1

k


1

2!

11

3!k!





1

1




1

k11




2!3!

k1
!







k!


k1

k1




 1

k1
k1
k

2!3!

k 1

!

1

k
1

k!



k!


k1k

2!

1
3!




1
k1
k1

k1

!

< br>k1

1

k
1
k!

< br>1

k
1

k!




k!


k1

k1




1

k1
k1


2!3!< br>
k1

!

k1

1

k
1
k
k1

k!


1< br>

k1

!




k!


k1k1
k1
k1

2!< br>
3!




1


k1

!


k1

1

k
1
k1
k1

k!


1

k1

!






k1

!


1

1k1
1


2!3!



1


k1

!

1

k
1
k!


1

k1
1


k1

!



所以，当
nk1
时，



式也成立。
排列组合问题之全错位排列问题（共3页）

2

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

T
n2
A
n3
n
0
!n!
n
n!
n
 A
n

n


1

A
n< br>

n
2!

3!


1< br>
n!


n!


1
2!

1
3!




 1

n

1

n!




n2



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

Tn
n
nT
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
n
nT
n 1


1


证明：由上面已证明的全错位排列数通项公式可知：
右边
n

n1
!


1

1



1

n1

1

n

2!3!

n1

!




1



n!


1

1




1

n1

1< br>
n
n!

2!3!

n1

!




1

n!



n!

n

1

2!

1
3!




1


1

n!



左边
所以
T
n
n
nT
n1


1

。

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

3