第六十六讲 加法原理和乘法原理讲义-2025-2026学年高二上学期数学人教A版选择性必修第三册

第六十六讲 加法原理和乘法原理

1. 加法原理

加法原理和乘法原理是组合计数的两个基本原理, 是探究更复杂的计数问题的基础。加法原理简单来说就是分类计算。用集合的语言来叙述，可表述为如下形式。

加法原理 将一个有限集合 划分为有限个互不相交的子集 (即对 ,有 ,且 ),则有

我们用 (有时也用 )表示有限集 的元素个数。加法原理的正确性是显而易见的。在运用加法原理时, 往往是需要计数的对象集合,通过某种方式将计数的对象分为若干类 ,这些类互不相交且包含所有的计数对象,则总数等于各类的数目之和。

例 1 问集合 有多少个三元子集,其中三个数两两互素。

解 显然至多含有一个偶数。

情形一:若不含偶数，则从 1，3，5，7，9 中选三个数，不能同时选 3 和 9，有 种方法。

情形二:若恰有一个偶数，记为 。若 ，则从1,3,5,7,9中再选两个数,且不能同时选 3 和 9,有 种方法,又 有三种可能,故总共 种选取方法。若 ，则另外两个奇数只能从 1，5，7 中选取，共有 3 种方法。若 ，则另外两个奇数只能从1,3,7,9中选取,且不能同时选 3 和 9,故有 种方法。

综上所述，由加法原理得，共有 个满足要求的三元子集。

例 2 设整数 。求三边长度均为整数,且有两边之和等于 的三角形个数。

解 记这样的三角形个数为 。设三边为 ,满足 ,且 。 则 需满足的充分必要条件为 。因此对固定的 ,第三条边 的选取方法数为 。对 求和有

2. 乘法原理

加法原理应用于计数对象可以分成几类, 对每一类分别计算。而如果计数的对象可以分成几个步骤加以构造, 则通常可以应用乘法原理。

乘法原理 设完成一件事需要 个步骤,对 ,不论前 步的结果如何,完成第 个步骤的方法数总是 ,则完成这件事共有 种不同的方法。

需要注意的是乘法原理中只要求完成第 个步骤的方法数不依赖于之前步骤的结果,而完成第 个步骤的方法可能依赖于之前步骤的结果。这在下面的例子中可以看到。

例 3 从一个 元集合 中选取 个互不相同的元素 排成一列, 。求有序组 的个数。

解 选取有序组 分 步进行。第一步,选取 ,有 种方法。第二步,选取 。由于 ,不论 为何值,完成第二步的方法数总是 。以此类推,第 步选取 的方法数为 。由乘法原理得,选取 , 的方法数为 。

评注 在选取第二个元素 时, 的取值范围与 的值有关,但 的选取方法数与 的值无关,总是 。

从一个 元集合中选取 个不同的元素排成一列,称为 的一个 元排列,其个数称为排列数,记为 ,本例证明了

在 时,即为 个元素的全排列数 。

例 4 证明: 一个 元集合的子集共有 个。

证明 设 。选取 的一个子集可以经过 个步骤,第 个步骤 确定是否放入元素 ,这有两种方式。当这 步做完后即可得到一个 的子集,如果某一步中的做法不同,就产生 的不同的子集。因此由乘法原理可知 的子集个数为 。

加法原理和乘法原理经常在计数问题中混合使用。在有些问题中直接计算符合要求的对象较为麻烦时, 也可以采取从总量中扣除不符合要求的对象, 例 1 中已经使用了这样的处理。

例 5 有多少个小于 1000 的正整数 ,满足 与 1000- 的十进制表示均不含数码 0 ?

解 记 。

若 是一位数,则 ,而 ,其中 ,故 9 个一位数都满足要求。

若 是两位数,设 ,则 。当且仅当 时, 。故两位数中满足条件的 有 个。

若 是三位数,设 。则 ,