7、排列组合问题

排列组合问题之全错位排列问题(一个通项公式和两个递推关系)一、 问题引入：问题1、4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有多少种？问题2、将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有多少种不同的放法？这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题。问题3、五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有多少种？解析：可以分类解决：第一类，所有同学都不坐自己原来的位置；第二类，恰有一位同学坐自己原来的位置；第三类，恰有两位同学坐自己原来的位置。对于第一类，就是全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题。设n个元素全错位排列的排列数为孔，则对于问题3，第一类全错位排列的排列数为T;第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第5二类的排列数为5T；第三类先确定两个排原位的同学，有C；=10种可能，其余三个同学全错位排列，所以第三类的排列数为10T，因此问题3的答案为：T+5T+10T=109。5 4 3由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法。二、 全错位排列数的递推关系式之一：T=(n—1)(T+T) (n>3)定义：一般地，设n个编号为L2、3、…、，、•••、_/、•••、n的不同元素a1、a2、％、…、a.、…、a.、…、a，排成一排，且每个元素均不排在与其编号相同的位置，这样的全错位排列数为T，贝T=1；T=2；T=(n—1)(T+T)，(n>3)。n 2 3 n n—1n—2递推关系的确立：显然当n=1、2时，有T=0，T=1o当n>3时，在n个不同元素中任取一个元素a,不排在与其编号相对应的i位，必排在剩下n—1个位置之一，所以a有n—1种排法。i对a〔每一种排法，如a〔排在j位，对应j位的元素a.的排位总有两种情况：第一种情况：a恰好排在i位上。此时，a排在j位，a排在i位，元素a，a排位j I j Ij已定。还剩n—2个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为n—2个元素全错位排列数，应有T—2种。第二种情况：a不排在，"位上。此时，a仍排在j位，a不排在i位，则a有n—1个j I j j位置可排。除a〔外，还有n—1个元素，每个元素均有一个不能排的位置，问题就转化为n—1n个元素全错位排列数，应有I种。由乘法原理和加法原理可得:T=(n—1)(T1+TJ,(n>3)。利用此递推关系可以分别算出匕=9，T=44。"

问题3的答案为：44+5x9+10x2=109o三、全错位排列数的通项公式之一:TOC\o"1-5"\h\z11 ]T—n!———+・..+(-1)，,— (jt>2)〃I2!3! nl]㈠探索：规定Ao=1CzgN*),试计算以下各式的值：①A2—Ai+Ao；②出一人2+Ai—Ao；③山一人3+A2—Ai+Ao。4 4 5 5 5 5 6 6 6 6 6很容易计算三式的值依次为9,44,265o而这与利用上面的递推关系式得到的T,4T,T刚好吻合。即6T=A2-Ai+Ao；T=A3—A2+Ai—Ao；T= +A2-Ai+Ao04 4445 5555 6 66666㈡猜想：根据上面的探索，我们可以猜想〃个元素全错位排列数为T= —A3+•••+(-1)〃Ao (n>2) (*)nn n n为了更容易看清其本质，我们对这个式子进行变形，得到：T-An-2-An-3H (-1)〃 =—-—H —nnn 〃 2!3! fl!=n\—-—H (-I》」o_2!3! n\_㈢证明(数学归纳法)：当〃=2,3时，(*)式显然成立。假设〃=*,上一1时，(*)式成立。则当n=k+l时，由上面的递推关系式可得：T=k(T+T)k+1 kk-1=k\k\-1-1+..•+(-!>—+Q-1)! +..+ ,1.>|_2!3! 们」2!3! U-1)!=上。-1)»1-1+...+(-!>£+2!3! k\=k\1=k\k\=k\=k\2!2!k+1IT=k\=k\2!2!k+1IT=k!工一史+..•+(—1)1吕+。+1)(一1)」+(一1)3危2! 3! U-1)! k\U+l,二Q+1)!-L-1+...+ z1x+(-1>—+(—)+1z1A2!3! U-1)!k\U+l)!j所以，当n=k+1时，(*)式也成立。由以上过程可知〃个元素全错位排列的排列数为：T=An-2—An-3H+(-1)nAo=―--―-H+(-1)n―-nnn n2!3! n!="12!-3!+…A"•J (n-2)四、全错位排列数的递推关系式之二：T=nT+(-1)〃由T=1,T=2,T=9,T=44,T=265可得:T=3T—1；T=4T+1；T=5T—1；T=6T+13 2 4 3 5 4 6 5于是猜想：气=nT,]+(-1)n证明：由上面已证明的全错位排列数通项公式可知：右边=n(n-1