计数原理Counting Theory

《计数原理Counting Theory》由会员分享，可在线阅读，更多相关《计数原理Counting Theory（47页珍藏版）》请在金锄头文库上搜索。

1、计数原理计数原理 Counting theoryCounting theory或一个阿拉伯数字给一个小班教室里的座位编 号，总共能够编出多少种不同的号码？请思考 :问题1：用一个大写的英文字母加法分类36种问题剖析问题问题 1 要完成什么事情完成这个事情有几 类方案 每类方案能否独立 完成这件事情 每类方案中分别有 几种不同的方法 完成这件事情共有 多少种不同的方法两类能26种 10种26+10=36种或一个阿拉伯数字给一个小班教室里的座位编 号，总共能够编出多少种不同的号码？请思考 :问题1：用一个大写的英文字母用一个大写的英文字母或一个阿拉伯 数字给教室里的座位编号完成一件事有两类不同方案

2、，在第1类方案中有 m种不同的方法，在第2类方案中有n种不同的方 法,那么完成这件事共有:种不同的方法。N=m+n完成一件事分两类不重不漏(Addition principle)深圳练习:从深圳到长沙，可以乘火车，也可以乘汽 车。一天中，火车有3班，汽车有2班。那么一 天中，乘坐这些交通工具从甲地到乙地共有多 少种不同的走法？长沙火 车 2火 车 1火 车 3汽 车 1汽 车 23+2=5（种）例1.在填写申请大学专业时,一名高中毕业生了解 到两所大学各有一些自己感兴趣的强项专业,具体 情况如下:耶鲁大学哈弗大学生物学化学医学物理学工程学数学会计学信息技术学法学如果这名同学只能选一个专业,那么

3、他共有多少种 选择呢?变式：在填写申请大学专业时,一名高中毕业生了 解到,三所大学各有一些自己感兴趣的强项专业,具 体情况如下:耶鲁大学哈弗大学生物学化学医学物理学工程学数学会计学信息技术学法学如果这名同学只能选一个专业,那么他共有多少种 选择呢?纽约大学机械制造建筑学广告学汉语言文学韩语N=5+4+5=14(种)如果完成一件事情有3类不同方案，在第1类方 案中有m1种不同的方法，在第2类方案中有m2 种不同的方法，在第3类方案中有m3种不同的 方法，那么完成这件事情有种不同的方法N=m1+m2+m3探究1如果完成一件事情有n类不同方案，在第1类 方案中有m1种不同的方法，在第2类方案中有m2

4、 种不同的方法， 在第n类方案中有mn种不 同的方法，那么完成这件事情有种不同的方法.探究2N=m1+m2+m3+.+mn如果完成一件事情有n类不同方案，在每 一类中都有若干种不同方法，那么应当如何计 数呢？分类加法计数原理Addition Principle思维的轨迹：问题1分类加 法计数 原理从特殊到一般的思想分类加法计数 原理(一般情况 )归纳问题1：用一个大写的英文字母或一个阿拉伯 数字给一个小班教室里的座位编号，总共能 够编出多少种不同的号码？取字母取数得到的号码A132546879A1 A2A3 A4A5 A6A7 A8A9分析：第1步第2步树形 图6 9 =54种完成一件事需要两

5、个步骤，做第1步有m种不同 的方法，做第2步有n种不同的方法,那么完成这件 事共有: 种不同的方法.分步相互依存， 缺一不可完成一件事(Multiplication principle)如果完成一件事需要n个步骤，做第一步有m1种不同 的方法，做第二步有m2种不同的方法， ，做第n步有mn 种不同的方法，那么完成这件事共有N=m1m2m3 mn种不同的方法.类比的思想分步乘法计数原理Multiplication Principle选法？赛，共有多少种不同的女生各一名代表参加比选出男、女生24名.现要从中0名,例2.设某班有男生3火 车 2火 车 1火 车 3练习： 从甲地到乙地，要从甲地先乘火

