第7章 计数原理 JI SHU YUAN LI
计数原理
两个基本原理 ………………………… 5 排列 …………………………………… 11 组合 …………………………………… 21 二项式定理 …………………………… 31
二项式定理 ……………………… 31
二项式系数的性质 ……………… 33
选修系列2 谓数为难穷，斯可；谓数为不可穷，斯不可.何则？彼其冥冥之中，固有昭昭者存.
李治：《测圆海镜》序 深信……有待探索的自然界是有规律的.相信基本规律是简明单纯的.
爱因斯坦
下图是某城市的街道．西北角是某同学的家，东南角是学校，问从家经东西5条街南北4条街到学校（最短距离）有几种走法？
在计算机中，是以二进制（只有0、1两个数码，逢二进一）串作为存储单元的地址的。如果一台计算机的存储器有一百万个单元，那么表示地址的二进制串必须要多长才能使每个单元都有它自己的地址呢？
从古到今，人们在社会生活的各个方面都常需要进行计数，如电话号码的编排、密码的设定、彩票设计、集成电路的布线安排，以及电子计算机的程序编制……，等等．
本章中，我们将研究
● 怎样用数学模型刻画计数问题？ ● 如何利用计数模型解决实际问题？
7.1 两个基本原理
4 计数原理 第7章
调查某市职工和农民家庭中按人均月收入划分的户数如下 户数 城市职工 农民 合计 500以下 8 413 421 500元以上 221 358 579 合计 229 771 1000 根据这组数据分别估计在该市任取一家庭，其人均月收入在500以下元的概率和在该市任取两个家庭，其中一个家庭人均月收入在500以下，另一家庭人均月收入在500元以上的概率。
● 上述两个问题有怎样的区别？
他们都是计数问题，但在问题（1）中，任选一种方法都能达到完成事件的目的，而在问题（2）中，必须分为两个步骤，依次连续完成全部的步骤，才能达到完成该事件的目的．
首先考察问题（1）．
乘坐汽车有3班，每一班汽车都可以完成从甲地到乙地这件事，而乘火车有2班，每一班火车也都能完成从甲地到乙地这件事，所以共有
3 + 2 = 5 种不同的走法．
再考察问题（2）．
必须经过先从甲地走到乙地，再从乙地到丙地两个步骤，才能完成从甲地经乙地到丙地这件事．
从甲地走到乙地有3走法，从乙地到丙地有2种走法．所以，从甲地经乙地到丙地共有
2 × 5 = 10
种不同的走法（图7-1-1）．
一般地，我们有
分类加法计数原理 完成一件事，有n类方式，在第1类方式中有m1种不同的方法，在第2类方式中有m2种不同的方法……在第n类方式中有mn种不同的方法．那么完成这件事共有
N = m1 + m2 + … + mn
种不同的方法．
和
分步乘法计数原理 完成一件事，需要分成n个步骤，做第1
分步乘法计数原理又称为乘法原理．
5 分类加法计数原理又称为加法原理． 选修系列2 步有m1种不同的方法，做第2步有m2种不同的方法……做第n步有mn种不同的方法．那么完成这件事共有
N = m1 ? m2 ? … ? mn
种不同的方法．
例1 某班共有男生28名、女生20名，欲从该班选出学生代表参加校学代会．
（1）若学校分配给该班1名代表，有多少种不同的选法？ （2）若学校分配给该班男、女生代表各1名，有多少种不同的选法？
解 （1）选出1名代表有2类办法：第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名分别上日班和晚班，有多少种不同的选法？
分析 我们可以从甲、乙、丙3名工人中任选1人上日班，再从余下的两人中任选1人上晚班．为了便于分析，可画出如下的树图：
画树形图可清楚地显示选法的情况．
乙 甲 丙
甲 乙 丙
甲 丙 乙
解 从3名工人中选出2名分别上日班和晚班，可以分两个步骤来完成：
第1步，先从甲、乙、丙3名工人中任选1名上日班，共有3种选法；
第2步，从余下的2名工人中任选1名工人上晚班，有2种选法． 根据分步乘法计数原理，所求的不同的选法数是
N = 3 ? 2 = 6．
6 计数原理 第7章 答 从3名工人中选出2名分别上日班和晚班，有6种不同的选法．
例 3 （1）在图7.1.3的电路中，只合上一只开关以接通灯泡，有多少种不同的方法？
（2）在图7.1.2中，分别在A、B中各合上一只开关以使电路接通，有多少种不同的通电线路？
图7.1.4 图7.1.3
解 （1）在图7.1.3按要求接通灯泡，只要在A中的两个开关或B中的三个开关中合上一只开关，就能使灯泡接通。故有
2+3=5
种不同的方法。
（2）在图7.1.4中，按要求接通灯泡必须分两步进行：第一步，合上A中的一只开关，第二步，再合上B中的一只开关。故有
2×3=6
种不同的通电线路。
答 图7.1.3的电路中，只合上一只开关以接通灯泡，有5种不同的方法，图7.1.2中，分别在A、B中各合上一只开关以使电路接通，有6种不同的通电线路。
例4 许多网站提供免费电子信箱的服务．为了确保电子信箱的安全，在注册时，通常要设置电子信箱密码．
（1）甲网站规定：信箱密码为4位，每位均为0到9这10个数字中的一个数字．那么在甲网站可注册多少个免费电子信箱？
（2）乙网站规定：信箱密码为4位，每位是0到9这10个数字中的一个，或是从A到Z这26个字母中的1个．那么在乙网站可注册多少个免费电子信箱？
（3）丙网站规定：信箱密码为4~6位，每位均为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种取法．
根据分步乘法计数原理，四位密码的个数是
7