主题目录

分类、分步与计数对象

基础更新于 2026-09-29

本页目录

计数的第一步是定义“一个结果是什么”，包括对象是否有标号、是否计顺序、是否允许重复。

分类相加与分步相乘

计数前先确定“一个结果”是什么，以及何时两个结果应算作同一个。两条基本原理都要求与最终结果建立不重不漏的对应。

分类加法原理

若全部结果被分成 $k$ 类，各类互不重叠，第 $j$ 类有 $m_j$ 个结果，则总数为

N=m_1+\cdots+m_k.

用集合语言表述，就是有限集合 $A_1,\ldots,A_k$ 两两不交时， $|A_1\cup\cdots\cup A_k|=\sum|A_j|$ 。每个结果恰在一个类别中出现，因而相加不重不漏。类别有重叠时需重新划分或使用容斥。

分步乘法原理

若完成一个结果需要依次作出 $k$ 步选择，并且无论前面的合法选择是什么，第 $j$ 步始终恰有 $m_j$ 种选择，同时每条完整选择路径恰好对应一个结果，则

N=m_1m_2\cdots m_k.

证明可逐步计数：第一步有 $m_1$ 条分支，每条又有 $m_2$ 种延续，故前两步有 $m_1m_2$ 种；反复应用得到总乘积。

后续选择数可以因前序选择而改变。这时应先按前序情况分类，分别乘出每条分支的结果数，再相加；不能任选一个选择数机械相乘。

怎样区分类别与步骤

一种类别内的选择已经能够独立完成一个结果，因此各类相加；一个步骤只完成结果的一部分，需要与其他步骤共同完成，因此各步相乘。

例如从两个互不重叠的社团中选一名代表，是分类；分别从两个社团各选一名代表，是分步。若社团成员重叠，前一个问题还须处理重复成员，后一个问题还须说明是否允许同一人担任两个名额。

例：不重不漏

用数字 $0,1,2,3$ 组成无重复的三位偶数。

末位为 $0$ 时，百位有 $3$ 种、十位有 $2$ 种，共 $6$ 个。末位为 $2$ 时，百位只能取 $1,3$ ，十位有剩余 $2$ 种，共 $4$ 个。两类不交，合计 $10$ 个。

对应计数与配对

设 $A,B$ 为有限集合。若能建立双射 $f:A\to B$ ，即每个 $A$ 中对象有唯一像、不同对象的像不同，且 $B$ 中每个对象都被取到，则 $|A|=|B|$ 。证明计数相等时，需要说明映射规则及其逆规则，仅凭两类对象“看起来对应”不够。

更一般地，若映射满射且每个 $b\in B$ 恰有 $r$ 个原像，原像集合将 $A$ 分成 $|B|$ 个大小为 $r$ 的互不相交部分，因此 $|A|=r|B|$ 。这就是“先计数，再除重复次数”的依据；若重复次数随结果变化，就不能统一除以一个数。

配对是特殊的对应。若变换 $T:A\to A$ 满足 $T(T(a))=a$ 且无不动点，则所有对象分成互不相交的二元组 $\{a,T(a)\}$ ，所以 $|A|$ 为偶数。若每对权值之和为固定数 $c$ ，总权值即为 $c|A|/2$ 。有不动点时须把它们单列，不能强行两两配对。数列倒写相加中的 $k\leftrightarrow n+1-k$ 就是这一思路； $n$ 为奇数时中间项对应自身。

易错点

“先分类后分步”不是固定模板，而是检查覆盖与唯一性的方法。加法原理中的互不重叠条件不能省去。

含零数字的组数：选择合适的分类

用 $0,1,2,3,4$ 组成不重复数字的三位偶数。按个位分类：

个位为 $0$ ：百位有 $4$ 种，十位有 $3$ 种，共 $12$ 个。
个位为 $2$ 或 $4$ ：个位有 $2$ 种，百位不能为零也不能与个位相同，有 $3$ 种；十位从剩余数字中选，有 $3$ 种，共 $18$ 个。

总计 $30$ 个。这里每类内使用乘法，各类互不相交后使用加法。分类标准应保证不重不漏；分步乘法不要求概率意义下的“独立”，只要求每一步对每种此前选择都有规定数量的后续选择，否则继续分类或逐支相加。

对子集中的量求总和：按原元素数贡献

设 $A=\{a_1,\ldots,a_n\}$ ，固定 $1\le r\le n$ 。把每个 $r$ 元子集中的元素相加，再对全部 $r$ 元子集求和，每个 $a_i$ 恰出现 $\binom{n-1}{r-1}$ 次，因为只需从其余 $n-1$ 个元素中再选 $r-1$ 个。所以总和为

\binom{n-1}{r-1}(a_1+\cdots+a_n).

这里计数的是带重数的子集和列表。若题目把相等的子集和合并成集合，必须先确认没有重复，才可把集合元素之和代入公式。

当 $r=n-1$ 时，令 $S=\sum a_i$ ，各和为 $b_i=S-a_i$ 。若 $n\ge2$ ，则 $\sum b_i=(n-1)S$ ，先求出 $S$ ，再用 $a_i=S-b_i$ 恢复原集合。例如三个元素之和所成集合为 $\{-1,3,5,8\}$ ，有 $n=4,S=15/3=5$ ，原集合是 $\{6,2,0,-3\}$ 。

对两元素和，也可结合排序：若五个互异实数的十个两两和互异，则总和等于原元素总和的 $4$ 倍；最小、次小两两和分别为 $a_1+a_2,a_1+a_3$ ，最大、次大分别为 $a_4+a_5,a_3+a_5$ 。已知十个和为 $3,4,5,6,7,8,9,10,11,13$ ，得 $S=76/4=19$ ， $a_3=19-3-13=3$ ，依次恢复 $a_1=1,a_2=2,a_5=8,a_4=5$ ；最后生成全部十个和，恰与给定列表一致，充分性才完成。

