带有约束条件的排列组合问题

会计学1带有约束条件的排列组合问题在一次数学竞赛中，某学校有12人通过了初试，学校要从中选出5人去参加市级培训，在下列条件下，有多少种不同的选法？(1)任意选5人；一题多变(2)甲、乙、丙三人必须参加；(3)甲、乙、丙三人不能参加；第1页/共70页在一次数学竞赛中，某学校有12人通过了初试，学校要从中选出5人去参加市级培训，在下列条件下，有多少种不同的选法？(4)甲、乙、丙三人只能有1人参加；一题多变第2页/共70页在一次数学竞赛中，某学校有12人通过了初试，学校要从中选出5人去参加市级培训，在下列条件下，有多少种不同的选法？(5)甲、乙、丙三人至少1人参加．一题多变第3页/共70页排列组合中的分组分配问题一、提出分组与分配问题，澄清模糊概念n个不同元素按照某些条件分配给k个不同得对象，称为分配问题，分定向分配和不定向分配两种问题；将n个不同元素按照某些条件分成k组，称为分组问题.分组问题有不平均分组、平均分组、和部分平均分组三种情况。分组问题和分配问题是有区别的，前者组与组之间只要元素个数相同是不区分的；而后者即使2组元素个数相同，但因对象不同，仍然是可区分的.对于后者必须先分组后排列。第4页/共70页二、基本的分组问题

例1六本不同的书，分为三组，求在下列条件下各有多少种不同的分配方法？

(1)每组两本.

(2)一组一本，一组二本，一组三本.

(3)一组四本，另外两组各一本.第5页/共70页三、基本的分配的问题(一)定向分配问题例2六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1)甲两本、乙两本、丙两本.(2)甲一本、乙两本、丙三本.(3)甲四本、乙一本、丙一本.第6页/共70页(二)不定向分配问题例3六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1)每人两本.(2)一人一本、一人两本、一人三本.(3)一人四本、一人一本、一人一本.第7页/共70页在今年国家公务员录用中，某市农业局准备录用文秘人员二名、农业企业管理人员和农业法制管理人员各一名，报考农业局公务人员的考生有10人，则可能出现的录用情况有____种.解法1:解法2:第8页/共70页马路上有编号为1，2，3，…，10的十盏路灯，为节约用电又不影响照明，可以把其中3盏灯关掉，但不可以同时关掉相邻的两盏或三盏，在两端的灯都不能关掉的情况下，有多少种不同的关灯方法？解：（插空法）本题等价于在7只亮着的路灯之间的6个空档中插入3只熄掉的灯，故所求方法总数为种方法插空法第9页/共70页某城新建的一条道路上有12只路灯，为了节省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有（）（A）种（B）种（C）种（D）种A插空法第10页/共70页例4.有10个运动员名额，再分给7个班，每班至少一个,有多少种分配方案？

解：因为10个名额没有差别，把它们排成一排。相邻名额之间形成９个空隙。在９个空档中选６个位置插个隔板，可把名额分成７份，对应地分给７个班级，每一种插板方法对应一种分法共有___________种分法。一班二班三班四班五班六班七班将n个相同的元素分成m份（n，m为正整数）,每份至少一个元素,可以用m-1块隔板，插入n个元素排成一排的n-1个空隙中，所有分法数为隔板法第11页/共70页10个优秀指标分配给6个班级，每个班级至少一个，共有多少种不同的分配方法？分析：（1）这是同种元素的“不平均分组”问题.本小题可构造数学模型，用5个隔板插入10个指标中的9个空隙，即有种方法。按照第一个隔板前的指标数为1班的指标，第一个隔板与第二个隔板之间的指标数为2班的指标，以此类推，因此共有种分法.隔板法第12页/共70页例7、从6个学校中选出30名学生参加数学竞赛,每校至少有1人,这样有几种选法?分析:问题相当于把个30相同球放入6个不同盒子(盒子不能空的)有几种放法?这类问可用“隔板法”处理.解:采用“隔板法”得:隔板法第13页/共70页混合问题，先“组”后“排”对某种产品的6件不同的正品和4件不同的次品,一一进行测试，至区分出所有次品为止，若所有次品恰好在第5次测试时全部发现,则这样的测试方法有种可能？解：由题意知前5次测试恰有4次测到次品，且第5次测试是次品。故有：种可能。次1正3次第14页/共70页练习：1、某学习小组有5个男生3个女生，从中选3名男生和1名女生参加三项竞赛活动，每项活动至少有1人参加，则有不同参赛方法______种.解：采用先组后排方法:2、3名医生和6名护士被分配到3所学校为学生体检,每校分配1名医生和2名护士,不同的分配方法共有多少种?解法一：先组队后分校（先分堆后分配）解法二：依次确定到第一、第二、第三所学校去的医生和护士.混合问题，先“组”后“排”第15页/共70页例3:

