关于错位排列问题的探讨

与全错位排列数公式有关的探索、猜想及证明214431江苏省江阴高级中学凌世春关键词：全错位排列，全错位排列数的通项公式，全错位排列数的递推关系式一．生活中的错位排列问题先看题一4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有种.题二将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有种不同的放法.这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题.再看题三五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有种.题三可以分类解决：第一类，所有同学都不坐自己原来的位置；第二类，恰有一位同学坐自己原来的位置；第三类，恰有两位同学坐自己原来的位置.对于第一类，就是上面讲的全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题.设n个元素全错位排列的排列数为Tn，则对于题三，第一类排列数为T5，第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第二类的排列数为5T4，第三类先确定两个排原位的同学，有25C=10种，所以第三类的排列数为10T3，因此题三的答案为：T5+5T4+10T3.由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法.二．关于全错位排列数的一个递推关系式1.一般地，设n个编号为1、2、3、…、i、…、j、…、n的不同元素a1、a2、a3、…、ai、…、aj、…、an，排在一排，且每个元素均不排在与其编号相同的位置，这样的全错位排列数为Tn，则T2=1，T3=2，Tn=(n-1)(Tn-1+Tn-2)，（n≥3）.2.递推关系的确立显然对于n=1，2时有T1=0，T2=1.当n≥3时，在n个不同元素中任取一个元素ai不排在与其编号相对应的i位，必排在剩下n-1个位置之一，所以ai有n-1种排法.对ai每一种排法，如ai排在j位，对应j位的元素aj的排位总有两种情况：第一种情况：aj恰好排在i位上，如表（1）123…i…j…najai表（1）此时，ai排在j位，aj排在i位，元素ai，aj排位已定，还剩n-2个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为n-2个元素全错位排列数，应有Tn-2种；第二种情况：aj不排在i位上，如表（2）123…i…j…nai表（2）此时，ai仍排在j位，aj不排在i位，则aj有n-1个位置可排，除ai外，还有n-1个元素，每个元素均有一个不能排的位置，问题就转化为n-1个元素全错位排列，排列数为Tn-1，由乘法原理和加法原理可得：Tn=(n-1)(Tn-1+Tn-2)，（n≥3）.利用此递推关系可以分别算出T4=9，T5=44，所以题三的答案为44+5×9+10×2=109.三．关于全错位排列数的一个通项公式1.探索规定0nA=1（n∈N*），试计算以下各式的值：（1）210444AAA；（2）32105555AAAA；（3）4321066666AAAAA.很容易计算三式的值依次为9，44，265.而这与利用上面的递推关系式得到的T4，T5，T6刚好吻合，即T4=210444AAA；T5=32105555AAAA；T6=4321066666AAAAA.2.猜想根据上面的探索，我们可以猜想n个元素全错位排列的排列数为Tn=230(1)nnnnnnAAA（n≥2）（*）为了更容易看清其本质，我们对这个式子进行变形，得到：Tn=230(1)nnnnnnAAA=!!!(1)2!3!!nnnnn=111![(1)]2!3!!nnn3.证明（数学归纳法）n=2，3时（*）式显然成立；假设n=k，k-1时（*）式成立，则当n=k+1时，有上面的递推关系式可得：Tk+1=k(Tk+Tk-1)=k{111![(1)]2!3!!kkk+1111(1)![(1)]2!3!(1)!kkk}aj不排i位=k·(k-1)!·{111[(1)]2!3!!kkk+1111[(1)]2!3!(1)!kk}=k!·[1111(1)2!3!(1)!kkkkk+k·1(1)!kk]=k!·[1111(1)2!3!(1)!kkkkk+（k+1）·1(1)!kk1(1)!kk]=k!·[1111(1)2!3!(1)!kkkkk+（k+1）·1(1)!kk1(1)(1)!kkk]=k!·[1111(1)2!3!(1)!kkkkk+（k+1）·1(1)!kk11(1)(1)!kkk]=(k+1)!·[1111(1)2!3!(1)!kk+1(1)!kk11(1)(1)!kk].∴n=k+1时（*）式也成立.由以上过程可知n个元素全错位排列的排列数为：Tn=230(1)nnnnnnAAA=!!!(1)2!3!!nnnnn=111![(1)]2!3!!nnn（n≥2）.四.关于全错位排列数的另一个递推关系式由T2=1，T3=2，T4=9，T5=44，T6=265可得：T3=3T2－1；T4=4T3+1；T5=5T4－1；T6=6T5+1.于是猜想Tn=nTn-1+(1)n.证明：由上面已证明的全错位排列数公式可知右边=n·1111(1)![(1)]2!3!(1)!nnn+(1)n=n!1111[(1)]2!3!(1)!nn+(1)n·!!nn=111![(1)]2!3!!nnn=左边.所以Tn=nTn-1+(1)n.五.综述在解决排列组合问题时，经常涉及到全错位或部分错位的排列问题，在元素不是很多时，我们可以通过分类讨论的方案，对问题进行讨论，但当元素较多时讨论起来非常麻烦，所以掌握了全错位排列数的一个通项公式和两个递推关系式，对我们解决这一类问题将带来很大的方便.参考书目：李宇襄编著《组合数学》，北京师范大学出版社出版.