mp3播放顺序-法国波尔多葡萄酒

排列组合专题之错排问题
1993年的全国高考试题一改以前数学高考“以知识立意” 命题思路，开始明确提出“以
能力立意”，这是数学高考改革的一项重要举措，高考数学命题更加注重了 对能力和素质的
考查，试题设计增加了应用性和能力型题目，其中的“贺卡问题”就属于这方面的一道好 题。
贺卡问题：同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送的贺
年卡 ，则四张不同的贺年卡不同的分配方式有：
A、6种 B、9种 C、11种 D、23种 < br>这个问题的情境新颖，无法直接套用公式、法则，主要考查分类或分步计数原理或从
反面考虑（排 除法）的思想方法，考查分析问题与解决问题的能力，本题以组合数学中著名
的“错排问题”为背景，用 贴近学生身边生活的“贺卡”来设计问题，显得较恰当。其实，
实际生活中的“错排问题”有多种多样， 如信封中装错信件或坐错座位等等。
错排问题：有n个正整数1，2，3，……n，将这n个正整数重 新排列，使其中的每一
个数都不在原来的位置上，这种排列称为正整数1，2，3，……n的错排，问这 n个正整数
的排个数是多少？
设这n个正整数的错排个数为a
n
，为了探求 a
n
的表达式，我们先从最特殊的情形入手。
当n=1时，由于只有一个数1，不可能有错排，所以a
1
=0.
当n=2时，两个数的错排是唯一的，所以a
2
=1.
当n=3时，三个数 1、2、3只有2、3、1和3、1、2两种错排，所以a
3
=2.
当n=4时，四 个数1、2、3、4的错排有：2、1、4、3；2、3、4、1；2、4、1、3；3、
1、4、2； 3、4、2、1；4、1、2、3；4、3、1、2；4、3、2、1，共有9种错排，所以a
4
=9.
刚才提到的93年高考试题——贺卡问题，实际上求的就是a
4
等于多少？
上面使用的是枚举法，当n较大时，这种方法是很麻烦的、难以解决问题的，必须另
辟蹊径，现 在考虑用排除法求出1、2、3、4这四个正整数的错排的种数，从中摸索出规律。
对于四个正整数1、2、3、4，这四个数的全排列数为4！。
有一个数不错排的情况应排除 ，由于1排在第1位的有3！种，2排在第2位的有3！
种，……4排在第4位的有3！种，所以共应排 除4×3！种。
然而在排除有一个数不错排的情况时，把同时有两个数不错排的情况也排除了，应予< br>以补上，由于1、2分别排在第1、第2位上的情况共有2！种，同理1、3分别排在第1、
第3 位上的情况也有2！种，……，这四个数中同时有两个数不错排的情况共有种，所以应
补上
C< br>4
2!
2
4!
种。在补上同时有两个数不错排的情况时，把同时有 三个数不错排的情况
2!
1
也补上了，应予以排除，四个数中有1、2、3不错排，1 、2、4不错排，1、3、4不错排和
2、3、4不错排共
C
4
种情况，所以 应排除
C
4
1!
1
4!
种。
3!
在 排除同时有三个数不错排的情况时，把同时有四个数不错排的情况也排除了，所以
应补上同时有四个数不 错排的情况仅1、2、3、4这一种。
4!4!4!4!4!
19.

2!3!2!3!4!
4!4!4!3!3!2!
由
a
4
 
以及
a
3
2
，
a
2
1，我们猜想n个正整数1、2、3、
2!3!4!2!3!2!
综上所述，
a4
4!43!
4、……、n的错排的种数a
n
的表达式为an
=

(1)
k2
n
k
n!
，下 面我们来证明这个表达式。
k!
一般来说，正整数1、2、3、……、n的全排列有n！种， 其中第k位是k的排列有（n-1）！，

当k取1、2、3、……、n时，共有n×（n -1）！种排列，由于是错排，这些排列应排除，
但是此时把同时有两个数不错排的排列多排除了一次， 应补上；在补上时，把同时有三个数
不错排的排列多补上了一次，应排除；……；继续这一过程，得到错 排的排列种数为
a
n

n!n!n!
(1)
n
，
2!3!n!
n
n!n!n!n!n!
k
n!
n
n !
n
n!
，即
a
n


(1)
.
a
n
n!(1)(1)
k!1!2!3!n!2!3!n!
k2
计数是一种常见的数学问题，涉及计数问题的另一种 思路是运用递推方法，应该说，
利用递推方法是解决计数问题的重要方法，下面我们再用递推关系求a< br>n
的值。
由题意a
1
=0，a
2
=1，当n≥3时 ，在错排中n必不在第n位，设n放在第k位上（1≤k
≤n-1），则第n位上有两种可能：
（1）如果第n位上不是k，那么把第n位看作第k位，将n以外的n－1个数进行错排，
错排个数是 a
n-1
；
（2）如果第n位上是k，那么除n和k以外的n－2个数的错排是a
n-2
， 所以n在第k位上的错排数共有a
n-1
＋a
n-2
，由于k可取1、2 、3、4、……、n－1共n－1种
取法，所以n个数的错排个数
a
n
(n 1)(a
n1
a
n2
)
，其中n≥3.
下面我们来求数列{a
n
}的通项。
为了方便起见，设
a
k
k!b
k
(k1,2,,n)
,
则
b
1
0,b
2

1
,
当n3时,n!b
n(n1)(n1)!b
n1
(n1)!b
n2
,

2
即：
nb
n
(n1)b
n1
b
n2
,

于是有
b
n
b
n1
< br>1
(b
n1
b
n2
)(
1
)(
1
)(
1
)(b
2
b
1
)(1)
n
1
，
nnn13n!
从而可求
bn
，所以
a
n

n!n!n!
(1)< br>n
。
2!3!n!