6、车 到丙地，再于次日从丙地乘汽车到乙地。一 天中，火车有3班，汽车有2班，那么两天中 ，从甲地到乙地共有多少种不同的走法？ 甲乙丙汽 车 2汽 车 1例3.书架的第1层放有4本不同的计算机书 ，第2层放有3本不同的文艺书，第3层放2本 不同的体育书. 从书架上任取1本书，有多少种不同的 取法？ 从书架的第1、2、3层各取1本书，有多 少种不同的取法？若完成一件事情可以有n类方案，在第一类方案中有m1种不同 的方法，在第二类中有m2种不同的方法,在第n类方案中有mn种不 同的方法，那么完成这件事情有: N=m1+m2+m3+m4+.+mn种不同的方法若完成一件事情需要n个步骤，在第一步中有m1种

7、不同的方法， 在第二步中有m2种不同的方法，在第n步方法中有mn种不同的方法 ，那么完成这件事情有： N=m1m2m3m4. mn种不同的方法Addition principleAddition principleMultiplication principleMultiplication principle计数原理计数原理 Counting theoryCounting theory分类类加法计计数原理 分步乘法计计数原理相同点区 别别完成一件事情的不同方法种数问题一步完成(分类)多步完成(分步)每类中的任一种方法都能 独立完成这件事情 不重复、不遗漏相互依存 缺一不可分类加法计数原理与分步

8、乘法计数原理 的联系与区别例1. 五名学生报名参加四项体育比赛，每人限 报一项，报名方法的种数为多少？又他们争夺 这四项比赛的冠军，获得冠军的可能性有多少 种？ 解：（1）5名学生中任一名均可报其中的任一项，因此每 个学生都有4种报名方法，5名学生都报了项目才能算完成 这一事件故报名方法种数为44444= 种 .（2）每个项目只有一个冠军，每一名学生都可能获得 其中的一项获军，因此每个项目获冠军的可能性有5种 故有n=5= 种 .例2.给程序模块命名，需要用3个字符，其中首个字 符要求用字母AG或UZ，后两个要求用数字1 9，问最多可以给多少个程序命名？分析：要给一个程序模块命名，可以分三个步

9、骤：第一步， 选首字符；第二步，先中间字符；第三步，选末位字符。解：首字符共有7+613种不同的选法，答：最多可以给1053个程序命名。中间字符和末位字符各有9种不同的选法根据分步计数原理，最多可以有13991053种不同的选法例3.核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子 是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称 为碱基的化学成分所占据，总共有个不同的碱基，分别用A，C，G，U表 示，在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位 置上的碱基与其他位置上的碱基无关。假设有一类RNA分子由100个碱基组 成，那么能有多少种不

10、同的RNA分子？UUUAAACCCGGG分析:用100个位置表示由100个碱基组成的长链，每个位置都可以从A、C 、G、U中任选一个来占据。第1位第2位第3位第100位4种4种4种4种解：100个碱基组成的长链共有100个位置，在每个位置中，从A、C、G、U 中任选一个来填入，每个位置有4种填充方法。根据分步计数原理，共有种不同的RNA分子.例4.电子元件很容易实现电路的通与断、电位的高与底等两种 状态，而这也是最容易控制的两种状态。因此计算机内部就采 用了每一位只有0或1两种数字的计数法，即二进制，为了使计 算机能够识别字符，需要对字符进行编码，每个字符可以用一 个或多个字节来表示，其中字节

11、是计算机中数据存储的最小计 量单位，每个字节由个二进制位构成，问 （1）一个字节（8位）最多可以表示多少个不同的字符？ （2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉 字为一个字符，要对这些汉字进行编码，每个汉字至少要用多 少个字节表示？第1位第2位第3位第8位2种2种2种2种如00000000，10000000 ，11111111.例5.随着人们生活水平的提高，某城市家庭汽车拥有量迅速增 长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌 照组成办法，每一个汽车牌照都必须有个不重复的英文字母 和个不重复的阿拉伯数字，并且个字母必须合成一组出现 ，个数字也必须合成一组出现，那

