计数：加法与乘法原理

• 加法原理：做一件事有 $n$ 类互不重叠的办法，各类分别有 $m_1,m_2,\dots ,m_n$ 种，总数是 $m_1+m_2+\cdots +m_n$。关键词是“或”——选一类即可完成。
• 乘法原理：做一件事要依次经过 $n$ 步，各步分别有 $m_1,\dots ,m_n$ 种，总数是 $m_1{m}_2\cdots m_n$。关键词是“且”——每步都要做。

分类要求不重不漏：任何一种办法恰好落入一类。分步要求步与步独立，前一步的选择不影响后一步的种数（否则要分类讨论）。

• 用加法前检查各类是否互斥，重叠部分要用容斥减回去；
• 用乘法前检查是否“算顺序”了不该算的：三个小球放进三个盒子这类题，盒子有编号与无编号是两道题；
• “至少”型问题可以正难则反：总数减去对立面的数目。

数目不大时直接列举，但要按固定顺序（字典序、从小到大）数，并在草稿上画树状图或表格，保证不重不漏。竞赛里枚举结果常用来检验公式。

例1 分步

用 $1$、$2$、$3$、$4$ 组成无重复数字的两位数，其中偶数有多少个？

解：偶数要求个位是偶数，分两步：

第一步选个位：$2$ 或 $4$，共 $2$ 种；第二步选十位：剩下 $3$ 个数字任选，$3$ 种。

乘法原理：$2\times 3=6$ 个。先定受限最强的位置（个位），是组数字题的通用顺序。

例2 分类

从 $1$ 到 $20$ 中取两个不同的数，使它们的和是 $5$ 的倍数，有多少种取法？

解：按除以 $5$ 的余数分类：余 $0$ 有 $4$ 个，余 $1$、$4$ 各 $4$ 个，余 $2$、$3$ 各 $4$ 个。

和是 $5$ 的倍数的组合有两类：两数都余 $0$；一余 $1$ 一余 $4$；或一余 $2$ 一余 $3$。共三类。

• 余 $0$ 里取两个：$C_4^2=6$；
• 余 $1$ 配余 $4$：$4\times 4=16$；
• 余 $2$ 配余 $3$：$4\times 4=16$。

加法原理：$6+16+16=38$ 种。余数分类把“和的条件”变成了“类的搭配”，是整除计数题的第一反应。

例3 正难则反

从 $1$ 到 $10$ 中取三个不同的数，使其中没有两个数的和等于 $11$，有多少种取法？

解：先配对：$(1,10)$、$(2,9)$、$(3,8)$、$(4,7)$、$(5,6)$，共 $5$ 对。取出的三个数如果“没有两数和为 $11$”，就意味着每对中至多取一个，五个对最多取 $5$ 个数——与取 $3$ 个并不矛盾，所以不能直接对 $3$ 用抽屉，改用补集：

总取法 $C_{10}^3=120$。设 $A_i$ 为“取到了第 $i$ 对的两个”（$i=1,\dots ,5$），则 $|A_i|=C_8^1=8$；又三个数无法同时包含两对（那需要 $4$ 个数），诸 $A_i$ 两两互斥。

补集：$120-5\times 8=120-40=80$ 种。

本题正面枚举“每对至多取一”也可行：从 $5$ 对中选 $3$ 对、每对选一个，$C_5^3\times 2^3=80$，与补集一致。