错排问题

castelu

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

这个规律是:如图

kuing

呵，可以用递推关系或容斥原理进行证明的。

appletree444

很经典的一道题目，呵呵。

ccmmjj

下回看就没

ccmmjj

下回看就没