利用加法原理和乘法原理计数Liyong jiafa yuanli he chengfa yuanli jishu

加法原理与乘法原理(参阅“加法原理”、“乘法原理”条)是处理计数问题的有效工具，实际运用时须特别注意以下事项：
❶什么情形下应该用乘法，什么情形下应该用加法；
❷什么情形下直接用加法原理， 什么情形下需要利用容斥原理。重复的计数怎样去除。
例1:如下图所示的直线上有5个点A、B、C、D、E. 问以它们为端点的线段共有多少条？
解： 我们对各点分别分析， 以A为端点之一的线段有AB,AC,AD, AE4条， 同样道理以B、C、D、E为端点之一的线段也各有4条， 注意到每条线段有2个端点， 在对它的每一端点进行分析时各被计入1次， 因此每条线段被计算了2次， 这样， 以A、B、C、D、E为端点的线段数目为4×5/2=10。本例使用了乘法原理。

图1

图2

例2: 问围棋盘图1中有多少与图2中小正方形一样的正方形 (第2届华罗庚金杯赛)。
解：注意审题，不要误解为图1的面积是图2的几倍。在图1中，象图2一样的正方形，上边在第一条横线的有：左边在第一条竖线的，左边在第2条竖线的，……左边在第10条竖线的，共10个。同样道理，上边在第2条横线的、上边在第3条横线的，……上边在第10条横线的也各有10个，根据乘法原理图1中与图2一样的小正方形个数为10×10=100个。
例3:分子不大于6，分母不大于40的即约真分数有多少个？
解： 我们分别考查分子是1, 2, 3, 4, 5, 6的即约真分数个数。
分子是1时，分母应不小于2，这样的即约真分数有40-1=39个。
分子是2时，分母应大于2，且不被2整除，即分母应为大于2的奇数， 介于2与40之间的奇数有19个， 故这样的即约真分数有19个。
同样的道理可知，分子为3，分母不大于40的即约真分数有25个，分子为4的有18个，分子为5的有28个。
当分子等于6时，分母应该大于6并与6互素，也就是说既不被3整除，也不被2整除，从7到40被3整除的数有11个，被2整除的数有17个，被2×3=6整除的数有5个，根据容斥原理，既不被3整除又不被2整除的数有40-(11+17-5)=17，即分子等于6分母不大于40的即约真分数有17个。
把这些数加起来， 分子不大于6, 分母不大于40的即约真分数共有39+19+25+18+28+17=146个。本题综合运用了简单的加法原理和容斥原理。