每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题.1．错位排列问题例1.4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有种.例2.将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有种不同的放法.这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题.例3.五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有种.解析：可以分类解决：第一类，所有同学都不坐自己原来的位置；第二类，恰有一位同学坐自己原来的位置；第三类，恰有两位同学坐自己原来的位置.对于第一类，就是上面讲的全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题.设n个元素全错位排列的排列数为Tn，则对于例3，第一类排列数为T5，第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第二类的排列数为5T4，第三类先确定两个排原位的同学，有C5=10种，所以第三类的排列数为10T3，因此例3的答案为：T5+5T4+10T3=109.由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法.2．关于全错位排列数的一个递推关系式：Tn=(n-1)(Tn-1+Tn-2)，（n≥3）(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…iaj表（1）此时，ai排在j位，aj排在i位，元素ai，aj排位已定，还剩n-2个元素，每个元素均…jai
…n2有一个不能排的位置，它们的排位问题就转化为n-2个元素全错位排列数，应有Tn-2种；第二种情况：aj不排在i位上，如表（2）123…i…jaiaj不排i位表（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.3．关于全错位排列数的一个通项公式：Tn=n![(1).探索规定An=1（n∈N*），试计算以下各式的值：（1）A4A4A4；（2）A5A5A5A5；（3）A6A6A6A6A6.很容易计算三式的值依次为9，44，265.而这与利用上面的递推关系式得到的T4，T5，T6刚好吻合，即T4=A4A4A4；T5=A5A5A5A5；T6=A6A6A6A6A6.(2).猜想根据上面的探索，我们可以猜想n个元素全错位排列的排列数为Tn=AnTn=An
=n2
n30
An(1)nAn（n≥2）n30An(1)nAn4
3
2
1
0
3
2
1
0
2
1
0
4
3
2
1
0
3
2
1
0
2
1
0
0
…n111
(1)n]（n≥2）.2!3!n!（*）为了更容易看清其本质，我们对这个式子进行变形，得到：n2
n!n!n!111
(1)n=n![(1)n]2!3!n!2!3!n!(3).证明（数学归纳法）n=2，3时（*）式显然成立；假设n=k，k-1时（*）式成立，则当n=k+1时，有上面的递推关系式可得：Tk+1=k(Tk+Tk-1)=k{k![
111111
(1)k]+(k1)![(1)k1]}2!3!k!2!3!(k1)!=k·(k-1)!·{k[=k!·[=k!·[=k!·[=k!·[111111(1)k]+[(1)k1]}2!3!k!2!3!(k1)!k1k1k1k1+k·(1)](1)k1
k!2!3!(k1)!1k1k1k1k1(1)k]+（k+1）·(1)(1)k1
k!k!2!3!(k1)!k1k1k1k1k1+（k+1）·(1)](1)k1(1)kk!2!3!(k1)!(k1)!k1k1k1k1k1+（k+1）·(1)](1)k1(1)k1k!2!3!(k1)!(k1)!1111k1+(1)].(1)k1(1)k1
k!2!3!(k1)!(k1)!=(k+1)!·[∴n=k+1时（*）式也成立.由以上过程可知n个元素全错位排列的排列数为：Tn=An
n2
n30
An(1)nAn=n!n!n!
(1)n2!3!n!=n![
111
(1)n]（n≥2）.2!3!n!n
4.关于全错位排列数的另一个递推关系式：Tn=nTn-1+(1)
由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·(n1)![
=n![=n![
n
111
(1)n1]+(1)n2!3!(n1)!n!111(1)n1]+(1)n·n!2!3!(n1)!111
(1)n]=左边.2!3!n!n
所以Tn=nTn-1+(1).5.点评在解决排列组合问题时，经常涉及到全错位或部分错位的排列问题，在元素不是很多时，我们可以通过分类讨论的方案，对问题进行讨论，但当元素较多时讨论起来非常麻烦，所以掌握了全错位排列数的一个通项公式和两个递推关系式，对我们解决这一类问题将带来很大的方便.（三）利用隔板法巧解排列、组合题
隔板法是将相同的球放入不同的盒子，每盒放入球的个数不限，求不同方法种数的一种解题方法。利用隔板法能够巧解许多排列、组合问题。1.放球问题。例1、把8个相同的球放入4个不同的盒子，有多少种不同方法？解：取3块相同隔板，连同8个相同的小球排成一排，共11个位置。由隔板法知，在11个位置中任取3个位置排上隔板，共有C11种排法。3=C11311109
=165(种)321所以，把8个相同的球放入4个不同的盒子，有165种不同方法。点评：相同的球放入不同的盒子，每个盒子放球数不限，适合隔板法。隔板的块数要比盒子数少1。2.指标分配问题。例2、某校召开学生会议，要将10个学生代表名额，分配到某年级的6个班中，若每班至少1个名额，又有多少种不同分法？解：名额与名额是没有差别的，而班级与班级是有差别的，这样，把10相同的名额分配到6个不同的班级中，适合隔板法。将10个学生代表名额，分配到某年级的6个班中，每班至少1个名额，可分以下两步完成。第一步：每班先给1个名额，仅有1种给法；第二步：将剩余的4个名额分到这6个班里，由隔板法知，此时，有C9种不同分法。由分步计数原理知，共有C9种不同分法。C9=C9=54559876
=126（种）。4321答：某校召开学生会议，要将10个学生代表名额，分配到某年级的6个班中，若每班至少1个名额，有126种不同分法.点评：名额与名额是没有差别的，而班级与班级是有差别的，故适合隔板法。3.求n项展开式的项数。例3、求(x1x2x5)展开式中共有多少项？解：用10个相同的小球代表幂指数10,用5个标有x1、x2、…、x5的5个不同的盒子表示数x1、x2、…、x5，将10个相同的小球放入5个不同的盒子中，把标有xi（i=1,2,…,5）每个盒子得到的小球数ki（i=1，2，…，5;kiN），记作xi的ki次方。10这样，将10个相同的小球放入5个不同的盒子中的每一种放法，就对应着展开式中的每一项。由隔板法知，这样的放法共有C14种，故(x1x2x5)的展开式中共有C14项。4=C14410414131211
=1001（种）。432110所以，(x1x2x5)展开式中共有1001项。点评：准确理解隔板法的使用条件，是使用隔板法求(x1x2x5)展开式中的项数的理论依据。4.求n元一次方程组的非负整数解。例4、求方程x1+x2+…+x5=7的正整数解的个数。解：用7个相同的小球代表数7,用5个标有x1、x2、…、x5的5个不同的盒子表示未知数x1、x2、…、x5，要得到方程x1+x2+…+x5=7的正整数解的个数，可分以下两步完成。第一步：从7个相同的小球中任取5个放入5个不同的盒子中，仅有1种放法；第二步：把剩余的2个小球放入5个不同的盒中，由隔板法知，此时有C6种放法。由分步计数原理知，共有C6种不同放法。我们把标有xi（i=1,2,…,5）的每个盒子得到的小球数ki（i=1，2，…，5;kiN
4410），记作：xi=ki。这样，将7个相同的小球放入5个不同的盒子中的每一种放法，就对应着方程x1+x2+…+x5=7的每一组解（k1，k2，…，k5）。C64=C62=65
=15（个）21所以，方程x1+x2+…+x5=7的正整数解共有15个。点评：准确理解隔板法的使用条件，是使用隔板法求方程x1+x2+…+x5=7的非负（或正）整数解的个数的理论依据。
因篇幅问题不能全部显示，请点此查看更多更全内容