排列组合题解法总结3755.pdf

《排列组合题解法总结3755.pdf》由会员分享，可在线阅读，更多相关《排列组合题解法总结3755.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排列组合题型总结 灵璧一中 裴恒永 1 排列组合题解法总结 解决排列组合综合性问题的一般过程如下:1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 二.相邻元素捆绑策略 三.不相邻问题插空策略 四.定序问题用除法 五.直接不行间接法 六.多排问题直排策略 8 人排成前后两排,每排4 人,其中甲乙在前排,丙在后排,共有多少排

2、法 解:共有215445A A A种 前 排后 排 七.排列组合混合问题先选后排策略 例.有 5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装法.要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也必须排列.元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两排列组合题型总结 灵璧一中 裴恒永 2 解:第一步从5 个球中选出2 个组成复合元共有25C种方法.再把4个元素(包含一个复合元素)装入4 个不同的盒内有44A种方法，根据分步计数原理装球的方法共有2454C A

3、 练习题：一个班有6 名战士,其中正副班长各1 人现从中选4 人完成四种不同的任务,每人完成一种任务,且正副班长有且只有1人参加,则不同的选法有 192 种 八.小集团问题先整体后局部策略 例，计划展出10 幅不同的画,其中1 幅水彩画,幅油画,幅国画,排成一行陈列,要求同一品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为254254A A A 九.元素相同问题隔板策略 例.有 10 个运动员名额，分给7 个班，每班至少一个,有多少种分配方案？解：因为10 个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。在个空档中选个位置插个隔板，可把名额分成份，对应地分给个班级，每一

4、种插板方法对应一种分法共有69C种分法。一班二班三班四班五班六班七班 练习题，10 个相同的球装5 个盒中,每盒至少一有多少装法？49C 十.平均分组问题除法策略 例.6 本不同的书平均分成3 堆,每堆2 本共有多少分法？解决排列组合混合问题,先选后排是最基本的指导思想.此法与相邻元素捆绑策略相似吗?将 n 个相同的元素分成 m 份（n，m 为正整数）,每份至少一个元素,可以用 m-1 块隔板，插入 n 个元素排成一排的 n-1 个空隙中，所有分法数为11mnC 排列组合题型总结 灵璧一中 裴恒永 3 解:共有22236423/C C CA种分法。练习题：1，将 13 个球队分成3 组,一组5

5、 个队,其它两组4 个队,有多少分法？（544213842/C C CA）2.某校高二年级共有六个班级，现从外地转入4 名学生，要安排到该年级的两个班级且每班安排2 名，则不同的安排方案种数为_（22224262/90C C AA）十一.合理分类与分步策略 例.在一次演唱会上共10 名演员,其中8 人能唱歌,5 人会跳舞,现要演出一个2 人唱歌2 人伴舞的节目,有多少选派方法 解：10 演员中有5 人只会唱歌，2 人只会跳舞3 人为全能演员。选上唱歌人员为标准进行研究只会唱的5 人中没有人选上唱歌人员共有2233C C种,只会唱的5 人中只有1 人选上唱歌人员112534C C C种,只会唱的

6、5 人中只有2 人选上唱歌人员有2255C C种，由分类计数原理共有 22112223353455C CC C CC C种。十二.构造模型策略 例.马路上有编号为1,2,3,4,5,6,7,8,9 的九只路灯,现要关掉其中的3 盏,但不能关掉相邻的2 盏或3 盏,也不能关掉两端的 2 盏,求满足条件的关灯方法有多少种？平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以nnA(n为均分的组数)避免重复计数。解含有约束条件的排列组合问题，可按元素的性质进行分类，按事件发生的连续过程分步，做到标准明确。分步层次清楚，不重不漏，分类标准一旦确定要贯穿于解题过程的始终。排列组合题型总

7、结 灵璧一中 裴恒永 4 解：把此问题当作一个排队模型在6 盏亮灯的5 个空隙中插入3 个不亮的灯有35C 种 练习题：某排共有10 个座位，若4 人就坐，每人左右两边都有空位，那么不同的坐法有多少种？（120）十三.实际操作穷举策略 例.设有编号1,2,3,4,5的五个球和编号1,2,3,4,5的五个盒子,现将5 个球投入这五个盒子内,要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号相同,有多少投法 解：从5 个球中取出2 个与盒子对号有25C种还剩下3 球 3 盒序号不能对应，利用实际操作法，如果剩下3,4,5 号球,3,4,5 号盒3 号球装4 号盒时，则4,5 号球有只有1 种

