分类、分步与计数对象

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

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

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

当 $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}$ 个子集包含，因为固定选择它后，其余元素任取。因此

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

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

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

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

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

例如 $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$，且它严格位于两端之间。

故三元子集数为

当 $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$ 个，则

矛盾。若每个抽屉都多于 $\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$ 类，至少两人同月出生。这个结论只保证存在，不指出具体哪两人，也不计算满足条件的组合数。分类若重叠或遗漏，不能直接应用上述求和关系。