排列组合问题17种策略.

1、rST*r *复习巩固1 分类计数原理（加法原理） 完成一件事，有n类办法，在第1类办法中有 m】种不同的方法，在第2类办法中有m2种不 同的方法，在第n类办法中有叫种不同的 方法，那么完成这件事共有： 种不同的方法. N二叫切2+ni 口2分步计数原理（兼法原理） 完成一件事，需要分成n个步骤，做第1步有 眄种不同的方法，做第2步有叫种不同的方 法做第n步有叫种不同的方法，那么完 成这件事共有：二叫吗叫种不同的方法3分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法 都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法 完成事件的一个阶段，不能完成整个事件-解决排列

2、组合综合性问S的一般过程如下：1. 认真审题弄清要做什么事2. 怎样做才能完成所要做的事，即采取分步还 是分类或是分步与分类同时进行，确定分多少步及多少类。3. 确定每一步或每一类是排列问题（有序）还是 组合（无序）问题，元素总数是多少及取出多 少个元素.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略1. 推列的定义：从H个不同元素中，任取个元索，按照 定的顺序排成列，叫做从n个不同元索中取出个 元索的个排列。2. 组合的定义：从fl个不同元素中，任取ni个元素，并成一组，叫做从n个不同元素中取出m个尤素的一 个组合推列与组合的关键他矿题与次序仔无关系。A = Z7（n

3、 1）（” 一 2）（”一力 + 1）3. 列数公式：(zi m )!-林/Z(Z7 1)(/7 2)-*-(z/ 7+1)4组合数公式：U =穴=Cfnm !(n m)!5加法廉理和乘法原理：完成任务时是分类进行还足步进行。一.特殊元素和特殊位优先策*例1 由（M234,5可以组成多少个没有重复数字 五位奇数_鮮:由于末位和首位有特殊要求，应该优先安 IM_ _L_ f一 L 1位分析法和元素分析法罷解决排列组合问 MW用也是基本的方法若以元*分析为 主 11先安排特殊元*轉处理其它元若以 位分析为主 1先満足特殊位的要求再 如理其它位-若有多个约東条件往往是 考盘一个釣東条件的同时还要集願

4、其它条件练习题1. 7种不同的花种在排成一列的花盆里，若两 种葵花不种在中间，也不种在两端的花盆 里，问有多少不同的种法？解一：分两步完成：第一步选两英花之外的花占据两端和中间的位置竹X：利喟乍V上 第二步排其余的位置：冇A：种排法.共冇种不同的排法 解二：第一步由葵花去占位:右X：利扌申法第二步由其余元素占位: 右左种排法共tmx 种不同的拙法小结：当排列或组合问题中，若某些元素或某些位置有特殊要 求的时候，那么，一般先按排这些特殊元素或位置.然后再 按排其它元素或位置.这种方法叫特殊元素（位S）分析法。二相邻元素捆綁策略例27人站成一排，其中甲乙相邻且丙丁相 邻-共有多少种不同的排法WFi

