30、捆绑法与插空法---副本

陈老师讲义1/5第30讲捆绑法与插空法【内容综述】大家这节课需要掌握的知识主要是基本的排列、组合算法．1、mnA是最一般的乘法原理简单记号，n表示最大的因数，m表示因数的个数，且这m个因数连续，如，7654357A，123456789101010A，因此mnA是n个不同对象中选出m个的排列个数．2、mnC既是从n个不同对象中选出m个，却不去排列．．．．它，这样的选法数．或者是n个对象中恰有m个相同或m个不同对象顺序固定得到的组合数．它与排列数的关系为：1211221mmnnmmnnnnmACmmmA，mnmnnCC．这里学习排列组合中常用的两种方法：捆绑法和插空法．1、捆绑法：当一些对象需要相对位置固定，也就是说一个对象位置确定了，那么另一个对象的位置也就固定了，另一个对象就像它的“跟屁虫”．常见的是两者或三者相邻或只间隔1个或2个对象等．一般我们把这些对象捆绑在一起考虑，捆成一个“臃肿对象”参与排列，这个排列不妨叫做大排列，大排列后还要给捆在一起的对象松绑，这些捆绑对象还要排列，叫做小排列，大、小排列之积就是排列总数了．如果两个对象相邻也可以在这两个对象中找一个作代表参与排列，这个对象排好后，另一个对象赶快进入它的左边或右边，也能解决这类问题．2、插空法：如果一些对象不相邻，可以让其它对象先排好，然后不相邻对象插到它们之间的空隙中去，但是它们不能同时插在同一个空隙中，这种方法叫做对象插空法．在插空法中，空隙个数很重要，有时只在站好的对象之间的空隙中，也有时可以插到两端的位置．这节课我们主要学习的插空法，插入的是排列对象，相同或者不同，并不是插入“板子”或“符号”．插板子的插空法，又叫隔板法，我们将在后面学习进一步学习．两句顺口溜总结内容如下：捆绑法，要点抓，相邻问题就用它，屡试不爽嘻哈哈！插空法，真是好，分离问题没处跑，其它方法替不了！谁用谁知道，„„例1.入学军训时，8个人排成一排进行队列训练，其中1）甲、乙必须相邻的排列共有________种；2）甲、乙必须不相邻的排列共有________种；3）甲、乙必须相邻，丙、丁必须不相邻的排列共有________种．【分析】1）甲、乙必须相邻，也就是此两人形影不离，可以把两人捆在一起，看成一个“臃肿人”进行排列，同时进行整体的大排列，两人之间的小排列；2）上面第一小题甲、乙两人好的不得了，形影不离．你说这两个熊孩子，一会屁股一会脸的．现在两人闹矛盾了，谁看到谁都跟仇人似的，当然他们就不想站在一起了．其他同学对甲、乙两人的不友好感到很生气，不带甲、乙玩了，他们6人先站好了．这时甲、乙悻悻地走到队伍的空隙中，当然两人不能站在同一个空隙中．也就是其他6人先排列，甲、乙插到空隙中，注意两端也可以看作空隙，即空隙有7个，这种方法叫做“插空法”．3）这一小题是前面两小题的综合运用．甲、乙必须相邻先去捆绑，丙、丁必须不相邻后期插空．【解答】1）甲、乙必须相邻，采用捆绑法．甲、乙捆在一起看作1个对象，共有7个对象全排列，有774050A种，甲、乙之间的小排列有222A种，一共5040210080种．陈老师讲义2/5综合列式：727210080AA种．2）去掉甲、乙，其他6人先排列，有66720A种，6人站好后有7个空隙（包括两端），甲、乙的站法有2742A种，所以共有7204230240种．综合列式：626730240AA种．另解：甲、乙站位的情况只有两种，一种是相邻，另一种是不相邻，在就不相邻问题可以从整体全排列中去掉相邻的情况，所以有8810080403201008030240A种；3）甲、乙相邻捆绑成一个对象，丙、丁不相邻后期插空，这样就剩下5个对象全排列了，2255240AA种．6人站好后有7个位置可以让丙、丁插空，2721A种，所以240215040种．综合列式：2552271202504021AAA种．【评注】在第一小题中，也可以采用“代表法”，让甲先参与排列，然后乙可以站到甲的左边或者右边，共2种情况，所以列式为77082100A种．例2.8名学生站成一排，且其中甲与乙之间恰好间隔2人，那么共有________种不同的站法．【分析】甲、乙之间恰有两人，它们的位置相对固定，可以先选两人站在中间，参与4人的捆绑，变成一个“臃肿对象”参与整体排列，同时注意甲、乙可以互换位置．【解答】如图，甲、乙可以排在方框的位置，从其它6人中选出2人排在中间的圆圈位置，有2630A种，1大4小参与全排列，有55120A种，甲、乙排列有222A种，共3012027200种．综合列式：5622257200AAA种．另解：本题分为三步，然后使用乘法原理，【评注】在多人的捆绑中，注意要先选好搭配的对象，然后参与大排列，同时也不要忘了小排列哦．例3.在一张节目表上原有6个节目，如果保持这些节目的相对顺序不变，再添加进去三个不同节目，有________种安排方法，若新添的三个不同节目互不相邻，共有________种不同安排方法．【分析】6个节目相对顺序不变，故此6人不需要排列了，而新插入3个节目是否可以相邻，是插入的时候需要注意的．甲、乙一起选位置5甲、乙排列22A其他6人排列66A7200陈老师讲义3/5【解答】1）6个节目相对顺序不变，即排法唯一，加上首尾，有7个位置排可以3个不同新节目．由于新节目不同，可以分开依次插入，第一个新节目有7个位置插入．一旦第一个插入后，由于新节目位置没有限制，当然可以相邻，这样第二个新节目插入的位置就增加到8个位置，同理第三个新节目插入的位置增加到9个，所以共有789504种安排方法．2）当新节目不同且互不相邻，可以从7个位置中选3个位置插入新节目，有37765210A种．注意这里为什么是37A种，而不是37C种呢？哦，原因是3个新节目互不相同，如果3个新节目完全相同，则就是37C种了．【评注】在使用插空法时候，一是注意插入的“空”有多少个？是否包括两端的位置？二是插入的对象是否相同，相同的可以一起插入，不同可以依次插入；三是插入的对象是否可以相邻？在第一小题中，当然也可以把9个节目全排列，然后考虑原来的6个节目顺序不变，6个对象的全排列就会变成1种了，共有9696987504AA种．例4.2名女生、2名男生和2名老师站成一排照相，如果要求2个男同学不相邻、2个女同学也不相邻，而两名老师不能站在排头和排尾，那么共有________种不同的站法；【分析】按照前面的思路，应该把不相邻的学生插空，但是有两组学生都不相邻，同时老师还不愿意站在两端，就没有可以先期来排列的了．干脆我们让不相邻的两组对象先排列，最后再考虑老师的位置吧．如果老师起到破坏相邻的情况，那一定要站这个位置，否则可以在中间随便插空了．【解答】1）首先一旦位置固定，老师之间、男生之间、女生之间可以相对换位，固每种位置都对应2228种排法．2）现在位置有多少种情况．先2男2女之间排列有246C种情况，其中有男排头的有3种：男男女女老师位置固定就1种：男师男女师女；男女男女老师位置随意，有233C种；男女女男老师有1人中间站位，另一个随意，有2种排法．女生排头排法相同，所以共有8[1322]96种不同的站法．【评注】在上面确定位置情况时，有点麻烦，分类较多反面分析，同学们可以试一试．例5.从数1、2、3、…、12中按从小到大的顺序取出三个数，使得三个数中相邻的两个数之差不小于3，那么这样的三个数共有________种取法；【分析】在取出的三个数中，按从小到大排列后，要求相邻两数之差大于或等于3，而平时任意取三个不同数，差是大于或等于1的，因此不妨把取到的后面两个数各减去1和2，就会与任意取三个数取法作出一个对应．【解答】设原来取出的符合要求的3个数为a、b、c，且abc，3cb，3ba．现在转化为取a、b1、c2，则相当于从1、2、3、„、9、10中任意取出三个互不相邻的数．与在6个数之间插入3个数，且插空的数不相邻完全对应，有3856C种．例如现在取出三个数为2、5、6，给后面两个数各加上1、2，实际对应取出的三个数为2、6、7．再如：1、3、5→1、4、7陈老师讲义4/53、6、10→3、7、12„„所以，共有3856C种．【评注】在计数问题中，如果一个问题比较复杂，经常在所求问题与所设计问题之间做出一一对应，这样就能得到所求的结果了，这种方法有时叫做对应法．另解，设原来取出的符合要求的3个数为a、b、c，且abc，3cb，3ba．现在转化为取a、b2、c4，则相当于从1、2、3、„、8中任意取出三个不同的数，有3856C种．例如现在取出三个数为2、5、6，给后面两个数各加上2、4，实际对应取出的三个数为2、7、10．再如：1、2、3→1、4、73、6、8→3、8、12„„所以，共有3856C种．例6.一条马路的一侧有20个路灯．为了迎接新年，要把其中的5盏灯，更换成5种颜色的彩灯，要求彩灯不是首尾的两个，且彩灯互不相邻，那么有________种不同的更换方法；【分析】现在彩灯互不相邻，可以把彩灯插空，要知道一共20盏灯，是在20515之间插入5盏不同的彩灯，彩灯有区别，选位且排列，同时彩灯不在首尾的位置．【解答】20盏路灯更换其中的5盏，变成颜色不同的5盏彩灯，且彩灯不相邻，相当于把彩灯插入14个空隙中，有514240240A种．【评注】这里彩灯互不相同，彩灯在空隙中要排列，如果是一样的彩灯，那么直接选位插入彩灯即可．【练习题】1.书架上有6本书摆放成一列，现将3本不同的书插入其中，所插入的书不相邻有________种不同放法；2.4名男生，3名女生，全体排成一行，1）男1号、女1号两人必须排在两端，共有________种排法；2）男生在一起、女生也在一起，共有________种排法；3）男、女相间，共有________种排法．陈老师讲义5/53.1）A、B、C、D、E、F、G这7个人排成一列，若要求A、B两人不能相邻，而B、C两人必须相邻，那么共有________种不同的排法．2）A、B、C、D、E、F、G这7个人排成一列，若要求A、B两人不能相邻，而C、D两人必须相邻，那么共有________种不同的排法．4.用1、2、3、4、5、6这六个数字组成无重复数字的六位数，其中首位数字大于末位数字，且3和4不在相邻两个数位的六位数共有________个．5.从1、2、3、4、5、6、7、8、9中取出三个数字，使得这三个数字互不相邻，共有________种取法；6.一条马路的一侧有20个路灯．为了节省用电，熄灭其中的5盏灯，要求熄灭的灯不是首尾的两个，同时不影响照明，熄灭的灯要不相邻，那么有________种不同的熄灭方法；【参考答案】1、210；2、240，288，144；3、1200，960；4、240；5、35；6、2002；