1.1-基本计数法则PPT演示课件

1、1.1 基本计数法则,2,1.1 基本计数法则,加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式,集合论语言： 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n,例1.1.1 书架上有数学类书5本，计算机类书3，任取其中一本，有多少种取法,共有5+3=8种取法,1.1.1 加法法则,3,1.1 基本计数法则,乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式,集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| =

2、m n,例1.1.2 从A到B有三条道路，从B到C有两条道路，则从A经B到C有几条道路,有 32=6 条,1.1.2 乘法法则,4,例1.1.3 机动车牌照字由7个字符组成，第一个字符是汉字，表示省份或军区等，第二个字符是英文字母，表示市、区或行业等，其余5位可选自英文字母或数字（有时用第三个字符表示行业，如出租用T)，问一个市的机动车拥有量最多是多少,机动车拥有量最多是： (26+10)5 辆,出租车拥有量最多是： (26+10)4 辆,1.1 基本计数法则,5,1.1 基本计数法则,例1.1.4 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则

3、共有42 = 8种着色方案,若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4 = 16， 而只有 4 3 = 12 种,在乘法法则中要注意事件 A 和 事件 B 的相互独立性,6,1.1 基本计数法则,例1.1.5 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数,小于10000的正整数可看做4位数, 共有 104 1=9999 个（0000除外） 不含1的4位数有：9416560个 含1的4位数有：99996560=3439个,另: 全部4位数有10 4个,不含1的四位数有94 个, 含1的4位数为两个数的差: 104 9 4= 3

4、439个,7,2)“含0”和“含1”不可直接套用。0019(含1但不含0)。 在组合的习题中有许多类似的隐含的规定，要特别留神,不含0的1位数有9个，2位数有92 个，3位数有93 个，4位数有94 个,不含0小于10000的正整数有 9+92+93+94 =(951)/(91)=7380个,含0小于10000的正整数有 99997380=2619个,1.1 基本计数法则,8,1.1 基本计数法则,例1.1.6 求除尽 n=73.112.134 的数的个数,故整除的个数为,9,如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与1,n元一一对应的关系,在组合计数时往往借助于一一对应实现

5、模型转换,比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应,一一对应原理 如果事件A与事件B间存在一一对应（双射），则事件A与B一样大，即|A|=|B,1.1 基本计数法则,1.1.3 一一对应原理,10,例1.1.7 在65名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛,另一种思路是淘汰的选手与比赛(按场计)集一一对应。淘汰64名选手，需要64场比赛,1.1 基本计数法则,一种常见的思路是按轮计场（费事）： 32+16+8+4+2+1+1=64 注意，每轮都有一人轮空,11,例1.1.8 设凸n边形的任意三条

6、对角线不共点，求对角线在多边形内交点的个数,可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂,可以考虑对应关系： 多边形内交点 to 多边形四个顶点,可以证明这是一一对应（映射，单且满,1.1 基本计数法则,交点的个数：Cn4,12,例1.1.9 有一排灯共n盏，都关着。现有n个人通过，第一个人拔动第1,2,3，n盏等的开关，第二个人拔动第2,4,6，盏等的开关，第三个人拔动第3,6,9，盏等的开关， ，第n个人拔动第n盏等的开关。这n个人走过之后问哪些灯亮着,1.1 基本计数法则,引理 正整数n有奇数个因子(包括1，n)当且仅当n是完全平方数,由引理可知亮灯的是第1,4,9,16， 盏灯亮,13,例1.1.10 简单格路问题：从 (0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径,1.