不错-排列组合问题之全错位排列问题

排列组合问题之全错位排列问题（共3页）1排列组合问题之全错位排列问题（一个通项公式和两个递推关系）一、问题引入：问题1、4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有多少种？问题2、将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有多少种不同的放法？这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题。问题3、五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有多少种？解析：可以分类解决：第一类，所有同学都不坐自己原来的位置；第二类，恰有一位同学坐自己原来的位置；第三类，恰有两位同学坐自己原来的位置。对于第一类，就是全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题。设n个元素全错位排列的排列数为nT，则对于问题3，第一类全错位排列的排列数为5T；第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第二类的排列数为45T；第三类先确定两个排原位的同学，有2510C种可能，其余三个同学全错位排列，所以第三类的排列数为310T，因此问题3的答案为：543510109TTT。由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法。二、全错位排列数的递推关系式之一：121nnnTnTT3n①定义：一般地，设n个编号为1、2、3、…、i、…、j、…、n的不同元素1a、2a、3a、…、ia、…、ja、…、na，排成一排，且每个元素均不排在与其编号相同的位置，这样的全错位排列数为nT，则21T；32T；121nnnTnTT，3n。②递推关系的确立：显然当1n、2时，有10T，21T。当3n时，在n个不同元素中任取一个元素ia不排在与其编号相对应的i位，必排在剩下1n个位置之一，所以ia有1n种排法。对ia每一种排法，如ia排在j位，对应j位的元素ja的排位总有两种情况：第一种情况：ja恰好排在i位上。此时，ia排在j位，ja排在i位，元素ia，ja排位已定。还剩2n个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为2n个元素全错位排列数，应有2nT种。第二种情况：ja不排在i位上。此时，ia仍排在j位，ja不排在i位，则ja有1n个位置可排。除ia外，还有1n个元素，每个元素均有一个不能排的位置，问题就转化为1nn个元素全错位排列数，应有1nT种。由乘法原理和加法原理可得：121nnnTnTT，3n。利用此递推关系可以分别算出49T，544T。排列组合问题之全错位排列问题（共3页）2问题3的答案为：4459102109。三、全错位排列数的通项公式之一：Tn=n!12!-13!+...+-1()n×1n!éëêùûú2n㈠探索：规定01nAnN，试计算以下各式的值：①210444AAA；②32105555AAAA；③4321066666AAAAA。很容易计算三式的值依次为9，44，265。而这与利用上面的递推关系式得到的4T，5T，6T刚好吻合。即4T210444AAA；5T32105555AAAA；6T4321066666AAAAA。㈡猜想：根据上面的探索，我们可以猜想n个元素全错位排列数为Tn=Ann-2-Ann-3+...+-1()nAn02n为了更容易看清其本质，我们对这个式子进行变形，得到：Tn=Ann-2-Ann-3+...+-1()nAn0=n!2!-n!3!+...+-1()nn!n!=n!12!-13!+...+-1()n×1n!éëêùûú。㈢证明（数学归纳法）：当2n，3时，式显然成立。假设nk，1k时，式成立。则当1nk时，由上面的递推关系式可得：11kkkTkTT=kk!12!-13!+...+-1()k1k!éëêùûú+k-1()!12!-13!+...+-1()k-11k-1()!éëêêùûúúìíïîïüýïþï=kk-1()!k12!-13!+...+-1()k1k!éëêùûú+12!-13!+...+-1()k-11k-1()!éëêêùûúúìíïîïüýïþï=k!k+12!-k+13!+...+-1()k-1k+1k-1()!+k-1()k1k!éëêêùûúú=k!k+12!-k+13!+...+-1()k-1k+1k-1()!+k+1()-1()k1k!--1()k1k!éëêêùûúú=k!k+12!-k+13!+...+-1()k-1k+1k-1()!+k+1()-1()k1k!--1()kk+1k+1()!éëêêùûúú=k!k+12!-k+13!+...+-1()k-1k+1k-1()!+k+1()-1()k1k!+-1()k+1k+1k+1()!éëêêùûúú排列组合问题之全错位排列问题（共3页）3=k+1()!12!-13!+...+-1()k-11k-1()!+-1()k1k!+-1()k+11k+1()!éëêêùûúú所以，当1nk时，式也成立。由以上过程可知n个元素全错位排列的排列数为：Tn=Ann-2-Ann-3+...+-1()nAn0=n!2!-n!3!+...+-1()nn!n!=n!12!-13!+...+-1()n×1n!éëêùûú2n四、全错位排列数的递推关系式之二：11nnnTnT由21T，32T，49T，544T，6265T可得：3231TT；4341TT；5451TT；6561TT于是猜想：11nnnTnT证明：由上面已证明的全错位排列数通项公式可知：右边=nn-1()!12!-13!+...+-1()n-1×1n-1()!éëêêùûúú+-1()n=n!12!-13!+...+-1()n-1×1n-1()!éëêêùûúú+-1()nn!n!=n!12!-13!+...+-1()n×1n!éëêùûú=左边所以11nnnTnT。