排列组合—错位重排问题

【导读】华图南充公务员考试网同步未知发布：排列组合—错位重排问题,详细信息请阅读下文!如有疑问请加【2020南充考试交流群汇总】 ，更多资讯请关注南充华图微信公众号(huatu_v ),南充公务员/事业单位/教师培训咨询微信客服：点击查看,微博：@南充华图

排列组合—错位重排问题
                                               华图教育四川分校  何彦锋

排列组合问题一直是广大考生备考行测数量关系部分的一个难点，而其中的错位排列问题是更是一个非常古老非常棘手的问题，贝努利、欧拉等数学家都曾经研究过。错位排列问题虽然有难度，但是也有快速解决之道。需要总结规律，熟记结论，才能在临考时，快速准确抓住解题突破口。为帮助广大考生攻克这一难关，下面笔者为大家详细解读错位排列问题。
一、问题导入
根据需要进行错位排列的元素是否用完，可将错位排列问题分为：全错位排列问题和部分错位排列问题。下面先给出两道生活中的错位排列题目，让广大考生有一个直观感觉：
【例1】有4名同学各写了一张贺卡，先全部收集起来，然后每人从中拿出一张贺卡，要求每个人都不拿自己的贺卡，则四张贺卡的不同分配方式共有      种。
【例2】将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同（即1不放1，2不放2，3不放3，4不放4，也就是说4个全部放错），则共有      种不同的放法。
上面这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题。
再看下面的这题目：
【例3】五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有       种。
这道题可以分类解决：第一类，所有同学都不坐自己原来的位置；第二类，恰有一位同学坐自己原来的位置；第三类，恰有两位同学坐自己原来的位置。
对于第一类，就是上面讲的全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题。
设n个元素全错位排列的排列数为D_n，则对于题三，第一类排列数为D₅，第二类先确定一个排在原来位置的同学有5种可能，其余四个同学全错位排列，所以第二类的排列数为5D₄，第三类先确定两个排在原位的同学，有=10种，所以第三类的排列数为10D₃，因此题三的答案为：D₅+5D₄+10D₃。
可见，生活中类似于这样的问题非常多，而且“部分错位排列问题”也需要转化为“全错位排列问题”来求解，所以我们有必要研究一下关于“全错位排列问题”的解决方法。
二、递推关系式
1. 递推关系式
一般地，设n个编号为1、2、3、… 、i、…、j、…、n的不同元素a₁、a₂、a₃、…、a_i、…、a_j、…、a_n，排在一排，且每个元素均不排在与其编号相同的位置，这样的全错位排列数为Dn，则D₁=0，D₂=1，D₃=2，D_n=（n-1）（D_n-1+D_n-2）（n≥3）。
2. 递推关系式的证明
显然对于n=1、2时，有D₁=0，D₂=1。
当n≥3时，在n个不同元素中任取一个元素a_i不排在与其编号相对应的i位，必排在剩下n-1个位置之一，所以a_i有n-1种排法。
对a_i每一种排法，如a_i排在j位，对应j位的元素a_j的排位共有两种情况：
第一种情况：aj恰好排在i位上，此时，ai排在j位，aj排在i位，元素a_i，a_j排位已定，还剩n-2个元素，它们的排位问题就转化为n-2个元素全错位排列数，应有D_n-2种；
第二种情况：a_j不排在i位上，此时，a_i仍排在j位，a_j不排在i位，即此时a_j有一个不能排的位置，也就是说，除了a_i外，还有n-1个元素，每个元素均有一个不能排的位置，问题就可转化为n-1个元素得全错位排列，排列数为D_n-1，由乘法原理和加法原理可得：D_n=（n-1）（D_n-1+D_n-2）（n≥3）。
由此递推关系，可得：D₄=9，D₅=44，D₆=265……
三、知识补充
1. 全错位排列数的一个通项公式：
D_n=（n≥2）
==（n≥2）
2. 全错位排列数的另一个递推关系式：
由D₁=0，D₂=1，D₃=2，D₄=9，D₅=44，D₆=265可得：
D₂=2D₁+1；
D₃=3D₂-1；
D₄=4D₃+1；
D₅=5D₄-1；
D₆=6D₅+1；
……
D_n=nD_n-1+。
四、例题分析
【例1】（2014-北京）相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求所有车都不得停在原来的车位中，则一共有多少中不同的停放方式？（    ）
A. 9B. 12
C. 14D. 16
【答案】A
【解析】全错位排列问题。D₁=0，D₂=1，D₃=2，D₄=9，……，D_n=nD_n-1+，所以，4辆车一共有D₄=9种停放方式。因此，本题答案选择A选项。
【例2】（2011-浙江）四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法？（    ）
A. 6种B. 9种
C. 12种D. 15种
【答案】B
【解析】全错位排列问题。记住数字：D₁=0，D₂=1，D₃=2，D₄=9，……，D_n=nD_n-1+。可知，4个元素对应的全错位排列数为D₄=9。因此，本题答案选择B选项。
【例3】（2015-四川-泸州）a、b、c、d四台电脑摆放一排，从左往右数，如果a不摆在第一个位置上，b不摆在第二个位置上，c不摆在第三个位置上，d不摆在第四个位置上，那么不同的摆法共有（    ）种。
A. 9B. 10
C. 11D. 12
【答案】A
【解析】全错位排列问题。记住数字：D₁=0，D₂=1，D₃=2，D₄=9，……，D_n=nD_n-1+。可知，4个元素对应的全错位排列数为D₄=9。因此，本题答案选择A选项。
【例4】五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有       种。
【答案】109.
【解析】部分错位排列问题。本题可分三类求解：第一类，所有同学都不坐自己原来的位置，即5个元素的全错位排列，排列数为D₅=44；第二类，恰有一位同学坐自己原来的位置，其余4个同学进行全错位排列，排列数为5D₄=5×9=45；第三类，恰有两位同学坐自己原来的位置，其余3个同学进行全错位排列，排列数为×D₃=10×D₃=10×2=20。所以本题答案为：D₅+5D₄+10D₃=44+45+20=109种。
综上，对于全错位或部分错位排列问题，当元素不是很多时，我们可以通过分类讨论的方案，对问题进行讨论求解，但当元素较多时讨论起来非常麻烦，所以熟悉全错位排列数的通项公式和递推关系式，对我们解决这一类问题能带来很大的方便。同时，建议广大考生记住下面这几个数字：0，1，2，9，44，265，这也是一个有规律的数字推理题，递推关系式为：①D_n=(n-1)(D_n-1+D_n-2)（n≥3）；②D_n=nD_n-1+（n≥2）。
 
 

扫码关注【南充华图教育】

及时获取近期招考信息与备考资料

（编辑：四川华图）