排列组合典型问题选讲

《排列组合典型问题选讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一.集团排列问题：部分元素必须安排在一起（相邻）的排列问题，称之为“集团排列”问题.解决这类问题，常用“捆绑法”，其方法是先排“集团”内部的元素，再把这个大“元素”与其它元素一起排列即可.例1若7位同学站成一排（1）甲、乙两同学必须相邻的排法共有多少种？（2）甲、乙和丙三个同学都相邻的排法共有多少种？（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？（4）甲、乙、丙三个同学必须站在一起，另外四个人也必须站在一起的排法有多少种？解：（1）先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）一起进行全排列

2、有种方法；再将甲、乙两个同学“松绑”进行排列有种方法．所以这样的排法一共有种.（2）方法同上，一共有720种.（3）解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有种方法；将剩下的4个元素进行全排列有种方法；最后将甲、乙两个同学“松绑”进行排列有种方法．所以这样的排法一共有960种方法.解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有2种方法，所以，丙不能站在排头和排尾的排法有种方法.解法三

3、：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有种方法，再将其余的5个元素进行全排列共有种方法，最后将甲、乙两同学“松绑”，所以，这样的排法一共有960种方法．（4）将甲、乙、丙三个同学“捆绑”在一起看成一个元素，另外四个人“捆绑”在一起看成一个元素，时一共有2个元素，∴一共有排法种数：（种）说明：对于相邻问题，常用“捆绑法”（先捆后松）．二.间隔排列问题：部分元素不能安排在一起（间隔）的排列问题，称之为“间隔排列”问题.解决这类问题，常用“插空法”，其方法是先

4、排不需要间隔的元素，再将需要间隔的元素通过插空的方式插进来即可.例2在一条南北方向的步行街同侧有8块广告牌，牌的底色可选用红、蓝两种颜色.若只要求相邻两块牌的底色不都为红色，则不同的配色方案共有（）A.55.B.56.C.46.D.45.解：没有红牌，一种方法；有一块红牌，让其插空，有种方法；有二块红牌，让其插空，有种方法；有三块红牌，让其插空，有种方法；有四块红牌，让其插空，有种方法；共有方法种.说明：对于不相邻问题，常用“插空法”（特殊元素后考虑）．例3某仪表显示屏上一排有7个小孔，每个小孔可显示出0或1，若每次显示其中三个孔，但

5、相邻的两孔不能同时显示，则这显示屏可以显示的不同信号的种数有种.解：四个孔不亮，三个孔亮，相当于三个亮着的孔在四个不亮的孔之间插空，故有80种方法.三.部分不同元素定序与部分相同元素排列问题：部分不同元素在排列前后的顺序固定不变（不一定相邻）的排列问题，称之为“定序排列”问题.解决这类问题的基本方法有三种.（1）“消序法”（有些地方叫“整体法”），即若有个元素排成一列，其中有个元素之间的排列顺序不变，将这个元素任意排成一列，共有种不同的排法，其中未定序的个元素排在某一特定位置的排列的个数有种排法，但只有一个排列是我们所需要的排列，因而

6、共有种不同的排法.类似地还可推广到一般情形，如有有个元素排成一列，其中有个元素之间的排列顺序不变，且另外个元素之间的排列顺序也不变，则共有中不同的算法.（2）逐一插空法：先将定序的元素进行排列，再将其它元素逐一插入这组元素两端及中间.（3）优序法：先将所有位置中按“特殊元素”个数选出若干位置，并把这些特殊元素按规定顺序排上去，再将普通元素在其余位置上全排列.例4若5男5女排成一排，按下列要求各有多少种排法（1）男女相间；（2）女生按指定顺序排列.解：（1）先将男生排好，有种排法；再将5名女生插在男生之间的6个“空挡”（包括两端）中，有

7、种排法.故本题的排法有（种）；（2）方法1（消序法）：；方法2（逐一插空法）：5个女生按序排列，有1中方法，5个男生逐个插空，有6,7,8,9,10种方法，共有种方法.方法3（优序法）：设想有10个位置，先将男生排在其中的任意5个位置上，有种排法；余下的5个位置排女生，因为女生的顺序已经指定，所以她们只有一种排法.故本题的结论为（种）.例5今有2本相同的语文书，3本相同的数学书，4本相同的英语书排成一排，有多少种不同的排法？解：（消序法）有种.例6一个楼梯共18个台阶，12步登完，可一步登一个台阶，也可一步登两个台阶，一共有多少种不同

8、的走法？解：根据题意，要想12步登完，只能6个一步登一个台阶，6个一步登二个台阶.因此，把问题转化为“相同元素”的排列问题.因此有（种）.点评：对于部分不同元素定序排列以及相同元素的排列问题，可用优序法.【随堂练习】1．