计数原理

数え上げの原則

5 場合の数と確率／数え上げの原則 (集合の要素の個数，和の法則，積の法則を含む)

一句话结论

分类、只做其中一类，用加法；分步、每一步都要做，用乘法。加法要求各类互不重叠，有重叠就减去重叠部分；乘法要求每一步的做法个数固定。数「是 A」麻烦时，改数「不是 A」，再用全体去减。

食堂午饭有 3 种主食、4 种饮料。只买一样，有 $3+4=7$ 种买法；主食和饮料各买一样，有 $3\times4=12$ 种。同样是 3 和 4，一次相加、一次相乘，差别在于两件事是「只做其中一件」还是「两件都要做」。后面的排列、组合和概率，说到底都是在数情况数（場合の数），用的就是这两条规则；真正要花心思的，是数的时候不漏也不重。

为什么是这样

数情况要做到两点：不漏、不重（もれなく、重複なく）。最稳的办法是定一个顺序去列。一种是按字典顺序列（辞書式配列法），先按第一个字母从小到大，第一个相同再比第二个；另一种是画树形图（樹形図），第一步的每种做法画一根大枝，每根大枝上再分出第二步的做法，最末一层的每根枝梢就是一种情况。

和的法则（和の法則）：一件事分成几类做法，各类不会同时发生，总数就是各类相加。用集合的话说， $A\cap B=\varnothing$ 时 $n(A\cup B)=n(A)+n(B)$ 。两类有重叠时，重叠部分被数了两次，要减去一次（详见「集合与元素个数」）。

积的法则（積の法則）：一件事分两步完成，第一步有 $m$ 种做法，而且不论第一步怎么做，第二步都有 $n$ 种，总数就是 $mn$ 。看树形图最清楚： $m$ 根大枝，每根上都长 $n$ 根小枝，枝梢共 $m\times n$ 根。要紧的是每根大枝上小枝的个数相同，小枝具体是哪几种可以不同。用 $1\sim9$ 组成十位、个位不同的两位数，十位选了哪个，个位都还剩 8 个可选，所以有 $9\times8=72$ 个。

定量表达

约数的个数是积的法则最典型的用法。把正整数分解成 $N=p^aq^br^c$ ，它的每个正约数都写成 $p^xq^yr^z$ ， $x$ 可取 $0,1,\dots,a$ 共 $a+1$ 种， $y$ 、 $z$ 同理，三步都要选，所以正约数有 $(a+1)(b+1)(c+1)$ 个。指数取 $0$ 表示不含这个素因数，不能丢：约数 $1$ 就是三个指数都取 $0$ 。

把 $(1+p+\cdots+p^a)(1+q+\cdots+q^b)(1+r+\cdots+r^c)$ 展开，每一项是从每个括号里各取一个幂相乘，正好是一个约数，而且每个约数只出现一次，所以这个积就是正约数的总和。同一个道理， $(a+b)(x+y+z)$ 展开后有 $2\times3=6$ 项。

数「是 A」比数「不是 A」麻烦时，用补集： $n(A)=n(U)-n(\overline{A})$ 。题目说「至少一个」，它的反面是「一个也没有」。

N=p^aq^br^c\ \Longrightarrow\ \text{正约数个数}=(a+1)(b+1)(c+1),\quad\text{正约数之和}=(1+p+\cdots+p^a)(1+q+\cdots+q^b)(1+r+\cdots+r^c)

$N$: 要研究的正整数
$p,\ q,\ r$: $N$ 的互不相同的素因数
$a,\ b,\ c$: 各素因数的指数（正整数）

适用条件

先把 $N$ 分解成素因数的积；素因数个数不是 3 时，括号个数随之增减
每个括号里从指数 $0$ 写起： $p^0=1$ 对应「不含因数 $p$ 」，约数 $1$ 和 $N$ 本身都算在内

怎么用

先判断是分类还是分步：几种做法只做一种是分类，用加法；几个步骤都要做是分步，用乘法。分类时按限制最多的那个量来分，类数最少。用 100 元、50 元、10 元硬币凑出 400 元（某种可以不用），按 100 元硬币用 $0\sim4$ 枚分五类，每类里 50 元硬币的枚数一定、剩下由 10 元补足，共 $9+7+5+3+1=25$ 种。

登录后免费阅读全文

本节还有 7 部分，以及配套的真题和小测验。

免费注册登录

本节公式一览
例题
容易错在哪里
自测
小结
日文术语