第六课时几类特殊的排列组合问题的解决技巧

第六课时几类特殊的排列组合问题的解决技巧（一）教学目标：掌握几类特殊的排列问题的解决技巧.教学重点：掌握“条件排列”、“集团排列”、“间隔排列”、“部分顺序排列”问题的解题技巧.教学难点：如何应用“技巧”解题．教学过程：【例析技巧】一.集团排列问题：部分元素必须安排在一起（相邻）的排列问题，称之为“集团排列”问题.解决这类问题，常用“捆绑法”，其方法是先排“集团”内部的元素，再把这个大“元素”与其它元素一起排列即可.例1若7位同学站成一排（1）甲、乙两同学必须相邻的排法共有多少种？（2）甲、乙和丙三个同学都相邻的排法共有多少种？（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？（4）甲、乙、丙三个同学必须站在一起，另外四个人也必须站在一起的排法有多少种？解：（1）先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）一起进行全排列有66A种方法；再将甲、乙两个同学“松绑”进行排列有22A种方法．所以这样的排法一共有62621440AA种.（2）方法同上，一共有55A33A720种.（3）解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有25A种方法；将剩下的4个元素进行全排列有44A种方法；最后将甲、乙两个同学“松绑”进行排列有22A种方法．所以这样的排法一共有25A44A22A960种方法.解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有255A种方法，所以，丙不能站在排头和排尾的排法有960)2(225566AAA种方法.解法三：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有14A种方法，再将其余的5个元素进行全排列共有55A种方法，最后将甲、乙两同学“松绑”，所以，这样的排法一共有14A55A22A960种方法．（4）将甲、乙、丙三个同学“捆绑”在一起看成一个元素，另外四个人“捆绑”在一起看成一个元素，时一共有2个元素，∴一共有排法种数：342342288AAA（种）说明：对于相邻问题，常用“捆绑法”（先捆后松）．二.间隔排列问题：部分元素不能安排在一起（间隔）的排列问题，称之为“间隔排列”问题.解决这类问题，常用“插空法”，其方法是先排不需要间隔的元素，再将需要间隔的元素通过插空的方式插进来即可.例2在一条南北方向的步行街同侧有8块广告牌，牌的底色可选用红、蓝两种颜色.若只要求相邻两块牌的底色不都为红色，则不同的配色方案共有（）A.55.B.56.C.46.D.45.解：没有红牌，一种方法；有一块红牌，让其插空，有18C种方法；有二块红牌，让其插空，有27C种方法；有三块红牌，让其插空，有36C种方法；有四块红牌，让其插空，有45C种方法；共有方法12348765155CCCC种.说明：对于不相邻问题，常用“插空法”（特殊元素后考虑）．例3某仪表显示屏上一排有7个小孔，每个小孔可显示出0或1，若每次显示其中三个孔，但相邻的两孔不能同时显示，则这显示屏可以显示的不同信号的种数有种.解：四个孔不亮，三个孔亮，相当于三个亮着的孔在四个不亮的孔之间插空，故有35222C80种方法.三.部分不同元素定序与部分相同元素排列问题：部分不同元素在排列前后的顺序固定不变（不一定相邻）的排列问题，称之为“定序排列”问题.解决这类问题的基本方法有三种.（1）“消序法”（有些地方叫“整体法”），即若有mn个元素排成一列，其中有m个元素之间的排列顺序不变，将这mn个元素任意排成一列，共有mnmnA种不同的排法，其中未定序的n个元素排在某一特定位置的排列的个数有mmA种排法，但只有一个排列是我们所需要的排列，因而共有mnmnmmAA种不同的排法.类似地还可推广到一般情形，如有有mnk个元素排成一列，其中有m个元素之间的排列顺序不变，且另外k个元素之间的排列顺序也不变，则共有mnkmnkmkmkAAA中不同的算法.（2）逐一插空法：先将定序的元素进行排列，再将其它元素逐一插入这组元素两端及中间.（3）优序法：先将所有位置中按“特殊元素”个数选出若干位置，并把这些特殊元素按规定顺序排上去，再将普通元素在其余位置上全排列.例4若5男5女排成一排，按下列要求各有多少种排法（1）男女相间；（2）女生按指定顺序排列.解：（1）先将男生排好，有55A种排法；再将5名女生插在男生之间的6个“空挡”（包括两端）中，有552A种排法.故本题的排法有5555228800NAA（种）；（2）方法1（消序法）：10510105530240ANAA；方法2（逐一插空法）：5个女生按序排列，有1中方法，5个男生逐个插空，有6,7,8,9,10种方法，共有67891030240种方法.方法3（优序法）：设想有10个位置，先将男生排在其中的任意5个位置上，有510A种排法；余下的5个位置排女生，因为女生的顺序已经指定，所以她们只有一种排法.故本题的结论为510130240NA（种）.例5今有2本相同的语文书，3本相同的数学书，4本相同的英语书排成一排，有多少种不同的排法？解：（消序法）有992342341260AAAA种.例6一个楼梯共18个台阶，12步登完，可一步登一个台阶，也可一步登两个台阶，一共有多少种不同的走法？解：根据题意，要想12步登完，只能6个一步登一个台阶，6个一步登二个台阶.因此，把问题转化为“相同元素”的排列问题.因此有12126666924AAA（种）.点评：对于部分不同元素定序排列以及相同元素的排列问题，可用优序法.【随堂练习】1．从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五有2人参加，星期六、星期日各有1人参加，则不同的选派方法共有（B）A．40种B．60种C．100种D．120种2.安排3名支教老师去6所学校任教，每校至多2人，则不同的分配方案共有210种.（用数字作答）3．用数字0，1，2，3，4，5组成没有重复数字，且比20000大的五位偶数有（）A.288个B.240个C.144个D.126个4．如图，用6种不同的颜色给图中的4个格子涂色，每个格子涂一种颜色，要求最多使用3种颜色且相邻的两个格子颜色不同，则不同的涂色方法共有390种（用数字作答）．5．某校开设9门课程供学生选修，其中,,ABC三门由于上课时间相同，至多选一门，学校规定每位同学选修4门，共有75种不同选修方案.（用数值作答）6．从班委会5名成员中选出3名，分别担任班级学习委员、文娱委员与体育委员，其中甲、乙二人不能担任文娱委员，则不同的选法共有36种．（用数字作答）【课后作业】1．某校安排5个班到4个工厂进行社会实践，每个班去一个工厂，每个工厂至少安排一个班，不同的安排方法共有240种．（用数字作答）2．将数字1，2，3，4，5，6拼成一列，记第i个数为ia（i1，2，…，6），若11a，33a，55a，135aaa，则不同的排列方法有30种（用数字作答）．解：分两步：（1）先排1a，3a，5a，当1a=2时，有2种；当1a=3时，有2种；当1a=4时，有1种，共有5种；（2）再排2a，4a，6a，共有633A种，故不同的排列方法种数为5×6=30，填30．3.中韩两支围棋队各由8人组成，按事先排好的次序出场进行围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……，直到有一方全部被淘汰为止，另一方获胜，形成一个比赛过程．（1）已知中方动用了5名队员，取得了胜利，问这样的比赛过程有多少种？（2）求由中方第8位选手获得最后胜利的概率.解：（1）中方胜利时，双方共有8513名队员参加了比赛，将他们按淘汰的顺序从左向右排列，则最右为中方5号，右第二个为韩方8号，从右第三个至最左，共11个位置上，有4个位置排中方队员，其余排韩方队员，每一种排法，对应一种比赛结果，故共有411330C种．（2）714816415CpC.4.若7位同学站成一排（1）甲、乙两同学不能相邻的排法共有多少种？（2）甲、乙和丙三个同学都不能相邻的排法共有多少种？解：（1）解法一：（排除法）3600226677AAA；解法二：（插空法）先将其余五个同学排好有55A种方法，此时他们留下六个位置（就称为“空”吧），再将甲、乙同学分别插入这六个位置（空）有26A种方法，所以一共有36002655AA种方法．（2）先将其余四个同学排好有44A种方法，此时他们留下五个“空”，再将甲、乙和丙三个同学分别插入这五个“空”有35A种方法，所以一共有44A35A＝1440种．【课后记】第七课时几类特殊的排列组合问题的解决技巧（二）教学目标：掌握几类特殊的排列问题的解决技巧.教学重点：掌握“错位排列”、“圆桌排列”、“转化命题”等问题的解题技巧.教学难点：如何应用“技巧”解题．教学过程：【例析技巧】四.错位排列问题n个不同元素排成一排，有m个元素（mn）不排在相应位置的排列种数共有：112233123(1)nnnnmmnmnmnmnmnmnmACACACACA.当nm时，规定000!1A，这个公式亦成立.例7五封标号为1～5的信放进5个编号为1～5的信笺里面，若信的编号与信笺的编号都不相同，一共有多少种不同放法.解：这是著名的信封问题，很多著名数学家都研究过.瑞士数学家欧拉按一般情况给出了一个递推公式：用A、B、C……表示写着n位友人名字的信封，a、b、c……表示n份相应的写好的信.把错装的总数记为()fn.假设把a错装进B里了，包含着这个错误的一切错装法分两类：（1）b错装进A里，这时每种错装的其余部分都与a、b、A、B无关，应有(2)fn种错装法.（2）b错装进A、B之外的信封，这时的装信工作实际是把（除a之外的）信纸b、c……装入（除B之外的）1n个信封A、C……，显然这种错装方法有(1)fn种.错装的其余部分都与a、b、A、B无关，应有(2)fn种错装法.总之在a错装入B的错误之下，共有错装法(1)(2)fnfn种.装入D……的2n种错误之下，同样都有(1)(2)fnfn种错装法.因此()(1)[(1)(2)]fnnfnfn，显然(1)0f，(2)1f.由此可得(5)44f.注意：用容斥原理亦可解决此题.普遍结论为错排公式1：1111()![1(1)]1!2!3!!nfnnn.错排递推公式2：()(1)[(1)(2)]fnnfnfn错排公式3：112233123(1)nnnnmmnmnmnmnmnmnmACACACACA例8有5个人站成一排，其中A不站第一位，B不站第二位，C不站第三位，D不站第四位，E不站第五位，共有多少种不同的站法.解析：上面两例实际上可以看成n个不同元素中有m（mn）错位排列的问题.而这个问题是其特殊情况，即全错位排列问题.共有514233241505545352515044ACACACACACA种（注意000!1A）例9同室四人各写一张贺年卡，先集中起来.然后每人从中拿一张别人送出的贺年卡.则四张贺年卡不同的分配方式有A.6种B.9种C.11种D.23种解析：由上面公式得：4132231404434241409ACACACACA种，∴选择B答案.因此可得到全错位排列的公式：n个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，……，第n个元素不在第n位的排列数为：11223301230(1)nnnnnnnnnnnnnnACACACACA这实际上是公式112233123(1)nnnnmmnmnmnmnmnmnmACACACACA