排列组合常见的九种方法

《排列组合常见的九种方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复习巩固1.分类计数原理(加法原理)完成一件事，有n类办法，在第1类办法中有m种不同的方法，在1第2类办法中有m种不同的方法，…，在第n类办法中有m种不2n同的方法，那么完成这件事共有：NmmLm12n种不同的方法．2.分步计数原理（乘法原理）完成一件事，需要分成n个步骤，做第1步有m种不同的方法，做1第2步有m种不同的方法，…，做第n步有m种不同的方法，那2n么完成这件事共有：NmmLm12n种不同的方法．3.分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理

2、各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件．一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数.解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素131C4A4C3占了这两个位置.先排末位共有1C3然后排首位共有1C4最后排其它位置共有3A4由分步计数原理得113CCA288434练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？二.相邻元素捆绑策略例2.7人站成一排,其中甲乙相邻且丙丁相邻,共有

3、多少种不同的排法.解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有522种不同AAA480522的排法甲乙丙丁练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为20三.不相邻问题插空策略例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？练习题：1、某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两

4、个新节目不相邻，那么不同插法的种数为302、某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为20四.定序问题倍缩空位插入策略例4.7人排队,其中甲乙丙3人顺序一定共有多少不同的排法解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数,则共有不同排法种数是：73A/A73(空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有4种A7方法，其余的三个位置甲乙丙共有1种坐法，则共有4种方法。A7思考:可以先让甲乙丙就坐吗?（插入法)先排甲乙

5、丙三个人,共有1种排法,再把其余4四人依次插入共有方法定序问题可以用倍缩法，还可转化为占位插空模型处理练习题:10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？5C10五.重复排列问题求幂策略解决“允许重复排列问题”要注意区分两类元素：一类元素可以重复，另一类不能重复再利用乘法原理直接求解.例21.七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有.例5.把6名实习生(元素)分配到7个车间(位置)实习,共有多少种不同的分法六.元素相同问题隔板策略例10.有十10个运动员名额，分给

6、7个班，每班至少一个,有多少种分配方案？(注意有9个空隙,6个隔板!)解：因为10个名额没有差别，把它们排成一排。相邻名额之间形成９个空隙。在９个空档中选６个位置插个隔板，可把名额分成７份，对应地分给７个班级，每一种插板方法对应一种分法共有6种分法。C9一二三四五六七班班班班班班班将n个相同的元素分成m份（n，m为正整数）,每份至少一个元素,可以用m-1块隔板，m1插入n个元素排成一排的n-1个空隙中，所有分法数为Cn1练习题：1．10个相同的球装5个盒中,每盒至少一有多少装法？4C92.求这个方程组的自然数解的组数3xy

7、zw100C103七.正难则反总体淘汰策略例11.从0,1,2,3,4,5,6,7,8,9这十个数字中取出三个数，使其和为不小于10的偶数,不同的取法有多少种？解：这问题中如果直接求不小于10的偶数很困难,可用总体淘汰法。这十个数字中有5个偶数5个奇数,所取的三个数含有3个偶数的取法有3,只含有1个偶数的取法有12,和为偶数的CCC555取法共有123。再淘汰和小于10的偶数共9种，符合条件CCC555的取法共有123CCC9555练习题：我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法

8、有多少种?八.平均分组问题除法策略例12.6本不同的书平均分成3堆,每堆2本共有多少分法？解:分三步取书得222种方法,但这里出现重复计数的现象,不CCC642妨记6本书为ABCDEF，若第一步取AB,第二步取CD,第三步取EF该分法记为(AB,CD,EF),则