两个计数的基本原理

资源描述

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

1、两个计数的基本原理1. 知识点和方法述要两个基本原理在计数过程中，乘法原理和加法原理是两个所依据的最基本的原理.(1) 乘法原理做一件事，完成它需要n个步骤，做第一步有m!种不同的方法，做第二步有m2种不同的方法做第n步有mn种不同的方法，那么完成这件事的所有方法有N二m1mj|mn种.运用乘法原理，关键在于把完成一件事的全过程作多重选取的过程处理，分成若干阶段，每一阶段都是从相应的一个集合中挑选一个元素，考虑其可能有的不同方式数.(2) 加法原理做一件事，完成它可以有几类方法，在第一类方法中有mi种不同方法，在第二类方法中有m2种不同的方法在第n类方法中有mn种不同的方法，那么完成这件事共有

2、方N=m1m2J(|mn种.如果把一个集合分成若干个子集Al,A2,，An,使得（i）A“Aj=0（仁i式j兰n）,n（ii）Ai=1,2,，n,iT那么这些子集Al,A2,，An叫做A的一个分划，也就是说，它们的并集为A,两两交集为空集，满足上述两条性质的子集Al,A2,A3,，An，加法原理表现为aHaHaJ+IIITaJ，这里|a|表示集合Ai所包含的元素个数.上述用集合的观点表示的加法原理，更突出地表明：运用加法原理计数，同级分类必须依据统一的分类标准，不能重复或遗漏.2. 穷举法（枚举法）计数中，穷举法（枚举法）是一种最原始最基本的方法，所谓穷举法，即通过对所有情形的一一列举而导致结

4、二nn-1n-2I|_2j.根据加法原理，对于全集I，当AI时，|iHA+A,即A=|I|-|A.由此马上可以得到，当aUAqU-UI时nAUAUUAm卜|i|-送|A|+送人141玄icj兰m-送|ariAj“Ak卜+(-1门4门宀门nAmi1_i:j:K_m上述等式我们称为逐步淘汰原理.例题精讲例1如果直角三角形的边长可表示为m2n2，m2-n2，2mnmn1,m,nN，边长均小于100，问这样的直角三角形有多少种不同情形？分析依题设，知m2n100.所以m空9，注意到mn，穷举如下：当m=2时，n=1;当m=3时，n=1,2;当m=4时，n=1,2,3;当m=5时，n=1,2,3,4;当

5、m=6时，n=1,2,3,4,5;当m=7时，n=1,2,3,4,5,6;当m=8时，n=1,2,3,4,5,6,7;当m=9时，n=1,2,3,4,5,6,7,8.直角三角形具体组成情况如下表所示，共有不同的直角三角形1+2+3+4+5+6+5+4=30（种）.mn2丄2m+n22m-n2mn215343110862135124117158220121632572491828018285773639072544976572例2已知A八印月2,川,时，求集合的子集数.分析就单元素集Q而言，它的子集有一，两个;若集合为Q,a21,那么它的子集有-，a/，a2?，a1,a2：?等四个；若集合为i：

6、a1,a2,a，那么它的子集有-a/，、耳包用等八af，a，ai，a，a2，a，aa3?个.由于每个子集的构成取决于元素a1，a2，a3是属于还是不属于该集合，根据乘法原理，可知集合A有子集2n个，其中包括-及自身.例3有壹元人民币3张，伍元人民币2张，拾元人民币4张，伍拾元人民币1张，从中至少取一张，多不限，共可取得多少种不同币值？分析注意到取2张伍元的人民币与1张拾元人民币币值相同，不能算作两种不同取法，为避免重复，将4张拾元人民币和2张伍元人民币的“换成”10张伍元人民币，二者所起的作用是一样的，同样一张伍拾元人民币、2张伍元人民币、4张拾元人民币可“换成”20张伍元人民币，于是问题等价

7、于：有一元人民币3张，伍元人民币10张，至少取一张，多不限，可取得多少种不同币值？把取币的过程看作二重选取过程，从3张壹元人民币中取有0，1，2，3张4种不同情形，从20张伍元人民币中取有0,1,2,20张21种不同情形，根据乘法原理，有4X21=84种不同币值.但必须除去壹元、伍元均没有取的情形，故可取得83种不同币值.在计数过程中常常将乘法原理和加法原理结合使用.例4如图2-3所示的棋盘格形的街道上，若阴影部分内暂时不能通过，问从A到B的最短路线有多少种?分析如图2-4,可将从A到B（不多刼龙:纭序芬=M罗越烷为IB麦乃序劣力乃*笏爲韧名232-4经过阴影部分)最短路线分为三类不同情形(i

8、)从A经过P到B.路线是惟一的.从A经过Q到B.由于从A到Q有8种不同路线，而从Q到B又有8种不同路线，根据乘法原理，从A经过Q到B的最短路线有8X8=64(种).(i)从A经过R到B.此类路线又可分为两种情形：(ii)从A经R再经N到B,路线是惟一的；(ii) 从A经R再经M到B,其中从A到R路线是惟一的，从R到M有2种不同路线，而从M到B又有8种不同路线，根据乘法原理，此类路线有1X2X8=16(种).于是从A经R再经M或N列B的路线有17种根据加法原理，所求路线共有1+64+17=82(种)例5有多少个能被3整除而又含数字6的五位数？分析五位数中含有数字6的情况比较复杂，可以含有一个6,

9、二个6乃至五个6.这些6还可以出现在各个不同的数位上，故正面分类繁难不妨从反面去想一想，情形就简单多了，只有不含有数字6一类，只须从被3整除的所有五位数中减去其中不含数字6的数即可求解.从10000到99999这90000个五位数中，能被3整除的五位数有30000个.再看上述30000个数中不含数字6的数.首先最高位数字有1,2,3,4,5,7,8,9等8种不同情形，而千位、百位、十位上不能为6,均有9种不同情形，个位上除了不能为6夕卜，还应保证整个五位数被3整除，换句话说，当前四位数字之和为3除余数为2时，个位数应为1,4,7中一个，当前四位数字之和被3除余数为1时，个位数字可为2,5,8之

10、，而当余数为0时，个位数可为0,3,9中一个，总而言之，无论前四位数字如何，个位数字都有3种可能情形，根据乘法原理，能被3整除且不含数字6的五位数有8X9X9X9X3=17496（个）.因此，所求五位数有3000017496=12504（个）.避繁就简，通过从总数中淘汰掉易于计数的不符合要求的情形是计数中常采用的手段.例6某工厂生产一批玩具，要预先制作一批圆环形底板，这些底板上均匀分布有12个半球形凹洞.其中3个为红色，9个是白色，如图2-5所示，若两个洞可以球心对球心，红色对红色，A白色对白色叠放在起，我们说它属于q同规格，问：该工厂生产的这类玩具底板一共可以有多少种不同的规格？LJ图2-5

11、分析如图2-5,先假定12个洞都为白色，再将其中三个涂成红色，并通过旋转将A处的球保证为红色，由A开始顺时针方向标数，A处的数标0，其他的洞顺序标为1,2,，10,11.三红洞所在位臵标的数记为：0,i,Fj.显然，i可以取值2,3,4,，11.当j=2时，i只能取值1,只有一种取法；当j=3时，i只能取值1,2,共2种；当j=4时，i可以取值1,2,3，共3种当j=11时，i可以取值1,2,，10,共10种取法，因此，为保证位于A处的洞是红色的，共有12III10=55种涂法.由于三红洞没有特殊性，经旋转后，另二红洞也可以位于A处，而属于同一类的涂法，都可以由同一类中选定的一种涂法经旋转而得

12、到.首先，若经旋转后，不产生新的涂法，则三红洞的位臵必是(0,4,8).其次，若经旋转后将第二个红洞转到A处，产生新的涂法，那么将第三个红洞转到A时必产生第三种涂法，否则就是(0,4,8).由于只有三个红洞，对于这一选定的涂法，经旋转只能产生三种涂法，因此55种涂法除(0,4,8)外，还有54种，其中任一种都与某二种属于同一类，所以有不同规格的玩具底板1=19（种）.3例7某州颁布由6个数字组成的车牌号码（由0-9的数字组成），亥州规定任何两个牌号至少有两个数字不同（因此证号027592|和020592不能都被使用）.试决定车牌证号最多有多少个？给出证明.解由5个数字组成的不同号码有105种，

13、对每个5位数号码NX2X3X4X5,再在后面添加第6个数字X6,其规则是：X6为Xi,X2,X3,X4,X5的和的个位数字.对于任何这样构造出来的两个不同数：a1a2a3a4a5a6,b1b2b3b4b5b6.至少有一个数位1j7,根本不存在合格的k-组合，即对于k7,恒有f(k)=0.上不相邻的两点，而每个圆周上不相邻的两点所成点对”皆为5个，根据乘法原理可得f6-5125.每个合格的5-组合，则是在其中一个圆周上取一点，在其余两圆周上各取一个不相邻点所成“点对”.根据乘法原理，3个圆中取1个且在该圆的5个点中取I点有15种取法，而在其余的两圆周不相邻点所成“点对”皆为5个，因此又由乘法原理可得f(5)=15X52=375.所有合格的4-组合可分为两类：一类是取两个圆，每个圆周上取一对不相邻点，这有3X52=

展开阅读全文