5、:可先将甲乙两元素捆绑成整体并看成 一个复合元素，同时丙丁也看成一个 复合元孟再与其它元素进行排列， *宴求第几个元萦必须祥在一起的问题,可以用 糰绑法来詔决问题.即将需寥相邻前元素台井 为一丫元萦，再与其它元累一起作禅列，同时 搜注意白笄元素內部也必须挪列练习题某人射击8枪，命中4枪，4枪命中恰好 有3枪连在一起的情形的不同种数为(2()三不相邻问插空策略Til例3个晚会的节目有4个舞蹈 2个相声,3个 独唱，舞蹈节目不能连续出场，则节目的出 场顺序有多少种？解:分两步进行第一步排2个相声和3个独唱共 有 疋 种，第二步将4舞蹈插入第一步排 好的6个元素中间包含首尾两个空位共有 种上笙不同的

6、方法由分步计数原理,节目的 不同顺序共有也种元匚凭胡詞问趣可先把没有位童耍穴前元霆疑 行曲趾再把不扫邻元案插八中冋臥冏端练习题某班新年联欢会原定的5个节目已排成节 目单，开演前又增加了两个新节目如果 将这两个新节目插入原节目单中，且两 个新节目不相邻，那么不同插法的种数 为（30 ）四定序问题倍缩空位插入策略例47人排队其中甲乙丙3人顺序一定共有多 少不同的排法解：（倍缩法）对于某几个元素顺序一定的排列 问题,可先把这几个元素与其他元素一起 进行排列，然后用总排列数除以这几个元 素之间的全排列数,则共有不同排法种数 是：4Ax:|Til（空位法）设想有7把椅子让除甲乙丙以外 的四人就坐共有上

7、种方法，其余的三个 位S甲乙丙共有丄种坐法，则共有仝种 方法 思考:可以先让甲乙丙就坐吗?（插入法）先排甲乙丙三个人，共有1种排法，再 把其余4四人依次插入共有4*5*6*7方法 定序问题可以用倍缩法，还可转化为占位插I 空模型处理练习题10人身高各不相等,排成前后排，每排5人，要 求从左至右身高逐渐增加，共有多少排法？J 10五重排问题求幕策略止例5 把6名实习生分配到7个车间实习共有 多少种不同的分法Cl解:完成此事共分六步:把第一名实习生分配 到车间有2种分法.把第二名实习生分配 到车间也W7种分法，依此类推，由分步计粧许賣踊韵IJ问題的特点是叹元素为研究 对象，元素不受位置的约束，可以

8、逐一安排 各个元素的位般地n不同的元素没有限 制地安排在m个位置上的排列数为练习题1.某班新年联欢会原定的5个节目已排成节 目单，开演前又增加了两个新节目如果将这 两个节目插入原节目单中，那么不同插法的 种数为（42 ）2.某8层大楼一楼电梯上来8名乘客人，他们 到各自的一层下电梯，下电梯的方法（T ）六.环排问题线排策略例6. 5人围桌而坐，共有多少种坐法？解：围桌而坐与坐成一排的不同点在于，坐成 圆形没有首尾之分，所以固定一人A并从 此位置把圆形展成直线其余4人共有 种排法即（5-1）!一般地.n个不同元素作E形排 列，共有（n-D!种排法如果 从n个不同元素中取岀m个元素 作圆形排列共有

9、i A：练习题6颗颜色不同的钻石，可穿成几种钻石圈60要考虑“钻石圈”可以翻转的特点设六颗颜色不同的钻石为a,b,c d,e,f与围桌 而坐情形不同点是abcdef与f,edc,b,a在 围桌而坐中是两种排法，即在钻石圈中只 是一种排法，即把钻石圈翻到一边,所求数 为：(61)!/2=60七多排问题直排策略例78人排成前后两排，每排4人，其中甲乙在 前排，丁在后排共有多少排法解人排前后两排，相当于8人坐8把椅子，可以 把椅子排成一排先在前4个位置排甲乙两 个特殊元素有种，再排后4个位置上的 無廉元素有种其空的5人在5个位置 上任意排列有种，则共有丄辿种一般地，元素分成多排的排列问题, 可归结为

10、一排考虑，再分段研究.练习题nrnr有两排座位，前排11个座位，后排12个座位，现 安排2人就座规定前排中间的3个座位不能坐，并 且这2人不左右相邻，那么不同排法的种数是346甲乙都在前排：1、都在左面4个座位A；x3=6种2、都在右面4个座位同上，6种3、分列在中间3个的左右/1Jx4x4=32种共6+6+32=44种甲乙都在后排：A(22)*( 10+9+8+7+6+5+4+3+2+1 )=110种甲乙分列在前后两排A(22)*!2*8=192种共44+110+192=346种八.排列组合混合问题先选后排策略例&有5个不同的小球装入4个不同的盒内, 每盒至少装一个球共有多少不同的装解:第%

11、从5个球中选出2个组成复合元共 有G种方法再把5个元素(包含一个复合 元素)装入4个不同的盒内有2：_种方法. 根据分步计数原理装球的方法共有鱼解决排列姐合混合问愿先选后排是量墓本 的昙思此法与相邻元素捆绑策略相似 I 阳？_ _练习题一个班有6名战士，其中正副班长各1人 现从中选4人完成四种不同的任务，每人 完成一种任务，且正副班长有且只有1人 参加则不同的选法有19 种U!Til九小集团问题先整体局部策珞例9用1,2, 3. 4, 5组成没有重复数字的五位数 其中恰有两个偶数夹1, 5这两个奇数之 间这样的五位数有多少个？:把1,5,2,4当作一个小集团与3排队 共有种排法，再排小集团内部

12、共有 A淀种排法,由分步计数原理共有 A加用种排洙wfTil小集团排列问题中，先整体后局部，再结合其它策略进行处理。1 计划展出10幅不同的画，其中1幅水彩画,4 幅油画,5幅国画，排成一行陈列，要求同一 品种的必须连在一起，并且水彩画不在两 端，那么共有陈列方式的种数为仝込ITil2. 5男生和5女生站成一排照像9男生相邻，女 生也相邻的排法有血丄种十元素相同问题隔板策略TilStTil91例10有10个运动员名额，在分给7个班，每 班至少一个,有多少种分配方案？ 因为W个名额没有差别，把它们排成 一排。相邻名额之间形成9个空隙。 在9个空档中选6个位置插个隔板， 可把名额分成7份，对应地分

13、给7个 班级每一种插梅冇法对应一种分法 将n个相W的元素分成份（n, 为正#数）. I每份至少一个元素可以用H块購板.#入 个元素排成一排的rH个空障中，所分法数 为C练习题1. 10个相同的球装5个盒中每盒至少一 有多少装法？2 .x+y+z+w=100求这个方程组的自然数解 的组数cL十一.正难则反总体淘汰策略例11从0,123456亿&9这十个数字中取出三 个数，使其和为不小于10的偶数，不同的 取法有多少种？解：这i弓题中如果直接求不小于10的偶数很 困难，可用总体淘汰法。这十个数字中有5 个偶数5个奇数所取的三个数含有3个偶 数的取法有只含有1个偶数的取法 亠 CCi亠4亠有些排列组

14、合问甌正面直接考虑比较复杂. 両它的反面往往比较简捷可以先求岀它的 反面再从S体中海汰.练习题我们班里有43位同学，从中任抽5人，正、 副班长、团支部书记至少有一人在内的 抽法有多少种？ c2-c：十二.平均分组问题除法策略例12. 6本不同的书平均分成3堆，每堆2本共有 多少分法？ 2 ,解:分三步取书得GC；C；种方法，但这里出现 重复计数的现象,不妨记6本书为ABCDEF 若第一步取AB,第二步取CD,第三步取EF 该分法记为（AB,CD,EF）,则CCC中还有 （AB，EF,CD）,（CD,AB,EF）,（CD，EF，AB） I/W M J i a彎 III J n J J Id, 口

15、I*肿情况，所以分组后要一定要除以 人n为均 I分的组数）避免靈复计数。”例h有12人。按照下列要求分配.求不同的 分法种数。分为三组，一组5人，一组4人，一组3人；甲组5人，乙组4人,一组5人，一组4人，一组3人; 每组4人； 分为甲、乙、丙三组，丙组3人； 分为甲、乙、丙三组， 分为甲、乙、丙三组， 分为三组，每组4人 分成三组，其中一组2人，另外两组都是5人.答案GfCJ心 CJCJC，CjCJy：AJ C JC J心 阳啊心 cjAj21、结：练习I说明了非平均分配、平均分配以及部分平 均分配问题1.非平均分配问题中，没有给出组名与给出 组名是一样的，可以直接分步求；给出了组名 而没指

16、明哪组是几个，可以在没有给出组名 （或给出组名但不指明各组多少个）种数的 基础上乘以组数的全排列数2平均分配问题中，给出组名的分步求；若没给出组名的, 一定要在给出组名的基础上除以组数的全排列数3部分平均分配问题中，先考虑不平均分配，剩下的就是 平均分配.这样分配问题就解决了.结论：给出组名（非平均中未指明 各组个数）的要在未给出组名的种 数的基础上，乘以组数的阶乘1将13个球队分成3组T组5个队，其它两组4 个队,有多少分法？ CCjCA；2.10名学生分成3组，其中一组4人，另两组3人 但正副班长不能分在同一组有多少种不同 的分组方法（1540）3某校高二年级共有六个班级，现从外地转 入4

17、名学生，要安排到该年级的两个班级且每 班安排2名，则不同的安排方案种数为十三.合理分类与分步策略例13在一次演唱会上共10名演员，其中8人能 能唱歌 5人会跳舞现要演出一个2人 唱歌2人伴舞的节目，有多少选派方法？ 解:10演员中有5人只会唱歌，2人只会跳舞 3人为全能演员。以只会唱歌的5人是否 选上唱歌人员为标准进行研究只会唱 的5人中没有人选上唱歌人员共有 种，只会唱的5人中只有1人选上唱歌人 员C C C种.只会唱的5人中只有2人 选上唱歌人员有心种，由分类计数 原理共有 广种。本题还有如下分类标准：Yd*以3个全能演员是否选上唱歌人员为标准 *以3个全能演员是否选上跳算人员为标准 *以

18、只会跳算的2人是否选上跳算人员为标准 都可经得到正确结果列组合问题，可按元素 拠性质进行分类，按事件发生的连续过程分 涉，做到标准明确。分步层次清楚，不重不 帽，分类标准一旦确定要贯穿于解题过程的 怀终。练习题1.从4名男生和3名女生中选出4人参加某个座 谈会，若这4人中必须既有男生又有女生，则 不同的选法共有3423成人2小孩乘船游玩,1号船最多乘3人，2 号船最多乘2人,3号船只能乘1人，他们任选 2只船或3只船,但小孩不能单独乘一只船， 这3人共有多少乘船方法.27十四构造模型策略例14马路上有编号为1,2, 3, 4, 5, 6, 7, 8, 9的 九只路灯，现要关掉其中的3盏但不能关

19、 掉相邻的2盏或3盏，也不能关掉两端的2 盏,求满足条件的关灯方法有多少种？ 解：把此问题当作一个排队模型在6盏 亮灯的5个空隙中插入3个不亮的灯E常熟悉的模型，如占位填空模型，排队 莫型，装盒模型等，可使问题直观解决练习题某排共有w个座位，若4人就坐，每人左右 两边都有空位，那么不同的坐法有多少种?120十五实际操作穷举策略例15设有编号1.2, 3, 4. 5的五个球和编号1,2 3, 4, 5的五个盒子现将5个球投入这五 个盒子内要求每个盒子放一个球，并且 恰好有两个球的编号与盒子的编号相同,- 有多少投法.解：从5个球中取出2个与盒子对号有工种 还剩下3球3盒序号不能对应，利用实际 操

20、作法，如果剩下345号球,3,4,5号盒 3号球装4号盒时，贝14号5号球有只有1种 装法in Lft Lft3号盒4号盒 5号盒十五实际操作穷举策略例15设有编号1.2, 3, 4. 5的五个球和编号1,2 3, 4, 5的五个盒子，现将5个球投入这五 个盒子内要求每个盒子放一个球，并且 恰好有两个球的编号与盒子的编号相同,- 有多少投法.解：从5个球中取出2个与盒子对号有工种 还剩下3球3盒序号不能对应，利用实际 操作法，如果剩下345号球,3,4,5号盒 3号球装4号盒时，贝14号5号球有只有1种 装法，同理3号球装5号盒时45号球有也 只有1种装法，由分步计数原理有2C种対于务件比较夏祭的禅列纽台问;额，不易用 么式诳行运寡，往往利用穷举法或画出树状 图乞收到意想不到的结弟练习题则四张(9)Til1.同一寝室4人，每人写一张贺年卡集中起来, 然后每人各拿一张别人的贺年卡， 贺年卡不同的分配方式有多少种？42 给图中区域涂色，要求相邻区 域不同色，现有4种可选颜色，则 不同的着色方法有墓种十六.分解与合成策略例1630030能被多少个不同的偶数整除 分析：先把30030分解成质因数的乘积形式 30030=2X3X5 X 7 X11X13依题 意可知偶因数必先取2,再从其余5个 因