第02讲 组合数学――计数规则

哈尔滨工程大学课件沈晶制作第2讲计数法则加法法则乘法法则一一对应法则哈尔滨工程大学课件沈晶制作加法法则问题：2009级硕士研究生在沈老师班上组合数学课的学生有66人，在其余两位老师班上课的学生有123人，问共有多少人？哈尔滨工程大学课件沈晶制作加法法则假设有两个互斥的事件A与事件B，事件A有m种产生方式，事件B有n种产生方式，则事件A或B，有m+n种产生方式。集合论语言描述如下：若|A|=m,|B|=n,AB=,则|AB|=m+n哈尔滨工程大学课件沈晶制作加法法则例1在6位二进制数中，求至少有连续4位为1的数有多少个？解：A事件(连续4位为1):{111100,111101,011110,001111,101111}B事件(连续5位为1):{111110,011111}C事件(连续6位为1):{111111}则连续出现1111连续出现11111连续出现1111111111000111100011111011111111011111100111111111118125CBA哈尔滨工程大学课件沈晶制作第2讲计数法则加法法则乘法法则一一对应法则哈尔滨工程大学课件沈晶制作乘法法则问题从A到B有3条道路，从B到C有2条道路，则从A经B到C共有几条道路？实质上，相当于把计数过程分成了相互独立的两个步骤ABC第一步第二步事件A事件Bmn×=m﹒n哈尔滨工程大学课件沈晶制作乘法法则假设有两个相互独立的事件A和事件B,事件A有m种产生方式，事件B有n种产生方式，则事件A和B共有m·n种产生方式。集合论语言描述如下：若|A|=m,|B|=n,P(AB)=P(A)·P(B),AB={(a,b)|aA,bB},则|AB|=m·n哈尔滨工程大学课件沈晶制作加法法则与乘法法则例2求在1000到9999之间有多少个每位上的数字均不同的奇数？解：个位可从{1，3，5，7，9}中任取一个；千位有8种可能（去掉0和个位）；百位有8种可能（去掉个位和千位）；十位有7种可能（去掉个位、十位和百位）应用乘法规则共有5*8*8*7=2240哈尔滨工程大学课件沈晶制作加法法则与乘法法则例3求在2000到9999之间有多少个每位上的数字均不同的奇数？解：个位可分别从{3，5，7，9}和{1}集合中任取一个元素；千位分别有7、8种可能；百位分别有8、8种可能；十位分别有7、7种可能；应用乘法和加法法则共有4*7*8*7+1*8*8*7=2016哈尔滨工程大学课件沈晶制作加法法则与乘法法则例4求能除尽1400的正整数的个数（1除外）解：整数m可表示成m=a1p1.a2p2…anpn1400=23*52*71400的因数可表示为2p1*5p2*7p3，其中：0≤p1≤3；0≤p2≤2；0≤p3≤1根据乘法法则可得：4*3*2-1=23哈尔滨工程大学课件沈晶制作加法法则与乘法法则例5求100!这个整数的末尾有多少个零？解100！=2k*3m*5l*7n*…….因为lk，所以只需求出l的值从1到100中，共有20个数含有5，其中，25，50，75，100中含有2个5，则总共有24个5所以，100！中末位所含零的个数为24个哈尔滨工程大学课件沈晶制作减法与乘法法则例6求5位数中至少存在一个6且能被3整除的数的个数解用P1P2P3P4P5表示一个5位数；共有99999-9999=90000个5位数，能被3除尽的数共有30000个一个6都不出现的数的个数为8*9*9*9*3=1749630000-17496=12504哈尔滨工程大学课件沈晶制作第2讲计数法则加法法则乘法法则一一对应法则哈尔滨工程大学课件沈晶制作一一对应法则假设事件A的产生方式与事件B的产生方式一一对应，则事件A产生的方式数与事件B产生的方式数相等。要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。哈尔滨工程大学课件沈晶制作一一对应法则例7在100名选手中进行淘汰赛，最后产生一名冠军选手，要经过多少场比赛？解法一50+25+12+6+3+2+1=99解法二要淘汰99名选手，共需进行99场比赛哈尔滨工程大学课件沈晶制作总结加法法则乘法法则一一对应法则分类加法计数分步乘法计数难转化问题