4名男生5名女生，一共9名实习生分配到高一的四个班级担任见习班主任，每班至少有男、女实习生各1名的不同分配方案共有多少种？

解：由题意可知，有且仅有2名女生要分在同一个班，混合问题，先“组”后“排”第16页/共70页例7、有翻译人员11名，其中5名仅通英语、4名仅通法语，还有2名英、法语皆通。现欲从中选出8名，其中4名译英语，另外4名译法语，一共可列多少张不同的名单？多面手问题第17页/共70页例5.

有12名划船运动员,其中3人只会划左舷,4人只会划右舷,其它5人既会划左舷,又会划右舷,现要从这12名运动员中选出6人平均分在左右舷参加划船比赛,有多少种不同的选法?多面手问题分析：设集合A={只会划左舷的3个人}，B={只会划右舷的4个人}，C={既会划左舷又会划右舷的5个人}先分类，以集合A为基准，划左舷的3个人中，有以下几类情况：①A中有3人；②A中有2人；C中有1人；③A中有1人，C中有2人；④C中有3人。第①类，划左舷的人已选定，划右舷的人可以在B,C中选3人，有种,以下类同第18页/共70页例8、10双互不相同的鞋子混装在一只口袋中，从中任意取出4只，试求满足如下条件各有多少种情况：（1）4只鞋子恰有两双；(1)因为4只鞋来自2双鞋,所以有组对问题第19页/共70页例8、10双互不相同的鞋子混装在一只口袋中，从中任意取出4只，试求满足如下条件各有多少种情况：（2）4只鞋子没有成双的；(2)因为4只鞋来自4双不同的鞋,而从10双鞋中取4双有种方法,每双鞋中可取左边一只也可取右边一只,各有种取法,所以一共有种取法.第20页/共70页例8、10双互不相同的鞋子混装在一只口袋中，从中任意取出4只，试求满足如下条件各有多少种情况：（3）4只鞋子只有一双。(3)因为4只鞋来自3双鞋,而从10双鞋中取3双有种取法,3双鞋中取出1双有种方法,另2双鞋中各取1只有种方法故共有种取法.第21页/共70页8双互不相同的鞋子混装在一只口袋中，从中任意取出4只，试求满足如下条件各有多少种情况：（1）4只鞋子恰有两双；（2）4只鞋子没有成双的；（3）4只鞋子只有一双。第22页/共70页注意区别“恰好”与“至少”例2

从6双不同颜色的手套中任取4只，其中恰好有一双同色的手套的不同取法共有（）

(A)480种（B）240种（C）180种（D）120种小结：“恰好有一个”是“只有一个”的意思。“至少有一个”则是“有一个或一个以上”，可用分类讨论法求解，它也是“没有一个”的反面，故可用“排除法”。解：第23页/共70页练习:从6双不同颜色的手套中任取4只，其中至少有一双同色手套的不同取法共有____种解：第24页/共70页第25页/共70页把握分类原理、分步原理是基础例1、如图，某电子器件是由三个电阻组成的回路,其中有6个焊接点A，B，C，D，E，F，如果某个焊接点脱落，整个电路就会不通。现发现电路不通了,那么焊接点脱落的可能性共有（）

