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

计数原理1、分类加法计数原理完成一件事有n类方法；任两类无公共方法；每类中每种方法可单独做好这件事；共有N=m1+m2+ +mn种不同方法。2、分步乘法计数原理完成一件事必须走完n步，才能完成任务；前一步怎么走对后一步怎么走无影响；共有N=m1m2 mn种不同的方法。3、排列与排列数从n个不同元素中任取m个不同元素按照一定的顺序排成一列，共有Anm种方法。Anm=nn-1n-2(n-m+1) Ann=nn-1n-2321=n! Anm=n!n-m! ，规定0!=14、组合与组合数从n个不同元素中任取m个不同元素，并组成一组，共有Cnm种方法。Cnm=AnmAmm=nn-1n-2(n-m+1)m!=n!m!n-m! 5、组合公式的性质Cnm=Cnn-m ； Cnm+Cnm+1=Cn+1m+1Cm1Cnm=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）可以组成多少个数字不重复的三位奇数？（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）女生互不相邻的坐法有多少种？（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.14 B.16 C.20 D.48解析：C21C42+C20C43=16或C63-C22C41=16【例5】8人排成前后两排，每排4人，其中甲乙在前排，丙在后排，共有多少种排法？解析：A42A41A55=5760.分排问题看成一排分段即可！【例6】有10个运动员名额，分给七个班，每个班至少一个，有多少种分配方案？解析： C96=84（挡板法）【例7】x+y+z+w=100，求这个方程组的正整数解的组数。解析：C993=156849.【例8】如图，一环形花坛分成A,B,C,D四块，现有四种不同的花供选种，要求在每块里面种一种花，且相邻的两块种不同的花，则不同的种法总数为（ B ）A.96 B.84C.60 D.