全错位排列(4页).doc

-一、问题导入【引例1】唐僧、孙悟空、猪八戒、沙和尚4人在某公司不同岗位任职，现在需要调换岗位，要求每个人都不能在自己原来的岗位，则共有 种不同的安排方法。【引例2】有4名同学各写了一张贺卡，先全部收集起来，然后每人从中拿出一张贺卡，要求每个人都不拿自己的贺卡，则四张贺卡的不同分配方式共有 种。【引例3】将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同(即1不放1，2不放2，3不放3，4不放4，也就是说4个全部放错)，则共有 种不同的放法。不难发现，以上三个引例都是同一类问题，答案是多少呢?下面用枚举法给大家答案：假设原来顺序：A、B、C、D枚举的时候注意按照一定规律进行，如果看成1、2、3、4号位置，那么第一步A可以放2、3、4号位置中的任意一个，第二步把B的位置确定，第三步确定C和D的位置：第1种错位排列：B、A、D、C(A在2位，B在1位，C、D位置就唯一确定了);第2种错位排列：D、A、B、C(A在2位，B在3位，C、D位置就唯一确定了);第3种错位排列：C、A、D、B(A在2位，B在4位，C、D位置就唯一确定了);第4种错位排列：B、D、A、C(A在3位，B在1位，C、D位置就唯一确定了);第5种错位排列：C、D、A、B(A在3位，B在4位，C、D位置可以是1、2);第6种错位排列：D、C、A、B(A在3位，B在4位，C、D位置也可以是2、1);第7种错位排列：B、C、D、A(A在4位，B在1位，C、D位置就唯一确定了);第8种错位排列：C、D、B、A(A在4位，B在3位，C、D位置可以是1、2);第9种错位排列：D、C、B、A(A在4位，B在3位，C、D位置也可以是2、1)。可见，4个元素的错位排列一共有9种。即以上三道引例的答案都是9种。二、理论推导其实，上面引例涉及的三个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把带这种限制条件的排列问题叫做全错位排列问题。它是一个非常古老的数学问题，贝努利、欧拉等数学家都曾经研究过。这类问题虽然有难度，但我们解题是有快速破解的“窍门”的。且看下面详细解读：我们将n个元素的全错位排列数记做Dn。由于1个元素没有错位排列，因此D1=0。2个元素时可以相互交换一下位置，即有1种错位排列，则D2=1。当n3时，在n个不同元素中任取一个元素ai不排在与其编号相对应的i位，必排在剩下n-1个位置之一，所以ai有n-1种排法。即第一步排ai，有n-1种。第二步：排ai所占位置对应的元素。对ai每一种排法，如ai排在j位，对应j位的元素aj的排位共有两类情况：第一类情况：aj恰好排在i位上，此时，ai排在j位，aj排在i位，元素ai、aj排位已定，还剩n-2个元素，它们的排位问题就转化为n-2个元素全错位排列数，应有Dn-2种;第二类情况：aj不排在i位上，此时，ai仍排在j位，aj不排在i位，相当于aj也有一个不能排的位置，也就是说，除了ai外，其他n-1个元素，每个元素均有一个不能排的位置，那么问题就可转化为n-1个元素的全错位排列问题，排列数为Dn-1。即第二步排aj有(Dn-1+Dn-2)种。根据乘法原理，两步相乘可得：Dn=(n-1)(Dn-1+Dn-2)(n3)。也就是说我们得到了全错位排列数的一个递推公式，对于这个公式，只有我们知道第1项D1和第2项D2的值，就可以推出后面所以项的值。例如：D1=0，D2=1，D3=2(D2+D1)=2(1+0)=2种，D4=3(D3+D2)=3(2+1)=9种，D5=4(D4+D3)=4(9+2)=44种，D6=5(D5+D4)=5(44+9)=265种记住结论：D1=0，D2=1，D3=2，D4=9，D5=44，D6=265Dn=(n-1)(Dn-1+Dn-2)(n3)。三、速记1个元素时没有错位排列，D1=0;2个元素错位排列有1种，D2=1，速记：D2=2D1+1;3个元素错位排列有2种，D3=2，速记：D3=3D2-1;4个元素错位排列有9种，D4=9，速记：D4=4D3+1;5个元素错位排列有44种，D5=44，速记：D5=5D4-1;6个元素错位排列有265种，D6=265，速记：D6=6D5+1;n个元素错位排列有Dn种，速记：Dn=nDn-1+。四、考场秒杀【例1】(2014北京)相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求所有车都不得停在原来的车位中，则一共有多少种不同的停放方式?( )A. 9 B. 12C. 14 D. 16【答案】A【解析】全错位排列问题。记住数字：D4=9，D5=44，Dn=nDn-1+，所以，4辆车一共有D4=9种停放方式。因此，本题答案选择A选项。【例2】(2011浙江)四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法?( )A. 6种 B. 9种C. 12种 D. 15种【答案】B【解析】全错位排列问题。记住数字：D4=9，D5=44，Dn=nDn-1+。可知，4个元素对应的全错位排列数为D4=9。因此，本题答案选择B选项。【例3】(2015四川泸州事业单位)a、b、c、d四台电脑摆放一排，从左往右数，如果a不摆在第一个位置上，b不摆在第二个位置上，c不摆在第三个位置上，d不摆在第四个位置上，那么不同的摆法共有( )种。A. 9 B. 10C. 11 D. 12【答案】A【解析】全错位排列问题。记住数字：D4=9，D5=44，Dn=nDn-1+。可知，4个元素对应的全错位排列数为D4=9。因此，本题答案选择A选项。【例4】(2015山东)某单位从下属的5个科室各抽调了一名工作人员，交流到其他科室。若每个科室只能接收一个人的话，有多少种不同的人员安排方式?( )A. 120 B. 78C. 44 D. 24【答案】C【解析】全错位排列问题。记住数字：D4=9，D5=44，Dn=nDn-1+。可知，5个元素对应的全错位排列数为D5=44。因此，本题答案选择C选项。例1：(2011年浙江省考真题55题)四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法？A.6种              B.9种              C.12种             D.15种【答案与解析】B。此题为全错位排列试题。根据全错位排列公式“An(An2A n1)×(n1)(其中，n3，且A 10，A 21)”，可知，当n4时，共有9种尝法。例2：(2010年某省考试真题)五个瓶子都贴了标签，其中恰好贴错了三个，则错的可能情况共有多少种？A.5                B. 10               C. 15               D. 20【答案与解析】D。做此类题目时通常分为两步：第一步，从五个瓶子中选出三个，共有C(3，5)10种选法；第二步，将三个瓶子全部贴错，根据上表有2种贴法。则恰好贴错三个瓶子的情况有10×220种。-第 4 页-