第34讲 计数原理(上)：排列组合基本方法、容斥原理

《第34讲 计数原理(上)：排列组合基本方法、容斥原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计数原理1、分类加法计数原理完成一件事①有n类方法；②任两类无公共方法；③每类中每种方法可单独做好这件事；共有N=m1+m2+······+mn种不同方法。2、分步乘法计数原理完成一件事①必须走完n步，才能完成任务；②前一步怎么走对后一步怎么走无影响；共有N=m1×m2×······×mn种不同的方法。3、排列与排列数从n个不同元素中任取m个不同元素按照一定的顺序排成一列，共有Anm种方法。Anm=n·n-1·n-2···(n-m+1)Ann=n·n-1·n-2···3·2·1=n!Anm=n!n-m!，规定0!=14、组合与组合数从n个不同元素中任取m个不同元素，并组成一组，共有C

2、nm种方法。Cnm=AnmAmm=nn-1n-2···(n-m+1)m!=n!m!n-m!5、组合公式的性质①Cnm=Cnn-m；②Cnm+Cnm+1=Cn+1m+1③Cm1Cnm=Cn1Cn-1m-1；④Cmm+Cm+1m+Cm+2m+···+Cnm=Cn+1m+16、排列组合常用技巧位置优先；元素优先；捆绑法；插空法；挡板法；间接法；定序问题无序法；分排问题直排法7、排列组合基本原则:不重不漏；先选后选；构造模型；分解化归【例1】把6名实习生分配到7个车间实习，共有多少种方法？解析：76.【例2】用0，1，2，3，4，5这6个数字（1）可以组成多少个数字不重复的三位数？（2）可以

3、组成多少个数字允许重复的三位数？（3）可以组成多少个数字不重复的三位奇数？（4）可以组成多少个数字不重复的小于1000的自然数？（5）可以组成多少个数字不重复的大于3000，小于5421的四位数？解析：（1）C51C51C41=100；（2）C51C61C61=180；（3）C31C41C41=48；（4）C61+C51C51+C51C51C41=131；（5）C21C51C41C31+C11C41C41C31+C11C11C21C31+C11C11C11C11=175.【例3】4名男生和3名女生并坐一排，分别回答下列问题：（1）男生必须排在一起的坐法有多少种？（2）女生互不相邻的坐

4、法有多少种？（3）男生相邻、女生也相邻的坐法有多少种？（4）男女生相间的坐法有多少种？（5）女生顺序已定的坐法有多少种？解析：（1）A44A44=576；（2）A44A53=1440；（3）A22A33A44=288；(4)A44A33=144；（5）A77A33=A74C33=840。【例4】某地政府召集5家企业的负责人开会，其中甲企业有2人到会，其余4家企业各有1人到会，会上有3人发言，则这2人来自3家不同企业的可能情况的种数为（B）A.14B.16C.20D.48解析：C21C42+C20C43=16或C63-C22C41=16【例5】8人排成前后两排，每排4人，其中甲乙在前排

5、，丙在后排，共有多少种排法？解析：A42A41A55=5760.分排问题看成一排分段即可！【例6】有10个运动员名额，分给七个班，每个班至少一个，有多少种分配方案？解析：C96=84（挡板法）【例7】x+y+z+w=100，求这个方程组的正整数解的组数。解析：C993=156849.【例8】如图，一环形花坛分成A,B,C,D四块，现有四种不同的花供选种，要求在每块里面种一种花，且相邻的两块种不同的花，则不同的种法总数为（B）A.96B.84C.60D.48解析：（染色问题）法一：主线分类支线分布C42A22+C43C21A33+A44=84法二：主线分布支线分类C41C311×3+2

6、×2=84