(A)63种（B）64种（C）6种（D）36种分析:由加法原理可知由乘法原理可知2×2×2×2×2×2-1=63第26页/共70页特殊元素（或位置）优先安排例3将5列车停在5条不同的轨道上，其中a列车不停在第一轨道上，b列车不停在第二轨道上，那么不同的停放方法有（）（A）120种（B）96种（C）78种（D）72种解：练习3从7盆不同的盆花中选出5盆摆放在主席台前，其中有两盆花不宜摆放在正中间，则一共有_____种不同的摆放方法。解：C第27页/共70页“相邻”用“捆绑”，“不邻”就“插空”例4七人排成一排，甲、乙两人必须相邻，且甲、乙都不与丙相邻，则不同的排法有（）种960种（B）840种（C）720种（D）600种解：另解：小结：以元素相邻为附加条件的应把相邻元素视为一个整体，即采用“捆绑法”；以某些元素不能相邻为附加条件的,可采用“插空法”。“插空”有同时“插空”和有逐一“插空”,并要注意条件的限定.第28页/共70页8.九张卡片分别写着数字0，1，2，…，8，从中取出三张排成一排组成一个三位数，如果6可以当作9使用，问可以组成多少个三位数？解：可以分为两类情况：①若取出6，则有种方法；②若不取6，则有种方法，一共有+＝602种方法课堂练习：第29页/共70页例6：（1）平面内有9个点，其中4个点在一条直线上，此外没有3个点在一条直线上，过这9个点可确定多少条直线？可以作多少个三角形？（2）空间12个点，其中5个点共面，此外无任何4个点共面，这12个点可确定多少个不同的平面？第30页/共70页例8、某医院有内科医生12名，外科医生8名，现要派5人参加支边医疗队，至少要有1名内科医生和1名外科医生参加，有多少种选法？例9:某外语组有9人,每人至少会英语和日语中的一门,其中7人会英语,3人会日语,从中选出会英语与日语的各1人,有多少种不同的选法？解：由于7＋3=10＞9，所以9人中必有1人既会英语又会日语．(1)从只会英语的6人中选1人，只会日语的2人中选1人，有N1=6×2=12(2)既会英语又会日语的那位选定，其余8人中选1人，有N2=1×8=8由分类计数原理得N=N1+N2=20.选人问题：第31页/共70页课堂练习：2、从6位同学中选出4位参加一个座谈会，要求张、王两人中至多有一个人参加，则有不同的选法种数为

。3、要从8名男医生和7名女医生中选5人组成一个医疗队，如果其中至少有2名男医生和至少有2名女医生，则不同的选法种数为（）4、从7人中选出3人分别担任学习委员、宣传委员、体育委员，则甲、乙两人不都入选的不同选法种数共有（）1、把6个学生分到一个工厂的三个车间实习，每个车间2人，若甲必须分到一车间，乙和丙不能分到二车间，则不同的分法有

种。99CD第32页/共70页如图，某城市中，M、N两地有整齐的道路网，若规定只能向东或向北两个方向沿途中路线前进，则从M到N不同的走法共有（）

（A）25（B）15（C）13（D）10总共需6步到达，其中2步向北或者4步向东或B第33页/共70页5、如图,某市有7条南北向街道，5条东西向街道（每小方格均为正方形）（1）其中有多少个矩形？（2）其中有多少个正方形？（3）从A点到B点最短路线的走法有多少种？首先，只由一个小正方形组成的有7*4

由2*2小正方形组成的有6*3

由3*3小正方形组成的有5*2

由4*4小正方形组成的有4*1

所以7*4＋6*3＋5*2＋4*1=60第34页/共70页(1)以正方体的顶点为顶点，可以确定多少个四面体？(2)以正方体的顶点为顶点，可以确定多少个四棱锥？第35页/共70页排列与组合应用题的技巧汇总在解决一个实际问题的过程中，常常遇到排列、组合的综合性问题．而解决问题的第一步是审题，只有认真审题，才能把握问题的实质，分清是排列问题、组合问题，还是综合问题，分清分类与分步的标准和方式，并且要遵循两个原则：一是按元素的性质进行分类；二是按事情发生的过程进行分步．第36页/共70页解决排列组合应用题的常用方法：(1)合理分类，准确分步；(2)特殊优先，一般在后；(3)先取后排，间接排除；(4)集团捆绑，间隔插空；(5)抽象问题，构造模型；(6)均分除序，定序除序．第37页/共70页用数字1,2,3,4,5组成没有重复数字的五位数，则其中数字2,3相邻的偶数有________个．(用数字作答)例1【解析】

数字2和3相邻的偶数有两种情况．第一种情况，当数字2在个位上时，则3必定在十位上，此时这样的五位数共有6个；第二种情况，当数字4在个位上时，且2,3必须相邻，此时满足要求的五位数有AA＝12(个)，则一共有6＋12＝18(个)．【答案】

18【题后小结】

“个位”是特殊位置或“偶数数字”是特殊元素，应优先考虑．第38页/共70页从1,3,5,7,9五个数字中选2个，0,2,4,6,8五个数字中选3个，能组成多少个无重复数字的五位数？例2【题后小结】对于组合、排列的综合问题，一般采取先取元素后排列的方法．第39页/共70页某校高二年级共有六个班级，现从外地转入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为(

)A．80B．90C．100D．120例3【答案】

B【题后小结】本题是平均分组再分配问题．平均分组是组合数除以“组数”的排列数，分配就是排列．第40页/共70页2521440302402880

1.

