计数原理复习课

第一章计数原理复习课知识网络分类计数原理（加法原理）完成一件事,有n类办法,在第1类办法中有m1种不同的方法,在第2类办法中有m2种不同的方法……在第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+…+mn种不同的方法.分步计数原理：（乘法原理）完成一件事,需要分成n个步骤,做第1步有m1种不同的方法,做第2步有m2种不同的方法……做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法.排列：从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列。排列数：从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数。通常用表示。mnA特别地，当m=n时，称为一个全排列，)!(!)1()2)(1(mnnmnnnnAmn12)2)(1(nnnAnn=n！.这里,且。*,Nmnnm注意：第一公式用于计算、第二个公式用于证明。规定：0！=1全排列数组合：从n个不同元素中取出m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合.组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数,记作.mnC!)!(!!)1()2)(1(mmnnmmnnnnAACmmmnmn注意：第一公式用于计算，第二个公式用于证明。这里,且.*,Nmnnm（2）上面两个性质，除了根据组合定义直接得到外，还可用组合数公式证明．mnmnnCC性质111mmmnnnCCC性质2注意：（1）为了使上面的公式在m＝n时也能成立，，规定10nC当时，利用这个性质计算比较简便．2nm组合数性质：例1.满足,1,0,1,2ab,且关于x的方程220axxb有实数解的有序数对(,)ab的个数为（）A．14B．13C．12D．10B例2.从1,3,5,7,9这五个数中,每次取出两个不同的数分别为,ab,共可得到lglgab的不同值的个数是（）A．9B．10C．18D．20C例3.2016年西博会组委会要从小张、小赵、小李、小罗、小王五名志愿者中选派四人分别从事接待、宣传、信息采集、司机四项不同工作，若其中小张和小赵只能从事前两项工作，其余三人均能从事这四项工作，则不同的选派方案共有（）A.36种B.12种C.18种D.48种解：分两类：若只有小张或只有小赵入选，则有选法24331212ACC；若小张、小赵都入选，则有选法122322AA，共有选法36种，选A.例4.将序号分别为1,2,3,4,5的5张参观券全部分给4人,每人至少1张,如果分给同一人的2张参观券连号,那么不同的分法种数是_________.96例5．（1）5名学生参加四种项目不同的体育比赛，争夺这四项活动的冠军，获得冠军的可能性有（）A.45B.9C.54D.20（2）从A、B、C、D、E五名学生中选出四名分别参加数学、物理、化学、英语竞赛，其中A不参加物理、化学竞赛，则不同的参赛方案种数为（）A.24B.48C.120D.72（3）有A、B、C、D、E、F6个集装箱，准备用甲、乙、丙三辆卡车运送，每辆卡车一次运两个，若卡车甲不能运A箱、卡车乙不能运B箱，此外无其它任何限制。要把这6个集装箱分配给这3台卡车运送，则不同的分配方案的种数（）A．168B．84C．56D．42CDD21534=420（种）33354445552ACACA解：按颜色分类，有三类不同的着色方法：（1）涂5色：有种；55A（2）涂4色：有种.4445AC由分类计数原理，不同的着色方法有：2（3）涂3色：有种.3335AC例6．如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有5种颜色可供选择，则不同的着色方法共有种（以数字作答）.变式6.某人有3种颜色的灯泡（每种颜色的灯泡足够多），要在如图所示的6个点111ABCABC、、、、、上各安装一个灯泡，要求同一条线段两端的灯泡不同色，则不同的安装方法共有_________种（结果用数字表示）．思考：若改为用4种颜色的灯泡，结果是多少？解：由题意知本题是一个计数原理的应用，第一步先安排底面三个顶点共有3216种不同的安排方法，第二步安排上底面的三个顶点共有2种不同的安排方法（3个元素的错排问题）．由分步计数原理可知，共有6212种不同的安排方法．例6.用0,l,2,3,4,5这六个数字，（l）能组成多少个无重复数字的四位偶数？（2）能组成多少个无重复数字且为5的倍数5位数？（3）能组成多少个比1325大无重复数字的四位数？（4）能组成多少个无重复数字的且奇数在奇数位上的六位数字？解：（2）符合条件的可分为二类：第一类：0在个位时有个；45A第二类：5在个位时有个；3414AA由分类计数原理得，符合条件的五位数341445AAA=216（个）解：（3）符合条件的可分为三类：第一类：千位数字为2、3、4、5时有个；3514AA第二类：千位百位数字为14、15时有个；2412AA由分类计数原理得，符合条件的数共有131224123514AAAAAA=270（个）第三类：千位百位十位数字为134、135时有个；1312AA例5用0,l,2,3,4,5这六个数字，（l）能组成多少个无重复数字的四位偶数？（2）能组成多少个无重复数字且为5的倍数5位数？（3）能组成多少个比1325大无重复数字的四位数？（4）能组成多少个无重复数字的且奇数在奇数位上的六位数字？解：（4）先将1，3，5在奇数位上排列，有种，再将其余3个偶数排在剩余3个位置上排列，共有种，33A由分步计数原理得，共有种排法，22333333AAAA=24（个）33A3333AA而其中0在首位上时不合题意，有种，2233AA所以符合条件的数共有例5用0,l,2,3,4,5这六个数字，（l）能组成多少个无重复数字的四位偶数？（2）能组成多少个无重复数字且为5的倍数5位数？（3）能组成多少个比1325大无重复数字的四位数？（4）能组成多少个无重复数字的且奇数在奇数位上的六位数字？课后作业完成复习讲义相关题目