所有子集的大小和、交集大小和

设 $X$ 有 $n\ge1$ 个元素，其所有子集为 $A_1,\ldots,A_{2^n}$ 。

每个 $x\in X$ 被恰好 $2^{n-1}$ 个子集包含，因为固定选择它后，其余元素任取。因此

\sum_{i=1}^{2^n}|A_i|=n2^{n-1}.

若对所有有序对 $(A_i,A_j)$ （允许 $i=j$ ）求交集大小之和，则固定的 $x$ 必须同时被两集合包含，两者其余元素独立选择，共 $2^{n-1}2^{n-1}=4^{n-1}$ 次。所以

\sum_{i,j=1}^{2^n}|A_i\cap A_j|=n4^{n-1}.

若题目限制 $i\ne j$ ，还应扣掉对角和 $n2^{n-1}$ ；若只对 $i<j$ 求和，扣掉对角后再除以二。 $n=0$ 时两个总和都直接等于零，不需要引入负指数的计数解释。

交集的下界：逐步选取共同满足条件的对象

设有限全集 $U$ 有 $N$ 个元素，各条件对应集合 $A_1,\ldots,A_k$ 。由补集和并集的上界，

\left|\bigcap_{i=1}^k A_i\right| =N-\left|\bigcup_{i=1}^k A_i^c\right| \ge N-\sum_{i=1}^k|A_i^c|.

若右侧为正，就存在同时满足所有条件的对象；不要求各个失败集合互不相交。

例如 $500$ 人中每人至少认识 $401$ 人，且认识关系相互。记某人的熟人集为 $N(v)$ ，其补集包括本人及不认识的人，最多 $99$ 人。已选 $k\le5$ 个彼此认识的人后，他们熟人集的交至少有 $500-99k>0$ 人。交中的人不可能是已选者，因为每个人不在自己的熟人集中，故能再加入一人。逐步得到六个彼此认识的人。

证明包含“存在候选”与“候选不是已经选过的对象”两步，后一条件不能省略。

固定贡献计数还可以制造矛盾

假设从 $\{0,1,\ldots,9\}$ 选出五个数，两两不同元素的和除以 $10$ 的余数能覆盖 $0$ 至 $9$ 。五个数恰有 $\binom52=10$ 对，要覆盖十种余数，必须每种余数恰出现一次，因此这十个余数之和为 $45$ ，是奇数。

另一方面，每个选中数在四个两两和中出现，所以十个原始和的总和是选中数总和的四倍，是偶数。把每个原始和减去某个 $10$ 的倍数变成余数，不改变总和的奇偶性，矛盾。因此这样的五元集不存在。

方法是先确认“对象数恰等于必须覆盖的种类数”，再推出没有重复，并用同一个总量的两种计算找矛盾；没有数量相等这个前提，不能擅自说每种恰出现一次。

三项等差子集：选两端或选中点

从 $\{1,\ldots,N\}$ 选三个不同数构成等差数列。把它们升序写为 $a<b<c$ ，须 $a+c=2b$ 。因此两端 $a,c$ 必须同奇偶；反之每一对同奇偶的不同端点，都唯一确定整数中点 $b=(a+c)/2$ ，且它严格位于两端之间。

故三元子集数为

\binom{\lceil N/2\rceil}{2}+\binom{\lfloor N/2\rfloor}{2}.

当 $N=2013$ 时为 $\binom{1007}{2}+\binom{1006}{2}=1006^2$ 。也可以固定中点 $b$ ，公差 $d$ 有 $1\le d\le\min(b-1,N-b)$ 种，再对 $b$ 求和；二者计数的是同一批无序三元子集，不额外乘排列数。

抽屉原理：由总量保证存在性

把 $N$ 个对象分到 $n\ge1$ 个抽屉中，每个对象恰属于一个抽屉。记各抽屉的对象数为非负整数 $x_1,\ldots,x_n$ ，有 $x_1+\cdots+x_n=N$ 。则至少一个抽屉含有不少于 $\lceil N/n\rceil$ 个对象，也至少一个抽屉含有不多于 $\lfloor N/n\rfloor$ 个对象。

证明。 若每个抽屉都少于 $\lceil N/n\rceil$ 个，则

N=\sum x_i\le n(\lceil N/n\rceil-1)<N,

矛盾。若每个抽屉都多于 $\lfloor N/n\rfloor$ 个，则 $\sum x_i\ge n(\lfloor N/n\rfloor+1)>N$ ，也矛盾。

特别地， $m\ge0,n>1$ 为整数时，把 $mn+1$ 个对象放入 $n$ 个抽屉，必有一个不少于 $m+1$ 个，也有一个不多于 $m$ 个。第二个结论的 $n>1$ 不能省去。

若无限多个对象分入有限个抽屉，则至少一个抽屉含无限多个对象。否则每个抽屉都有限，有限个有限集的并仍有限，与对象总数矛盾。若抽屉本身无限，这个结论失效，例如每个正整数各占一个抽屉。

使用步骤与边界

先确定要放入的对象，再设计有限分类作为抽屉；证明每个对象确实落入其中一个；最后比较对象数与每个抽屉允许的容量。若目标是证明“某一类至少有 $k$ 个”，常反设各类至多 $k-1$ 个，推出总数至多 $n(k-1)$ 。

例如任取 $13$ 个人，按出生月份分成 $12$ 类，至少两人同月出生。这个结论只保证存在，不指出具体哪两人，也不计算满足条件的组合数。分类若重叠或遗漏，不能直接应用上述求和关系。

关联阅读

先修：集合运算与韦恩图。

同主题：排列、组合与圆排列。