2.第41页/共70页例5．（1）四个不同的小球放入四个不同的盒中，一共有多少种不同的放法？解：（1）根据分步计数原理：一共有种方法；（2）（捆绑法）第一步：从四个不同的小球中任取两个“捆绑”在一起看成一个元素有种方法；第二步：从四个不同的盒中任取三个将球放入有种方法，所以，一共有＝144种方法（2）四个不同的小球放入四个不同的盒中且恰有一个空盒的放法有多少种？第42页/共70页①分为三组，一组5人，一组4人，一组3人；②分为甲、乙、丙三组，甲组5人，乙组4人，丙组3人；③分为甲、乙、丙三组，一组5人，一组4人，一组3人；④分为甲、乙、丙三组，每组4人；⑤分为三组，每组4人。例1：12人按照下列要求分配，求不同的分法种数。答案①C125.C74.C33②C125.C74.C33③C125.C74.C33.A33④C124.C84.C44⑥分成三组，其中一组2人，另外两组都是5人。⑥C122.C105.C55A22⑤C124.C84.C44A33第43页/共70页1.高二要从全级10名独唱选手中选出6名在歌咏会上表演，出场安排甲，乙两人都不唱中间两位的安排方法有多少种？练习：第44页/共70页

例1：5个不同的元素a,b,c,d,e每次取全排列。①a,e必须排在首位或末位，有多少种排法？一题多变

解：①（解题思路）分两步完成，把a,e排在首末两端有A22种，再把其余3个元素排在中间3个位置有A33种。由乘法共有A22.A33=12(种)排法。优先法第45页/共70页

例1：5个不同的元素a,b,c,d,e每次取全排列。②a,e既不在首位也不在末位，有多少种排法？一题多变

解：②先从b,c,d三个选其中两个排在首末两位，有A32种，然后把剩下的一个与a,e排在中间三个位置有A33种，由乘法原理:

共有A32.A33=36种排列.间接法：

A55-4A44+2A33（种）排法。第46页/共70页

例1：5个不同的元素a,b,c,d,e每次取全排列。③a,e排在一起多少种排法？一题多变

解：③捆绑法：a,e排在一起，可以将a,e看成一个整体,作为一个元素与其它3个元素全排列，有A44种；a,e两个元素的全排列数为A22种，由乘法原理共有A44.A22(种)排列。第47页/共70页

例1：5个不同的元素a,b,c,d,e每次取全排列。④a,e不相邻有多少种排法？一题多变

解：④排除法：即用5个元素的全排列数A55，扣除a,e排在一起排列数A44.A22，则a,e不相邻的排列总数为A55-A44.A22（种）插空法：即把a,e以外的三个元素全排列有A33种，再把a,e插入三个元素排定后形成的4个空位上有A42种，由乘法原理共有A33.A42

(种)第48页/共70页

例1：5个不同的元素a,b,c,d,e每次取全排列。⑤a在e的左边（可不相邻）有多少种排法？一题多变

解:

⑤a在e的左边(可不相邻)，这表明a,e只有一种顺序，但a,e间的排列数为A22，所以，可把5个元素全排列得排列数A55，然后再除以a,e的排列数A22。所以共有排列总数为A55/A22（种）

注意：若是3个元素按一定顺序，则必须除以排列数P33。第49页/共70页

例2：已知集合A={1，2，3，4，5，6，7，8，9}，求含有5个元素，且其中至少有两个是偶数的子集的个数。解法1：5个元素中至少有两个是偶数可分成三类：①2个偶数，3个奇数；②3个偶数，2个奇数；③4个偶数，1个奇数。所以共有子集个数为

C42.C53+C43.C52+C44.C51=105解法2：从反面考虑，全部子集个数为P95，而不符合条件的有两类：①5个都是奇数；②4个奇数，1个偶数。所以共有子集个数为C95-C55-C54.C41=105第50页/共70页（三）排列组合混合问题：

例3：从6名男同学和4名女同学中，选出3名男同学和2名女同学分别承担A，B，C，D，E5项工作。一共有多少种分配方案。

解1：分三步完成，1.选3名男同学有C63种，2.选2名女同学有C42种，3.对选出的5人分配5种不同的工作有A55种，根据乘法原理C63.C42.A55=14400(种).第51页/共70页

例3：从6名男同学和4名女同学中，选出3名男同学和2名女同学分别承担A，B，C，D，E5项工作。一共有多少种分配方案。

解2：把工作当作元素，同学看作位置，1.从5种工作中任选3种（组合问题）分给6个男同学中的3人（排列问题）有C53.A63种,第二步,将余下的2个工作分给4个女同学中的2人有A42种.根据乘法原理共有C53.A63.A42=14400(种).

