10.3组合(3-4)组合中的分堆与隔板问题-

排列组合中的分堆与隔板问题一.平均分组问题理论部分：平均分成的组，不管它们的顺序如何，都是一种情况，所以分组后要除以，即m!，其中m表示组数。例如把abcd分成平均两组abcdacbdadbc有_____多少种分法？C42C22A223cdbdbcadacab这两个在分组时只能算一个mmA1：均分不安排工作的问题例1：12本不同的书（1）按4∶4∶4平均分成三堆有多少种不同的分法？（2）按2∶2∶2∶6分成四堆有多少种不同的分法？C102C82A33C122C66(2)C84C44A33C12412!4!·8!8!4!·4!13!(1)5775例2：（1）6本不同的书按2∶2∶2平均分给甲、乙、丙三个人，有多少种不同的分法？方法：先分再排法。分成的组数看成元素的个数·(1)C42C22A33C62A33C42C22C62（2）12支笔按3：3：2：2：2分给A、B、C、D、E五个人有多少种不同的分法？C93C62A33C123C42(2)A22C22A55练习1：12本不同的书平均分成四组有多少种不同分法？44333639312ACCCC2：10本不同的书（1）按2∶2∶2∶4分成四堆有多少种不同的分法？（2）按2∶2∶2∶4分给甲、乙、丙、丁四个人有多少种不同的分法？443344262821033442628210C)2(ACCCC(1)AACCC二.非均分组问题例1.（1）6本不同的书按1∶2∶3分成三堆有多少种不同的分法？（2）按1∶2∶3分给甲、乙、丙三个人有多少种不同的分法？注意：（1）分组后无序问题（2）分组后有序问题。33332516332516ACCC)2(CCC)1(例2.有六本不同的书分给甲、乙、丙三名同学，按下条件，各有多少种不同的分法？（1）每人各得两本；（2）甲得一本，乙得两本，丙得三本；（3）一人一本，一人两本，一人三本；（4）甲得四本，乙得一本，丙得一本；（5）一人四本，另两人各一本·(3)(4)(5)C52C33C61A33C52C33C61C21C11C64A31C21C11C64(2)C42C22C62(1)练习12本不同的书分给甲、乙、丙三人按下列条件，各有多少种不同的分法？（1）一人三本，一人四本，一人五本；（2）甲三本，乙四本，丙五本；（3）甲两本，乙、丙各五本；（4）一人两本，另两人各五本·C94C55C123(1)(2)(3)(4)A33C94C55C123C105C55C122A31C105C55C122练习:1、12名同学分别到不同的路口进行车流量的调查,若每个路口4人,则不同的分配方案共有（）A、4448412CCCB、44484123CCC3348412CCC334448412ACCCC、D、A2、已知集合｛1,2,3,4,5,6,7,8,9｝,其中含五个元素且至少有2个偶数的子集有（）A、275个B、7200个C、105个D、1200个3、3名医生和6名护士,被分配到3所学校为学生体检,每校分配1名医生和2名护士,不同的分配方案有（）种A、90B、180C、720D、540CD2、可以分三类：（1）恰有2个偶数，3个奇数（3）恰有4个偶数，1个奇数（2）恰有3个偶数，2个奇数603524CC402534CC51544CC3、可以分3大步6小步：540221124122613CCCCCC作业：例1、9件不同的玩具，按下列分配方案各有多少种不同的分法？（2）一人得2件，一人得3件，一人得4件（3）每人得3件（1）甲得2件，乙得3件，丙得4件（4）平均分成3堆（5）分成2,2,2,3四堆例2、把6位实习教师全部分到5个班级进行实习，每班至少一人，有多少种不同的分法？1将13个球队分成3组,一组5个队,其它两组各4个队,有多少分法？544138422CCCA2.某校高二年级共有六个班级，现从外地转入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为______2226422290ACCA三.元素相同问题隔板策略例3.有10个运动员名额，在分给7个班，每班至少一个,有多少种分配方案？解：因为10个名额没有差别，把它们排成一排。相邻名额之间形成９个空隙。在９个空档中选６个位置插个隔板，可把名额分成７份，对应地分给７个班级，每一种插板方法对应一种分法共有___________种分法。一班二班三班四班五班六班七班69C将n个相同的元素分到m个容器中（n，m为正整数）,每个容器中至少一个元素,有多少种分法.其解题原理是把n个元素排成一列,在它们中间的n-1个空位中,选取m-1个空位插入m-1块隔板，把n个元素分成m个部分,共有11mnC1、将7本相同的练习簿发给4名同学，每人至少一本，有多少种不同的分法？2、方程有多少组正整数解？1004321xxxx3、圆周上有个等分点，以其中三个点为顶点的直角三角形有多少个？)1(2nn4、圆上有个点，以这个点为端点的弦在圆的内部最多有多少个交点？)4(nnn5、在不相交的两条线段上分别有m,n个点，以这些点为端点的线段之间最多有多少个不同的交点？ba,练习例4.把6个相同的乒乓球任意分放到4个球箱中,共有多少种放法?解:由于是任意分放,所以一个球箱放0,1,….6个球都有可能.如果分类讨论,情况很复杂.我们可以这样考虑,从每个球箱中借出一个乒乓球(不管原来箱中是否有乒乓球),也就是相当于先分给每个球箱-1个球.这样问题就转化为:把10个乒乓球分放到4个球箱中,每个箱子至少一个共有多少中分法可以转化为隔板法练习：将10个相同的小球装入3个编号分别为1,2,3的盒子（要装完），要求盒子里的球的个数不少于盒子的编号数，共有多少种不同的装法？例5、（1）10个优秀指标分配给6个班级，每个班级至少一个，共有多少种不同的分配方法？（2）10个优秀指标分配到一、二、三3个班，若名额数不少于班级序号数，共有多少种不同的分配方法？分析：（1）这是同种元素的“不平均分组”问题.本小题可构造数学模型，用5个隔板插入10个指标中的9个空隙，即有种方法。按照第一个隔板前的指标数为1班的指标，第一个隔板与第二个隔板之间的指标数为2班的指标，以此类推，因此共有种分法.59C59C=126例題講解：（2）先拿3个指标分给二班1个，三班2个，然后，问题转化为7个优秀指标分给三个班，每班至少一个.由（1）可知共有种分法26C=15例題講解：例4．马路上有编号为1，2，3，…，10的十盏路灯，为节约用电又不影响照明，可以把其中3盏灯关掉，但不可以同时关掉相邻的两盏或三盏，在两端的灯都不能关掉的情况下，有多少种不同的关灯方法？解：（插空法）本题等价于在7只亮着的路灯之间的6个空档中插入3只熄掉的灯，故所求方法总数为种方法36C=20插档法：典型例题1.4名优等生被保送到3所学校，每所学校至少得1名，则不同的保送方案总数为（）。（A)36(B)24(C)12(D)62.若把英语单词“error”中字母的拼写顺序写错了，则可能出现的错误的种数是（）（A)20(B)19(C)10(D)693.小于50000且含有两个5，而其它数字不重复的五位数有（）个。（A)(B)(C)(D)282414CCC282414ACC442814ACC282414AAAABB2343CA3252C1A练习3.15人按照下列要求分配，求不同的分法种数。(1)分为三组，每组5人,共有______________种不同的分法。（2）分为甲、乙、丙三组，一组7人，另两组各4人，共有___________________种不同的分法。（3）分为甲、乙、丙三组，一组6人，一组5人，一组4人，共有___________________种不同的分法。4.8名同学选出4名站成一排照相，其中甲、乙两人都不站中间两位的排法有______________________种。5.某班有27名男生13女生，要各选3人组成班委会和团支部每队3人，3人中2男1女，共有_____________________种不同的选法。3355510515/ACCC22334448715/AACCC334459615ACCC222226331237124446AACAACCAC221224213427ACCCC作业与练习•作业：习题10.38、9、10、11题