12、么这种办法共能给多少辆 汽车上牌照?HomeworkHomework2、乘积展开后共有几项？3、某商场有6个门，如果某人从其中的任意一个 门进入商场，并且要求从其他的门出去，共有多 少种不同的进出商场的方式？1、A code consists of two letters of the alphabet followedby 4 digits. How many such codes are possible?4.如图,该电路,从A到B共有多少条不同的线路可通 电？AB开始子模块1 18条执行路径子模块3 28条执行路径子模块2 45条执行路径子模块5 43条执行路径子模块4 38条执行路径结

13、束A思考1：计算机编程人员 在编写好程序以后要对程 序进行测试。程序员需要 知道到底有多少条执行路 （即程序从开始到结束的 线），以便知道需要提供 多少个测试数据。一般的 ，一个程序模块又许多子 模块组 成，它的一个具有许多执 行路径的程序模块。问： 这个程序模块有多少条执 行路径？另外为了减少测 试时间，程序员需要设法 减少测试次数，你能帮助 程序员设计一个测试方式 ， 以减少测试次数吗？如图,要给地图A、B、C、D四个区域分别涂上红、 黄、蓝3种不同颜色中的某一种,允许同一种颜色可 使用多次,但相邻区域必须涂不同的颜色,不同的涂色 方案有多少种？解: 按地图A、B、C、D四个区域依次分四步

14、完成,第一步, m1 = 3 种, 第二步, m2 = 2 种,第三步, m3 = 1 种,第四步, m4 = 1 种,思考2 所以根据乘法原理, 得到不同的涂色方案种数共 有 N = 3 2 11 = 6 种.所以, 根据分类原理, 从A到B共有N = 3 + 1 + 4 = 8 条不同的线路可通电。在解题有时既要分类又要分步。解: 从总体上看由A到B的通电线路可分三类,第一类, m1 = 3 条 第二类, m2 = 1 条 第三类, m3 = 22 = 4, 条练习(2)2答案.如图,用5种不同颜色给图中的A、B、C、D四个区域涂色, 规定一个区域 只涂一种颜色, 相邻区域必须涂不同的颜色

15、, 不同的涂色方案有 种。 ABCD分析：如图，A、B、C三个区域两两相邻， A 与D不相邻，因此A、B、C三个区域的颜色两两 不同，A、D两个区域可以同色，也可以不同色 ，但D与B、C不同色。由此可见我们需根据A与D 同色与不同色分成两大类。解：先分成两类：第一类，D与A不同色，可分成四步完成。 第一步涂A有5种方法，第二步涂B有4种方法；第三步涂C 有3种方法；第四步涂D有2种方法。根据分步计数原理， 共有5432120种方法。 根据分类计数原理，共有120+60180种方法。第二类，A、D同色，分三步完成，第一步涂A和D有5种 方法，第二步涂B有4种方法；第三步涂C有3种方法。根据分 步

16、计数原理，共有54360种方法。1 用1,2,3,4,5五个数字,组成比2000大的没 有重复数字的四位数有多少个?变式2:用1,2,3,4,5五个数字,组成比2000大且 比5000小的没有重复数字的数有多少个?变式1:用1,2,3,4,5五个数字,组成比2000大 的没有重复数字的数有多少个?N=4432=96N=96+54321=216N=3432=72练习12 用1,2,3,4,5,6中的两个数分别作为对数的底 数和真数,得到不同的对数值有多少个?变式1: 用1,2,3,4,5,6,7,8,9中的两个数分别作 为对数的底数和真数,得到不同的对数值有多 少个?变式2: 用0,1,2,3,4,5,6中的两个数分别作为分 数的分子与分母,得到不同的值有多少个?N=54+1=21N=8