排列组合典型问题选讲 (2).doc

一.集团排列问题：部分元素必须安排在一起（相邻）的排列问题，称之为“集团排列”问题.解决这类问题，常用“捆绑法”，其方法是先排“集团”内部的元素，再把这个大“元素”与其它元素一起排列即可.例1 若7位同学站成一排（1）甲、乙两同学必须相邻的排法共有多少种？（2）甲、乙和丙三个同学都相邻的排法共有多少种？（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？（4）甲、乙、丙三个同学必须站在一起，另外四个人也必须站在一起的排法有多少种？解：（1）先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）一起进行全排列有种方法；再将甲、乙两个同学“松绑”进行排列有种方法所以这样的排法一共有种.（2）方法同上，一共有720种.（3）解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，有种方法；将剩下的4个元素进行全排列有种方法；最后将甲、乙两个同学“松绑”进行排列有种方法所以这样的排法一共有960种方法.解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有2种方法，所以，丙不能站在排头和排尾的排法有种方法.解法三：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有种方法，再将其余的5个元素进行全排列共有种方法，最后将甲、乙两同学“松绑”，所以，这样的排法一共有960种方法（4）将甲、乙、丙三个同学“捆绑”在一起看成一个元素，另外四个人“捆绑”在一起看成一个元素，时一共有2个元素，一共有排法种数：（种）说明：对于相邻问题，常用“捆绑法”（先捆后松）二. 间隔排列问题：部分元素不能安排在一起（间隔）的排列问题，称之为“间隔排列”问题.解决这类问题，常用“插空法”，其方法是先排不需要间隔的元素，再将需要间隔的元素通过插空的方式插进来即可.例2 在一条南北方向的步行街同侧有8块广告牌，牌的底色可选用红、蓝两种颜色.若只要求相邻两块牌的底色不都为红色，则不同的配色方案共有（ ）A.55. B.56. C.46. D.45.解：没有红牌，一种方法；有一块红牌，让其插空，有种方法；有二块红牌，让其插空，有种方法；有三块红牌，让其插空，有种方法；有四块红牌，让其插空，有种方法；共有方法种.说明：对于不相邻问题，常用“插空法”（特殊元素后考虑）例3 某仪表显示屏上一排有7个小孔，每个小孔可显示出0或1，若每次显示其中三个孔，但相邻的两孔不能同时显示，则这显示屏可以显示的不同信号的种数有 种.解：四个孔不亮，三个孔亮，相当于三个亮着的孔在四个不亮的孔之间插空，故有80种方法.三. 部分不同元素定序与部分相同元素排列问题：部分不同元素在排列前后的顺序固定不变（不一定相邻）的排列问题，称之为“定序排列”问题.解决这类问题的基本方法有三种.（1）“消序法”（有些地方叫“整体法”），即若有个元素排成一列，其中有个元素之间的排列顺序不变，将这个元素任意排成一列，共有种不同的排法，其中未定序的个元素排在某一特定位置的排列的个数有种排法，但只有一个排列是我们所需要的排列，因而共有种不同的排法.类似地还可推广到一般情形，如有有个元素排成一列，其中有个元素之间的排列顺序不变，且另外个元素之间的排列顺序也不变，则共有中不同的算法.（2）逐一插空法：先将定序的元素进行排列，再将其它元素逐一插入这组元素两端及中间.（3）优序法：先将所有位置中按“特殊元素”个数选出若干位置，并把这些特殊元素按规定顺序排上去，再将普通元素在其余位置上全排列.例4 若5男5女排成一排，按下列要求各有多少种排法（1）男女相间；（2）女生按指定顺序排列.解：（1）先将男生排好，有种排法；再将5名女生插在男生之间的6个“空挡”（包括两端）中，有种排法.故本题的排法有（种）；（2）方法1（消序法）：；方法2（逐一插空法）：5个女生按序排列，有1中方法，5个男生逐个插空，有6,7,8,9,10种方法，共有种方法.方法3（优序法）：设想有10个位置，先将男生排在其中的任意5个位置上，有种排法；余下的5个位置排女生，因为女生的顺序已经指定，所以她们只有一种排法.故本题的结论为（种）.例5 今有2本相同的语文书，3本相同的数学书，4本相同的英语书排成一排，有多少种不同的排法？解：（消序法）有种.例6 一个楼梯共18个台阶，12步登完，可一步登一个台阶，也可一步登两个台阶，一共有多少种不同的走法？解：根据题意，要想12步登完，只能6个一步登一个台阶，6个一步登二个台阶.因此，把问题转化为“相同元素”的排列问题.因此有（种）.点评：对于部分不同元素定序排列以及相同元素的排列问题，可用优序法.【随堂练习】1从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五有2人参加，星期六、星期日各有1人参加，则不同的选派方法共有（ B ）A40种B60种C100种D120种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门课程供学生选修，其中三门由于上课时间相同，至多选一门，学校规定每位同学选修4门，共有75种不同选修方案.（用数值作答）6从班委会5名成员中选出3名，分别担任班级学习委员、文娱委员与体育委员，其中甲、乙二人不能担任文娱委员，则不同的选法共有 36 种（用数字作答）【课后作业】1某校安排5个班到4个工厂进行社会实践，每个班去一个工厂，每个工厂至少安排一个班，不同的安排方法共有240种（用数字作答）2将数字1，2，3，4，5，6拼成一列，记第个数为（1，2，6），若，则不同的排列方法有 30 种（用数字作答）解：分两步：（1）先排，当=2时，有2种；当=3时，有2种；当=4时，有1种，共有5种；（2）再排，共有种，故不同的排列方法种数为56=30，填303.中韩两支围棋队各由8人组成，按事先排好的次序出场进行围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，直到有一方全部被淘汰为止，另一方获胜，形成一个比赛过程（1）已知中方动用了5名队员，取得了胜利，问这样的比赛过程有多少种？（2）求由中方第8位选手获得最后胜利的概率.解：（1）中方胜利时，双方共有8513名队员参加了比赛，将他们按淘汰的顺序从左向右排列，则最右为中方5号，右第二个为韩方8号，从右第三个至最左，共11个位置上，有4个位置排中方队员，其余排韩方队员，每一种排法，对应一种比赛结果，故共有种（2）.4. 若7位同学站成一排（1）甲、乙两同学不能相邻的排法共有多少种？（2）甲、乙和丙三个同学都不能相邻的排法共有多少种？解：（1）解法一：（排除法）；解法二：（插空法）先将其余五个同学排好有种方法，此时他们留下六个位置（就称为“空”吧），再将甲、乙同学分别插入这六个位置（空）有种方法，所以一共有种方法（2）先将其余四个同学排好有种方法，此时他们留下五个“空”，再将甲、乙和丙三个同学分别插入这五个“空”有种方法，所以一共有1440种【课后记】四.错位排列问题个不同元素排成一排，有个元素（）不排在相应位置的排列种数共有：.当时，规定，这个公式亦成立.例7 五封标号为15的信放进5个编号为15的信笺里面，若信的编号与信笺的编号都不相同，一共有多少种不同放法.解：这是著名的信封问题，很多著名数学家都研究过.瑞士数学家欧拉按一般情况给出了一个递推公式：用、表示写着位友人名字的信封，、表示份相应的写好的信.把错装的总数记为.假设把错装进里了，包含着这个错误的一切错装法分两类：（1）错装进里，这时每种错装的其余部分都与、无关，应有种错装法.（2）错装进、之外的信封，这时的装信工作实际是把（除之外的）信纸、装入（除之外的）个信封、，显然这种错装方法有种.错装的其余部分都与、无关，应有种错装法.总之在错装入的错误之下，共有错装法种.装入的种错误之下，同样都有种错装法.因此，显然，.由此可得.注意：用容斥原理亦可解决此题.普遍结论为错排公式1：.错排递推公式2： 错排公式3：例8有5个人站成一排，其中A不站第一位，B不站第二位，C不站第三位，D不站第四位，E不站第五位，共有多少种不同的站法.解析：上面两例实际上可以看成个不同元素中有（）错位排列的问题.而这个问题是其特殊情况，即全错位排列问题.共有种（注意）例9 同室四人各写一张贺年卡，先集中起来.然后每人从中拿一张别人送出的贺年卡.则四张贺年卡不同的分配方式有A.6种B.9种C.11种D.23种 解析：由上面公式得：种，选择B答案.因此可得到全错位排列的公式：个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，第个元素不在第位的排列数为：这实际上是公式的特殊情况.这个公式很有用，只要有特殊元素不站特殊位置的问题，都可以用这个公式很快得到解决，希望这个公式对大家有所帮助.五. 圆桌排列从个不同元素中不重复的取出（）个元素排在一个圆周上，叫做这个不同元素的圆排列.如果一个-圆排列旋转可以得到另一个-圆排列，则认为这两个圆排列是相同的.特别的，当时，个不同元素作成的圆排列总数为.证明：在圆周上任选一个位置排有种排法，再选一个位置排有种排法，最后一个位置排有1种排法.而这个人顺时针（或逆时针）挪动次位置都是同一种排列.所以共有种排法.例10 有5对夫妇参加一场婚宴，他们被安排在一张10个座位的圆桌就餐，但是婚礼操办者并不知道他们彼此之间的关系，只是随机安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少？( )A.在1到5之间B.在5到1%之间C.超过1%D.不超过1解：5对夫妇相邻而座，可以看做是五个大元素为桌而坐，所以有种坐法，而夫妇间又可以换位置，所以共有. 故选：A.例11 博杰学习网竞赛小组“先进人物评比”最终圈定了个人，需要确定最终的三个“先进人物”人选.方法是：这个人排成一行，从第一名开始，1至3循环报数，凡报出3的就退出，余下的向前靠拢，按此规律重复进行.直到第次报数后，只剩下3个人为止.试问：这剩下的三个人，分别在队伍最初的什么位置？解：设个人的编号依次为1,2，.最后剩下的三个人中，第三人的编号为.因未被淘汰，故不是3的倍数.第一次报数后淘汰了个人，还剩个人.向前移动了（）个人，前面淘汰了（1,2）个人.故.其中当为奇数时，；否则，每报一次号，人数减少（除不尽时取整）.计算逐步归纳为减小的数列，最终划归到小情况.例如时，第三个人的初始位置是712.例12 将圆分成（）个扇形，现用（）种颜色给这些扇形染色，每个扇形恰染一种颜色且要求相邻的扇形不同色.问有多少种不同的染色方法？解：设染色方法数为.（1）求初始值.当时，给染色有种方法，给染色有种方法.所以；（2）求递推关系. 给染色有种方法，给染色有种方法，给染色有种方法，给染色有种方法.共有种方法.这种情况可以分为两类一类是与不同色，此时的染色方法种数是；另一类是与同色，与可以合并为一个扇形，与不同色，染色方法种数为.由加法原理，得到（）.（3）求.构造等比数列.结论：共有种染色方法.六.转化命题对于一些较难的排列组合问题，通常采用转化命题的方法来解决.比如圆内弦的交点个数可转化为圆内接四边形的个数；异面直线的对数可转化为3倍的四面体的个数等.例13 圆周上共有15个不同的点，过其中任意两点连一弦，这些弦在圆内的交点最多有多少个？分析：若两弦有交点，则两弦应是圆内接四边形的对角线，即一个四边形对应一个交点.所以共有个交点.小结：1.“在”与“不在”可以相互转化.解决某些元素在某些位置上用“定位法”，解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解.2.排列组合应用题极易出现“重”、“漏”现象，而“重”、“漏”错误常发生在该不该分类、有无顺序的问题上.为了更好地防“重”堵“漏”，在做题时需认真分析自己做题思路，也可改变解题角度，利用一题多解核对答案.【作业】1.今有8个人坐圆桌，有多少种坐法？2.有5个男孩，3个女孩围成一圆，其中3个女孩不相邻，有多少种站法？3.一圆型餐桌依次有、六个座位，现让3个大人和3个孩子入座进餐，要求任何两个小孩都不能坐在一起，则不同的作法总数为 72 .七. 用容斥原理解排列问题有些排列组合问题可转化为求集合的元素的个数来求.充分应用容斥原理：.例14五人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法.解：这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑5个有的全排列，有种不同的排法，然后除去甲排第一（有种）与乙排第二（也有种），但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：种.例15有5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法.仿上分析可得：种.八.均匀分组问题一般地：将个不同元素均匀分成组（每组个元素），共有种方法例16 有6本不同的书，按下列要求各有多少种不同的选法：（1）分给甲、乙、丙三人，每人2本；（2）分为三份，每份2本；（3）分为三份，一份1本，一份2本，一份3本；（4）分给甲、乙、丙三人，一人1本，一人2本，一人3本；（5）分给甲、乙、丙三人，每人至少1本.解：（1）根据分步计数原理得到：种；（2）分给甲、乙、丙三人，每人两本有种方法，这个过程可以分两步完成：第一步分为三份，每份两本，设有种方法；第二步再将这三份分给甲、乙、丙三名同学有种方法根据分步计数原理可得：，所以因此，分为三份，每份两本一共有15种方法（3）这是“不均匀分组”问题，一共有种方法（4）在（3）的基础上再进行全排列，所以一共有种方法（5）可以分为三类情况：“2、2、2型”即（1）中的分配情况，有种方法；“1、2、3型”即（4）中的分配情况，有种方法；“1、1、4型”，有种方法；所以，一共有90+360+90540种方法点评：本题第（3）种类型为部分均匀分组再分配，其分组总数为题型变换：8名球员住、三个房间，每个房间最多住3人，有多少种住宿方法？解：例17 若3名飞行员和6名特勤人员分别上3架不同型号的直升飞机执行任务,每机一名飞行员和两名特勤人员，有多少种分配方法？解：先分组，再分配，或者类题：20名同学分两组，每组10人去某地社会实践，其中6名干部，每组3人，不同分法总数是多少？答案：九. 隔板法：将个相同元素，分成（，）组，可以看成是在个元素之间的个空隙间插入块隔板.共有种方法.例18 将六本相同的书全部发给甲、乙、丙三人.（1）每人至少分到一本书，问有多少种不同的分法？（2）每人不一定都分到一本书，问有多少种不同的分法？解：（1）用“隔板法”处理，六本书之间有五个空，插入两块隔板，有种分法；用“隔板站位法”处理，六本书之间有五个空，需插入两块隔板，但由于有人可能没有书，所以两块隔板站着两个位置，加上六本书，可以看着是本书，分成3分，所以有种分法点评：类题求不定方程的非负整数解的个数？题型变换一：四本不同的书，分给三个人，每人至少一本，全部分完，有几种分法？解：先分组，再分配有种题型变换二：本不同的书，分给个人，每人至少1本，全部分完，有几种分法？解：先分组，再分配有种题型变换三：本相同的书，全部分给（）个人.（1）每人至少分到一本书，问有多少种不同的分法？（2）每人不一定都分到一本书，问有多少种不同的分法？解：（1）解法一（隔板站位法）：每人先分一本书，还剩下本书，加上块隔板，可视为本书，分给个人，所以有种方法.解法二（隔板法）：本书之间有个空，需插入块隔板，所以有种方法.（2）（隔板站位法）：本书之间，需插入块隔板，但是，由于有人分不到书，所以块隔板站着个位置，加上本书，可视为本书，用块隔板分成分，所以有种方法（这也是一个公式）.【随堂练习】1.（1） 四个不同的小球放入四个不同的盒中，一共有多少种不同的放法？（2） 四个不同的小球放入四个不同的盒中且恰有一个空盒的放法有多少种？解：（1）根据分步计数原理：一共有种方法；（2）（捆绑法）第一步：从四个不同的小球中任取两个“捆绑”在一起看成一个元素有种方法；第二步：从四个不同的盒中任取三个将球放入有种方法，所以，一共有144种方法说明：先组合，再排列是解决问题的关键本题亦可先将4个小球分成三组，每组分别有/个，共再放入四个盒子中的三个，共有种思考：（1）四个相同的小球放入四个不同的盒子中，一共有多少种不同的放法？解：（隔板站位法）共（2）10个相同的小球放入编号为1、2、3的盒子中，球数不少于编号数的放法有多少种？解：按要求放6个，其余4个按隔板站位法有种方法另解：（隔板法）设1，2，3号盒子所放的球数分别为，.则有.设，则方程的正整数解的组数，就是放球的方法数.所以共有种方法.注意：这种利用“先换元，再用隔板技巧”的方法对于求有限制条件的不定方程的非负整数解的问题很有效！【总结提炼】均匀分组（不计组的顺序）问题不是简单的组合问题，如：将个人分成 组，每组一个人，显然只有种分法，而不是种 一般地，将个不同元素均匀分成组，有种分法；十.穷举法：对于一些不能直接用两个原理，且类别不多的问题，通常采用穷举法.即列举所有情况.例19 将五个市级三好学生名额和八个区级优秀学生干部名额全部分配到辖区的两所中学，每所学校至少有一个名额，有多少种不同的分配方案？解：分配情况用有序数组表示：（1,12），（2,11），（3,10），（4,9），（5,8），（6,7）.然后两校交换.所以共有分配方案数为223456652种.例20 .十一.递推法：对于一些较复杂的排列问题，可以建立排法之间的一个递推关系，通过递推关系求出排法种数.例19 一个楼梯共10个台阶，如果规定一步登一个台阶或登两个台阶，一共有多少种不同的走法？解：设上级台阶的走法为种，易知，当时，上级台阶的走法可分两类：第一类是最后一步跨一级，有种走法，第二类是最后一步跨二级，有种走法.由加法原理可知，据此可得种不同的走法.例20 有五个人排成一列，现在要重新排列，要求都不能站在原来的位置，有几种不同排法？解：我们考虑人数为的情况，即个人排成一列，重新站队时，各人都不站在原来的位置上.设满足这样的站队方式有种，现在我们来通过合理分步，恰当分类找出递推关系：第一步：第一个人不站在原来的第一个位置，有种站法.第二步：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类：第一类，第二个人恰好站在第一个位置，则余下的个人有种站队方式；第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，第个人不站在第个位置，所以有种站队方式.由分步计数原理和分类计数原理，我们便得到了数列的递推关系式：，显然，.故有44种不同排法.注意：个人排成一排后，解散后重新排队，自己不站原来的位置的排法种数可由以下公式推导得到：（1），（）；（2）.（3）.例21 在的网格中，从点到点，只能沿网格的边向轴正方向或轴正方向前进，问共有多少种不同的前进路线？解：对任意一个非轴、轴上的点，可以从点走来，也可以从点走来.因此，设处的路线条数为，则有递推公式：.下面的推理很重要：根据上述