8、装法，同理3号球装5 号盒时,4,5 号球有也只有1 种装法,由分步计数原理有252C种 534 3 号盒 4 号盒 5 号盒 练习题：同一寝室4 人,每人写一张贺年卡集中起来,然后每人各拿一张别人的贺年卡，则四张贺年卡不同的分配方式有多少种？(9)十四.分解与合成策略 例.30030 能被多少个不同的偶数整除 分析：先把30030 分解成质因数的乘积形式30030=2 3 5 7 11 13 依题意可知偶因数必先取2,再从其余5 个因数中任取若干个组成乘一些不易理解的排列组合题如果能转化为非常熟悉的模型，如占位填空模型，排队模型，装盒模型等，可使问题直观解决 对于条件比较复杂的排列组合问题，

9、不易用公式进行运算，往往利用穷举法或画出树状图会收到意想不到的结果 排列组合题型总结 灵璧一中 裴恒永 5 积，所有的偶因数为：1234555555CCCCC 练习:正方体的8 个顶点可连成多少对异面直线 解：我 们 先 从8 个 顶 点 中 任 取4 个 顶 点 构 成 四 体 共 有 体 共481258C,每个四面体有3 对异面直线,正方体中的8 个顶点可连成3 58174对异面直线 十五.化归策略 例.25 人排成5 5 方阵,现从中选3 人,要求3 人不在同一行也不在同一列,不同的选法有多少种？解：将这个问题退化成9 人排成3 3 方阵,现从中选3 人,要求3 人不在同一行也不在同一列

10、,有多少选法.这样每行必有1人从其中的一行中选取1 人后,把这人所在的行列都划掉，如此继续下去.从3 3 方队中选3 人的方法有111321C C C种。再从5 5 方阵选出3 3 方阵便可解决问题.从 5 5 方队中选取3 行3 列有3355C C选法所以从5 5 方阵选不在同一行也不在同一列的3 人有3311155321C C C C C选法。分解与合成策略是排列组合问题的一种最基本的解题策略,把一个复杂问题分解成几个小问题逐一解决,然后依据问题分解后的结构,用分类计数原理和分步计数原理将问题合成,从而得到问题的答案,每个比较复杂的问题都要用到这种解题策略 排列组合题型总结 灵璧一中 裴恒

11、永 6 练习题:某城市的街区由12 个全等的矩形区组成其中实线表示马路，从 A 走到B 的最短路径有多少种？(3735C)BA 十六.树图策略 例3 人相互传球,由甲开始发球,并作为第一次传球,经过5 次传求后,球仍回到甲的手中,则不同的传球方式有_ 练习:分别编有1，2，3，4，5 号码的人与椅，其中i号人不坐i号椅（54321,i）的不同坐法有多少种？44N 十七，递推法 一楼梯共 10 级，如果规定每次只能跨上一级或两级，要走上这 10 级楼梯，共有多少种不同的走法？分析：设上 n级楼梯的走法为 an种，易知 a1=1,a2=2,当 n2 时，上 n 级楼梯的走法可分两类：第一类：是最后一步跨一级，有 an-1种走法，第二类是最后一步跨两级，有an-2种 走 法，由 加 法 原 理 知：an=an-1+an-2,据 此，处理复杂的排列组合问题时可以把一个问题退化成一个简要的问题，通过解决这个简要的问题的解决找到解题方法，从而进下一步解决对于条件比较复杂的排列组合问题，不易用公式进行运算，树图会收到意想不到的结果。排列组合题型总结 灵璧一中 裴恒永 7 a3=a1+a2=3,a4=a#+a2=5,a5=a4+a3=8,a6=13,a7=21,a8=34,a9=55,a10=89.故走上 10 级楼梯共有 89 种不同的方法。另外排列组合中的几何问题和染色问题待续！