亦可先分配给女同学工作,再给男同学分配工作,分配方案有C52.A42.A63=14400(种).第52页/共70页例4.九张卡片分别写着数字0，1，2，…，8，从中取出三张排成一排组成一个三位数，如果6可以当作9使用，问可以组成多少个三位数？解：可以分为两类情况：①若取出6，则有种方法；②若不取6，则有种方法，根据分类计数原理，一共有+＝602种方法第53页/共70页典型例题

1.4名优等生被保送到3所学校，每所学校至少得1名，则不同的保送方案总数为（）。（A)36(B)24(C)12(D)62.若把英语单词“error”中字母的拼写顺序写错了，则可能出现的错误的种数是（）（A)20(B)19(C)10(D)69

3.小于50000且含有两个5，而其它数字不重复的五位数有（）个。（A)(B)(C)(D)

ABB第54页/共70页练习

3.15人按照下列要求分配，求不同的分法种数。(1)分为三组，每组5人,共有______________种不同的分法。（2）分为甲、乙、丙三组，一组7人，另两组各4人，共有___________________种不同的分法。（3）分为甲、乙、丙三组，一组6人，一组5人，一组4人，共有___________________种不同的分法。4.8名同学选出4名站成一排照相，其中甲、乙两人都不站中间两位的排法有______________________种。

5.某班有27名男生13女生，要各选3人组成班委会和团支部每队3人，3人中2男1女，共有_____________________种不同的选法。第55页/共70页1.(2011·大纲全国卷)某同学有同样的画册2本，同样的集邮册3本，从中取出4本赠送给4位朋友，每位朋友1本，则不同的赠送方法共有(

)A．4种B．10种C．18种 D．20种练习:解析：

分两种情况：①选2本画册，2本集邮册送给4位朋友有种方法；②选1本画册，3本集邮册送给4位朋友有种方法，所以不同的赠送方法共有6＋4＝10(种)，故选B.第56页/共70页[解题过程]

需分两步：第1步，根据经纪人的推荐在12种股票中选8种，共有C128种选法；第2步，根据经纪人的推荐在7种债券中选4种，共有C74种选法．根据分步乘法计数原理，此人有C128·C74＝17325种不同的投资方式．2.某人决定投资于8种股票和4种债券，经纪人向他推荐了12种股票和7种债券．问：此人有多少种不同的投资方式？第57页/共70页例4.(2011·北京高考)用数字2,3组成四位数，且数字2,3至少都出现一次，这样的四位数共有________个．(用数字作答)解析：

数字2,3至少都出现一次，包括以下情况：“2”出现1次，“3”出现3次，共可组成C41＝4(个)四位数．“2”出现2次，“3”出现2次，共可组成C42＝6(个)四位数．“2”出现3次，“3”出现1次，共可组成C43＝4(个)四位数．综上所述，共可组成14个这样的四位数．答案：

14第58页/共70页

例5.“抗震救灾，众志成城”，在我国甘肃舟曲的抗震救灾中，某医院从10名医疗专家中抽调6名奔赴某灾区救灾，其中这10名医疗专家中有4名是外科专家．问：(1)抽调的6名专家中恰有2名是外科专家的抽调方法有多少种？(2)至少有2名外科专家的抽调方法有多少种？(3)至多有2名外科专家的抽调方法有多少种？[规范解答]

(1)分步：首先从4名外科专家中任选2名，有种选法，再从除外科专家的6人中选取4人，有种选法，所以共有种抽调方法.第59页/共70页(2)“至少”的含义是不低于，有两种解答方法，方法一(直接法)：按选取的外科专家的人数分类：①选2名外科专家，共有C42·C64种选法；②选3名外科专家，共有C43·C63种选法；③选4名外科专家，共有C44·C62种选法；根据分类加法计数原理，共有C42·C64＋C43·C63＋C44·C62＝185种抽调方法.方法二(间接法)：不考虑是否有外科专家，共有种选法，考虑选取1名外科专家参加，有种选法；没有外科专家参加，有种选法，所以共有：种抽调方法.第60页/共70页(3)“至多2名”包括“没有”、“有1名”、“有2名”三种情况，分类解答．①没有外科专家参加，有C66种选法；②有1名外科专家参加，有C41·C65种选法；③有2名外科专家参加，有C42·C64种选法.所以共有C66＋C41·C65＋C42·C64＝115种抽调方法.第61页/共70页[题后感悟]解答有限制条件的组合问题的基本方法：第62页/共70页某市工商局对35种商品进行抽样检查，鉴定结果有15种假货，现从35种商品中