《排列组合课本电子稿》由会员分享，可在线阅读，更多相关《排列组合课本电子稿（40页珍藏版）》请在金锄头文库上搜索。
1、第7章计数原理JI SHU YUAN LI 计数原理两个基本原理 5排列 11组合 21二项式定理 31二项式定理 31 二项式系数的性质 33谓数为难穷，斯可；谓数为不可穷，斯不可.何则？彼其冥冥之中，固有昭昭者存. 治：测圆海镜序深信有待探索的自然界是有规律的.相信基本规律是简明单纯的. 爱因斯坦下图是某城市的街道西北角是某同学的家，东南角是学校，问从家经东西5条街南北4条街到学校（最短距离）有几种走法？ 在计算机中，是以二进制（只有0、1两个数码，逢二进一）串作为存储单元的地址的。如果一台计算机的存储器有一百万个单元，那么表示地址的二进制串必须要多长才能使每个单元都有它自己的地址呢？从古
2、到今，人们在社会生活的各个方面都常需要进行计数，如的编排、密码的设定、彩票设计、集成电路的布线安排，以及电子计算机的程序编制，等等本章中，我们将研究 怎样用数学模型刻画计数问题？ 如何利用计数模型解决实际问题？ 7.1 两个基本原理 调查某市职工和农民家庭中按人均月收入划分的户数如下户数500以下500元以上合计城市职工8221229农民413358771合计4215791000根据这组数据分别估计在该市任取一家庭，其人均月收入在500以下元的概率和在该市任取两个家庭，其中一个家庭人均月收入在500以下，另一家庭人均月收入在500元以上的概率。 上述两个问题有怎样的区别？他们都是计数问题，但在
3、问题（1）中，任选一种方法都能达到完成事件的目的，而在问题（2）中，必须分为两个步骤，依次连续完成全部的步骤，才能达到完成该事件的目的首先考察问题（1）乘坐汽车有3班，每一班汽车都可以完成从甲地到乙地这件事，而乘火车有2班，每一班火车也都能完成从甲地到乙地这件事，所以共有 3 + 2 = 5种不同的走法再考察问题（2）必须经过先从甲地走到乙地，再从乙地到丙地两个步骤，才能完成从甲地经乙地到丙地这件事从甲地走到乙地有3走法，从乙地到丙地有2种走法所以，从甲地经乙地到丙地共有2 5 = 10种不同的走法（图7-1-1） 一般地，我们有分类加法计数原理又称为加法原理分类加法计数原理 完成一件事，有n
4、类方式，在第1类方式中有m1种不同的方法，在第2类方式中有m2种不同的方法在第n类方式中有mn种不同的方法那么完成这件事共有N = m1 + m2 + + mn种不同的方法和分步乘法计数原理又称为乘法原理分步乘法计数原理 完成一件事，需要分成n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法做第n步有mn种不同的方法那么完成这件事共有N = m1 m2 mn种不同的方法 例1 某班共有男生28名、女生20名，欲从该班选出学生代表参加校学代会（1）若学校分配给该班1名代表，有多少种不同的选法？（2）若学校分配给该班男、女生代表各1名，有多少种不同的选法？解 （1）选出1名代表有2类
5、办法：第1类办法是从男生中选出1名代表，有28种方法；第2类办法是从女生中选出1名代表，有20种方法根据分类加法计数原理，不同的选法种数是N = m1 + m2 = 28 + 20 = 48（2）选出男、女生代表各1名，可以分成2个步骤完成：第1步，选1名男生代表，有28种方法；第2步，选1名女生代表，有20种方法根据分步乘法计数原理，选出男、女生代表各1名，不同的选法种数是N = m1 m2 = 28 20 = 560答 选出1名代表有48种不同的选法；选出男、女生代表各1名，有560种不同的选法 例2 要从甲、乙、丙3名工人中选出2名分别上日班和晚班，有多少种不同的选法？分析 我们可以从甲
6、、乙、丙3名工人中任选1人上日班，再从余下的两人中任选1人上晚班为了便于分析，可画出如下的树图：丙甲乙乙甲丙甲乙丙画树形图可清楚地显示选法的情况解 从3名工人中选出2名分别上日班和晚班，可以分两个步骤来完成：第1步，先从甲、乙、丙3名工人中任选1名上日班，共有3种选法；第2步，从余下的2名工人中任选1名工人上晚班，有2种选法根据分步乘法计数原理，所求的不同的选法数是N = 3 2 = 6答 从3名工人中选出2名分别上日班和晚班，有6种不同的选法例 3 （1）在图7.1.3的电路中，只合上一只开关以接通灯泡，有多少种不同的方法？（2）在图7.1.2中，分别在A、B中各合上一只开关以使电路接通，有
7、多少种不同的通电线路？图7.1.4图7.1.3解 （1）在图7.1.3按要求接通灯泡，只要在A中的两个开关或B中的三个开关中合上一只开关，就能使灯泡接通。故有2+3=5种不同的方法。（2）在图7.1.4中，按要求接通灯泡必须分两步进行：第一步，合上A中的一只开关，第二步，再合上B中的一只开关。故有23=6种不同的通电线路。答 图7.1.3的电路中，只合上一只开关以接通灯泡，有5种不同的方法，图7.1.2中，分别在A、B中各合上一只开关以使电路接通，有6种不同的通电线路。例4 许多提供免费电子信箱的服务为了确保电子信箱的安全，在注册时，通常要设置电子信箱密码（1）甲规定：信箱密码为4位，每位均为
8、0到9这10个数字中的一个数字那么在甲可注册多少个免费电子信箱？（2）乙规定：信箱密码为4位，每位是0到9这10个数字中的一个，或是从A到Z这26个字母中的1个那么在乙可注册多少个免费电子信箱？ （3）丙规定：信箱密码为46位，每位均为0到9这10个数字中的一个那么在丙可注册多少个免费电子信箱？ 解 （1）设置四位密码，每一位上都可以从0到9这10个数字中任取一个，有10种取法根据分步乘法计数原理，四位密码的个数是N = 10 10 10 10 = 10 000（2）设置四位密码，每一位上都可以从0到9这10个数字或从字母A到Z这26个字母中任取一个，共有10 + 26 = 36种取法根据分步
9、乘法计数原理，四位密码的个数是N = 36 36 36 36 = 1 679 616（3）设置一个由0到9这10个数字组成的46位密码，有3类办法：第一类办法是设置4位密码；第二类办法是设置5位密码；第三类办法是设置六位密码第一类办法可以设置4位密码的个数为m1 = 10 10 10 10 = 104；同理，第二、三类办法可以设置5，6位密码的个数分别为m2 = 105，m3 = 106根据分类加法计数原理，设置由数字0到9组成的46位密码的个数是N = m1 + m2 + m3 = 104 + 105 + 106 = 1 110 000答 在甲、乙和丙分别可注册10 000，1 679 61
10、6，1 110 000个免费电子信箱思 考在甲、乙、丙三个中申请免费电子信箱，哪一个比较安全？练 习1乘坐公共交通工具从甲地到相距较远的乙地，可以乘飞机，也可以乘火车，还可以乘长途汽车一天中，飞机有2个航班，火车有4班，长途汽车有10班那么一天中，乘坐这些公共交通工具从甲地到乙地共有多少种不同的走法？ 2手表厂为了供应更多新颖款式的手表，为统一的机芯设计了4种形状的外壳、2种颜色的表面及3种形状的数字，问： （1）可分为几个步骤考虑手表款式的种数？ （2）完成每个步骤分别有几种方法？ （3）共有几种不同的款式？3几个朋友出其不意地造访小，此时正是晚饭时间小迅速看了一下食品储藏室和冰箱中的存货：
11、4种肉食、7种蔬菜、3种面包和2种土豆食品问：小能做出多少种由一种肉食、一种蔬菜、一种面包和一种土豆组成的不同饭菜？4某街道社区有甲、乙、丙3名青年志愿者，要从他们3人中选出两人分别参加于下周六和下周日举行的青年志愿者活动，共有多少种不同的选法？5现有高中一年级的学生4名，高中二年级的学生5名，高中三年级的学生3名（1）从中任选1人参加夏令营，有多少种不同的选法？（2）从3个年级的学生中各选1人参加夏令营，有多少种不同的选法？甲丙乙（第6题）6如图，从甲地到乙地有3条陆路可走，从乙地到丙地有2条陆路可走，又从甲地不经过乙地到丙地有2条水路可走 （1）从甲地经乙地到丙地有多少种不同的走法？ （2
12、）从甲地到丙地共有多少种不同的走法？74名学生报名参加数学、计算机、航模兴趣小组，每人选报1种，则不同的报名种数有（ ） A 种 B种 C3 2 1种 D4 3 2种习题 71 感受理解 1为了准备晚饭，小找出了3种冷冻蔬菜、5种罐装蔬菜和4种不同的新鲜蔬菜如果晚饭时小只上一种蔬菜，那么共有多少种可能的选择？2在选修课程目录中，一个学生在选修系列3中发现了4门有趣的课程，在选修系列4中发现了6门有趣的课程如果这个学生决定在选修系列3和选修系列4中各选一门有趣的课程作为新学期的选修课，那么他有多少种可能的选择？3如图，从甲地到乙地有3条路，从乙地到丁地有2条路；从甲地到丙地有2条路，从丙地到丁地
13、有4条路从甲地到丁地共有多少种不同的走法？AB（第4题）甲丁丙（第3题）乙4如图，一条电路在从A处到B处接通时，可以有多少条不同的线路？5（1）连续抛掷一颗骰子两次，用树图画出正面朝上的点数的所有可能 （2）第一次抛壹元币，第二次抛伍角币，第三次抛壹角币，试用树图画出三次抛掷后三种硬币向上是正面或是反面的所有可能6从1，2，3，4四个数字中，每次取出两个数字组成两位数（1）若两位数中的数字不许重复使用，那么能得到多少个不同的两位数？（2）若两位数中的数字允许重复使用，那么能得到多少个不同的两位数？7用1，5，9，13中任意一个数作分子，4，8，12，16中任意一个数作分母，可构造多少个不同的分数？可构造多少个不同的真分数？8（1）乘积 (a + b + c + d)(m + n)(x + y + z) 展开后共有多少项？ （2）aibj 共有多少项？AB（第10题）9如图，从A沿街道走到B，使路程最短的走法有多少种？ABCDEF（第9题） 思考运用 10如图，从A沿街道走到B，使路程最短的走法有多少种？11以正方形的四个顶点中某一顶点为起点、
