错排问题——研究性学习的一个典型案例

《错排问题——研究性学习的一个典型案例》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据2005年第44卷第10期数学通报47错排问题——研究性学习的一个典型案例张惠良(江苏省太仓高级中学215400)1993年的全国高考试题一改以前数学高考“以知识立意”命题思路，开始明确提出“以能力立意”，这是数学高考改革的一项重要举措，高考数学命题更加注重了对能力和素质的考查，试题设计增加了应用性和能力型题目，其中的“贺卡问题”就属于这方面的一道好题．贺卡问题：同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送的贺年卡，则四张不同的贺年卡不同的分配方式有A．6种B．9种C．11种D．23种这个问题情境新颖，无法直接套用公式、法则，主要

2、考查分类或分步计数原理或从反面考虑(排除法)的思想方法，考查分析问题与解决问题的能力．本题以组合数学中著名的“错排问题”为背景，用贴近学生身边生活的“贺卡”来设计问题，显得较恰当．其实，实际生活中的“错排问题”有多种多样，如信封中装错信件或坐错座位等等．错排问题：有凡个正整数1，2，3，⋯，17,，将这几个正整数重新排列，使其中的每一个数都不在原来的位置上，这种排列称为正整数1，2，3，⋯，n的错排，问这几个正整数的错排个数是多少?设这n个正整数的错排个数为％，为了探求a。的表达式，我们先从最特殊的情形人手．当／／,=1时，由于只有一个数1，不可能有错排

3、，所以a1=0．当凡=2时，两个数的错排是唯一的，所以∞：1．当n=3时，三个数1、2、3只有2、3、1和3、1、2两种错排，所以o，=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、1、2；3、4，2、1；4、1，2、3；4、3，1、2；4、3、2、1．共有9种错排，所以o。=9．刚才提到的93年高考试题——贺卡问题，实际上求的就是a。等于多少?上面使用的是枚举法，当／7,较大时，这种方法是很麻烦的、难以解决问题的，必须另辟蹊径，现在考虑用排除法求出1、2、3、4这四个正整数的错排的

4、种数，从中摸索出规律．对于四个正整数1、2、3、4，这四个数的全排列数为41．有一个数不错排的情况应排除，由于l排在第1位的有31种，2排在第2位的有31种，⋯，4排在第4位的有31种，所以共应排除4×31种．然而在排除有一个数不错排的情况时，把同时有两个数不错排的情况也排除了，应予以补上，由于1、2分别排在第1、第2位上的情况共有21种，同理1、3分别排在第1、第3位上的情况也有21种，⋯，这四个数中同时有两个数不错排的情况共有暖种，所以应补上碍×21=著种．在补上同时有两个数不错排的情况时，把同时有三个数不错排的情况也补上了，应予以排除，四个数中有1

5、、2、3不错排，1、2、4不错排，1、3、4不错排和2、3、4不错排共cj种情况，所以应排除cj×11=务种．在排除同时有三个数不错排的情况时，把同时有四个数不错排的情况也排除了，所以应补上同时有四个数不错排的情况仅1、2、3、4这一种．综上所述，。4：41—4×31+筹一等+l：等一彗+著以由a4=筹一彗+筹以及a3=2=碧一蚤，02=1=暑，我们猜想n个正整数1、2、3、4、⋯、凡的错排的种数％的表达式为％：∑(～1)‘等，下面我们来证明这个表达式．万方数据48数学通报2005年第44卷第10期一般说来，正整数1、2、3、⋯、n的全排列有n!种，其中

6、第七位是矗的排列有(n一1)!种，当矗取1、2、3、⋯、n时，共有n×(n一1)!种排列，由于是错排，这些排列应排除．但是此时把同时有两个数不错排的排列多排除了一次，应补上；在补上时，把同时有三个数不错排的排列多补上了一次，应排除；⋯⋯；继续这一过程，得到错排的排列种数为n。=nz一器+署一碧+⋯+c一，，“碧=筹一碧+n!一可+万一可r一+L-1厂可2万一可+⋯+(一1)“等，即an=∑k(一1)‘铸(1)=2事实上，用上述方法解题，就是反复考虑包含与排斥的情形，这当然使我们直接想到利用容斥原理来解决，这样做应当更干脆利索一些．现在我们考虑，几个元素的

7、全排列中，求每个元素都不在自己位置上的排列数．设Ai为数i在第i位上的全体排列，i=1，2，⋯，n，因数字i保持不动，所以lAl=(17,一1)!；i=1，2，⋯，n．同理有IAir]AiI=(n一2)!，(1≤i<，≤n)，⋯，IAi．nAi．n⋯nAiI=(n—r)!(1≤il

8、≤4⋯+(一1)7·∑AinAi．⋯nAil+⋯+1≤iJ