组合的综合应用

第一章计数原理§3组合第2课时组合的综合应用有限制条件的组合问题•在一次数学竞赛中，某学校有12人通过了初试，学校要从中选出5人去参加市级培训，在下列条件下，有多少种不同的选法？•(1)任意选5人；•(2)甲、乙、丙三人必须参加；•(3)甲、乙、丙三人不能参加；•(4)甲、乙、丙三人只能有1人参加．解：(1)C512＝792种不同的选法．(2)甲、乙、丙三人必须参加，只需从另外的9人中选2人，共有C29＝36种不同的选法．(3)甲、乙、丙三人不能参加，只需从另外的9人中选5人，共有C59＝126种不同的选法．(4)甲、乙、丙三人只能有1人参加，分两步，先从甲、乙、丙中选1人，有C13种选法，再从另外的9人中选4人有C49种选法．共有C13C49＝378种不同的选法．若本例条件不变，那么“甲、乙、丙三人至少1人参加”有多少种？解：(直接法)可分为三类．第一类：甲、乙、丙中有1人参加，共有C13C49＝378种；第二类：甲、乙、丙中有2人参加，共有C23C39＝252种；第三类：甲、乙、丙中有3人参加，共有C33C29＝36种．共有C13C49＋C23C39＋C33C29＝666种不同的选法．(间接法)12人中任意选5人共有C512种，甲、乙、丙三人不能参加的有C59种，所以，共有C512－C59＝666种不同的选法．•1．(1)某校开设9门课程供学生选修，其中A，B，C三门由于上课时间相同，至多选一门．学校规定，每名同学选修4门，共有________种不同选修方案(用数字作答)．•(2)某班级要从4名男生2名女生中选派4人参加某次社区服务，如果要求至少有1名女生，那么不同的选派方案种数为()•A．14B．24•C．28D．48解析：(1)这里A，B，C三门课程“至多选一门”，即A，B，C三门课程都不选，或A，B，C这三门课程恰好选一门．分两类完成：第1类，A，B，C三门课程都不选，有C46种不同选修方案；第2类，A，B，C三门课程恰好选修一门，有C13·C36种不同选修方案．故共有C46＋C13·C36＝75种不同的选修方案．(2)这里“至少有1名女生”，即“恰好有1名女生”或“有2名女生”．方法一分两类完成：第1类，选派1名女生，3名男生，有C12·C34种选派方案；第2类，选派2名女生，2名男生，有C22·C24种选派方案．共有C12·C34＋C22·C24＝14种不同的选派方案．故选A．方法二(间接法)6人中选派4人的组合数为C46，其中都选男生的组合数为C44.所以至少有1名女生的选派方案有C46－C44＝14种．故选A．•答案：(1)75(2)A与几何有关的组合应用题•平面内有12个点，其中有4个点共线，此外再无任何3点共线．以这些点为顶点，可构成多少个不同的三角形？•解：方法一以从共线的4个点中取点的多少作为分类的标准．•第一类：共线的4个点中有2个点为三角形的顶点，共有CC＝48个不同的三角形；•第二类：共线的4个点中有1个点为三角形的顶点，共有CC＝112个不同的三角形；第三类：共线的4个点中没有点为三角形的顶点，共有C38＝56个不同的三角形．由分类加法计数原理知，不同的三角形共有48＋112＋56＝216个．方法二(间接法)从12个点中任意取3个点，有C312＝220种取法，而在共线的4个点中任意取3个均不能构成三角形，即不能构成三角形的情况有C34＝4种．故这12个点构成三角形的个数为C312－C34＝216．•2．如果一个凸多面体是n棱锥，那么这个凸多面体的所有顶点所确定的直线共有________条．这些直线中共有f(n)对异面直线，则f(4)＝________；f(n)＝________(答案用数字或n的解析式表示)．解析：n棱锥共n＋1个顶点，依两点确定一条直线，有C2n＋1＝nn＋12条直线．•f(4)表示四棱锥中的异面直线的对数，如图，每条侧棱和底面上不共顶点的两条底边、一条对角线共形成3对异面直线，即f(4)＝4×3＝12(对)；同理，一条侧棱与底面上n－2条底边异面，又与C2n－1－(n－1)＋1条底面对角线异面，即与这条侧棱异面的直线有C2n－1－(n－1)＋1＋(n－2)＝C2n－1＝n－1n－22条，故n条侧棱形成的异面直线的对数f(n)＝nn－1n－22.答案：nn＋1212nn－1n－22•6个相同的小球放入4个编号为1,2,3,4的盒子，求下列方法的种数．•(1)每个盒子都不空；•(2)恰有一个空盒子；•(3)恰有两个空盒子．相同元素分配问题解：(1)先把6个相同的小球排成一行，在首尾两球外侧放置一块隔板，然后在小球之间5个空隙中任选3个空隙各插一块隔板，有C35＝10种．(2)恰有一个空盒子，插板分两步进行．先在首尾两球外侧放置一块隔板，并在5个空隙中任选2个空隙各插一块隔板，如|0|000|00|，有C25种插法，然后将剩下的一块隔板与前面任意一块并放形成空盒，如|0|000||00|，有C14种插法，故共有C25·C14＝40种．(3)恰有两个空盒子，插板分两步进行．先在首尾两球外侧放置一块隔板，并在5个空隙中任选1个空隙插一块隔板，有C15种插法，如|00|0000|，然后将剩下的两块隔板插入形成空盒．①这两块板与前面三块板形成不相邻的两个盒子，如||00||0000|，有C23种插法；②将两块板与前面三块板之一并放，如|00|||0000|，有C13种插法．故共有C15·(C23＋C13)＝30种．•3．某同学有同样的画册2本，同样的集邮册3本，从中取出4本赠送给4位朋友，每位朋友1本，则不同的赠送方法共有()•A．4种B．10种•C．18种D．20种解析：第一类，当剩余的一本是画册时，相当于把3本相同的集邮册和1本画册分给4位朋友，只有1位朋友得到画册．即把4位朋友分成人数为1,3的两队，有1个元素的那队分给画册，另一队分给集邮册，有C14种分法．第二类，当剩余的一本是集邮册时，相当于把2本相同的画册和2本相同的集邮册分给4位朋友，有2位朋友得到画册，即把4位朋友分成人数为2,2的两队，一队分给画册，另一队分给集邮册，有C24种分法．因此，满足题意的赠送方法共有C14＋C24＝4＋6＝10种.•答案：B有6本不同的书，按照以下要求处理，各有几种分法？(1)平均分给甲、乙、丙三人；(2)甲得1本，乙得2本，丙得3本；(3)一人得1本，一人得2本，一人得3本；(4)平均分成三堆(组)；(5)一堆1本，一堆2本，一堆3本．分配问题[分析](1)、(2)两题可设想甲、乙、丙三人依次如数取书；(3)则在(2)的基础上甲、乙、丙三人全排列分配；由等概率思想，(4)为(1)的A33分一；(5)为(3)的A33分之一．[解析](1)每人得2本，可考虑甲先在6本书中任取2本，取法有C26种，再由乙在余下的书中取2本，取法有C24种，最后由丙取余下的2本书，有C22种取法，由分步计数原理．所以共有分法数：N＝C26C24C22＝90.所以一共有90种取法．(2)选取方法同(1)，所以共有分法数N＝C16C25C33＝60.所以一共有60种取法．(3)在(2)中甲得1本，乙得2本，丙得3本的基础上，考虑到甲、乙、丙三人的平等地位，让甲、乙、丙三人全排列调换位置，所以共有分法数：N＝C16C23C33·A33＝360.所以一共有360种选法．(4)由于三堆的位置并无差别，可在(1)的情况下，得共有分法数为：N＝C26·C24C22A33＝15.所以一共有15种分法．(5)类似(4)与(1)，考虑本题与(3)的差别，所以共有分法数：N＝C16C25C33＝60(种)．所以一共有60种分法．•现有5名学生要进入某工厂的四个车间去实习，每个车间至多去2人，有多少种不同的方法？•[解析]本例要求5个人去四个车间，每个车间至多去2人，但是并没有强调每个车间必须去几人，因此，本例可分为如下两类：有一个车间去2人，其余三个车间各去1人，或者，有两个车间各去2人，一个车间去1人，一个车间不去人．•依题意，至少有一个车间去2人，至多有两个车间各去2人，因此，实习方案可分为两类：第一类：有一个车间去2人，其余三个车间各去1人，所以，先在5个人中任选2人去一个车间，有C25种方法；将此2人看做1个元素，连同其余3个人，共4个元素分别到四个车间，有A44种方法，∴共有C25·A44＝240种．第二类：有两个车间各去2个人，一个车间去1个人，一个车间不去人，因此，先在5个人中确定1个人去一个车间，并在四个车间中选一个车间插入此人，有C15·C14种方法；然后在其余4个人中选2人到一个车间，另2人则自然到另一车间，并在剩下的三个车间中选两个车间来安排他们，有C24·C22·C23种方法，∴共有C15·C14·C24·C22·C23＝360种方法．由分类加法计数原理可知，所求方法共有240＋360＝600种．•1．“含”与“不含”问题：这类问题的解题思路是将限制条件视为特殊元素和特殊位置，一般来讲，特殊要先满足，其余则“一视同仁”．若正面入手不易，则从反面入手，寻找问题的突破口，即采用排除法．解题时要注意分清“有且仅有”“至多”“至少”“全是”“都不是”“不都是”等词语的确切含义，准确把握分类标准．2．几何中的计算问题：在处理几何问题中的组合应用问题时，应先明确几何中的点、线、面及构型，明确平面图形和立体图形中的点、线、面之间的关系，将几何问题抽象成组合问题来解决．3．相同元素分配问题常用隔板法，即：将n个相同的元素分给m个不同的对象(n≥m)，有Cm－1n－1种方法．可描述为n－1个空中插入m－1块板．