经典的计数模型

${\sum }_{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$（$\sum$ 表示把 $k=0,1,\dots ,n$ 的各项加起来）就是所有子集的元素个数之和，因为恰含 $k$ 个元素的子集有 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 个。每个元素是 1 分，出现 $2^{n-1}$ 次，所以和是 $n\cdot 2^{n-1}$。$n=3$ 时 $0+3+6+3=12=3\times 4$。这个结论可以再用：${\sum }_{k=2}^n(k-1)\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\cdot 2^{n-1}-2^n+1$，因为全部子集的 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 之和是 $2^n$，而从 $k=0$ 加到 $n$ 的和里，$k=0$ 一项是 $-1$，$k=1$ 一项是 0，去掉它们要加回 1。$n=4$ 时 $6+8+3=17=32-16+1$。这种式子常用在“先选并集，再选分割点”的题里。

若集合的元素写成 $4+2a+b$，$a,b\in \{0,1\}$，且不同的 $(a,b)$ 给出不同的数，那么元素是 $4,5,6,7$，总和 22。按位算：常数 4 出现 4 次；$a=1$ 的情况占一半，2 出现 2 次；$b=1$ 的情况也占一半，1 出现 2 次。$4\times 4+2\times 2+1\times 2=22$。用这个方法前要确认不同的取法不会给出相同的数，因为集合里相同的数只算 1 个。

元素 $x$ 对 $|A\cup B|$ 贡献 1，当且仅当它至少在 $A,B$ 之一中。这里 $|A\cup B|$ 表示 $A\cup B$ 的元素个数，$A,B$ 遍历 $n$ 元集合的全部子集。$x$ 在 $(A,B)$ 中有 4 种状态，其中 3 种符合，其余 $n-1$ 个元素各 4 种，所以 $x$ 被计入 $3\times 4^{n-1}$ 次，再乘元素个数 $n$。有限制时分别数。例如 $U=\{1,2,3\}$，$A,B$ 是 $U$ 的子集且 $1\in A$，求 $|A\cup B|$ 之和。元素 1 有 2 种状态（只在 $A$、都在），都计入，其余 2 个元素各 4 种，计入 $2\times 4^2=32$ 次。元素 2 要计入：3 种状态，元素 1 有 2 种，元素 3 有 4 种，计入 $3\times 2\times 4=24$ 次，元素 3 也是 24 次。总和是 $32+24+24=80$。

把子集从大到小交替加减，每个元素的正负取决于子集里比它大的数有几个：有偶数个时为正，奇数个时为负。例如 $\{1,2,3,4\}$ 的所有 3 元子集，求结果之和。4 总是最大，在 3 个子集里都为正，贡献 $+12$。3 在 $\{1,2,3\}$ 里为正，在另 2 个含 3 的子集里为负，贡献 $3-3-3=-3$。2 在 $\{1,2,3\},\{1,2,4\}$ 里为负，在 $\{2,3,4\}$ 里为正，贡献 $-2$。1 总是第 3 个，都为正，贡献 $+3$。总和是 $12-3-2+3=10$。逐个检查：$2,3,2,3$，和也是 10。不限大小时，还可以切换最大元素 $m$ 配对：不含 $m$ 的子集结果为 $s$，加入 $m$ 后变成 $m-s$，每对和为 $m$。

排列也能这样算。第 $i$ 位恰为 $i$ 时，叫不动点。给每个不动点 $i$ 记 $i$ 分，求 $1,\dots ,n$ 所有排列的总分：固定 $i$，它是不动点的排列有 $(n-1)!$ 个，其中 $(n-1)!$ 表示 $(n-1)\times \cdots \times 1$，所以总分是 $(n-1)!\times (1+2+\cdots +n)$。$n=3$ 时是 $2\times 6=12$，逐个排列的得分是 $6,1,2,3,0,0$，和是 12。还有一种用法：同一批对象用两种分法数。4 个数每次去掉 1 个求和，得到 $6,7,8,9$：每个数出现在 3 个和里，所以 $3S=30$，$S=10$。5 人互相握手，每人恰握 2 次：按人数是 $5\times 2=10$ 人次，每次握手算 2 人次，所以共 5 次握手。

不求和、只求个数的题，可以把每个元素看成独立的开关。$A\subseteq B\subseteq C$ 时，每个元素看它最早进入哪一层，有 4 种状态。$\{1,2,3\}$ 上要求 $1\in A$、$3\notin B$：元素 1 只有 1 种，元素 2 有 4 种，元素 3 不在 $A,B$ 中，只看在不在 $C$，有 2 种，共 $1\times 4\times 2=8$ 组。奇偶问题用切换：$\{1,2,3,4,5\}$ 中含 2 且和为奇数的子集，含 2 的子集有 $2^4=16$ 个，切换元素 1 把和的奇偶反过来，所以奇和、偶和各占一半，有 8 个。

题目只说某符号不相邻、没说有几个时，它出现的次数 $j$ 可以是 $0,1,2,\dots$。$j=0$ 也是 $1$ 类，不能漏。每类先选位置，再填其余位置，最后相加。

要求相邻两个选中的数之间至少有 $d$ 个空位（$d\ge 0$），也就是 $x_{i+1}-x_i\ge d+1$。令 $y_i=x_i-(i-1)d$，$y_i$ 严格递增且都在 $1$ 到 $n-(j-1)d$ 内，这个对应是一一的，所以有 $\left(\genfrac{}{}{0ex}{}{n-(j-1)d}{j}\right)$ 种（$j\ge 1$）。$d=1$ 就回到不相邻的公式。如果 $n-(j-1)d<j$，一种也没有。

上界不能压紧。这时先枚举相邻两数的差（或各段空隙），再数这种差能放在几个起点。选的是不同的人时，最后再乘人的排列数。元素不相邻的条件换成“同类至多连续 2 个”时，也是空隙上界：以另一类元素为骨架，每个空隙至多放 $2$ 个。

一个选中的数，如果左右两个邻数都没选，就叫孤立元素。把选中的数分成极大连续段：段内数字连续，不同段之间至少隔 $1$ 个。无孤立元素就是每段长度至少为 $2$。先分长度，再按空隙放段。段和段不能相接，否则就成了一段，会重复计数。

$n$ 个位置围成一圈，首尾也相邻，选 $j$ 个互不相邻（$j\ge 2$）。$n<2j$ 时一种也没有，下面设 $n\ge 2j$。含位置 $1$：它的 $2$ 个邻位不能选，其余 $n-3$ 个位置排成一行，选 $j-1$ 个互不相邻，有 $\left(\genfrac{}{}{0ex}{}{n-j-1}{j-1}\right)$ 种。不含位置 $1$：其余 $n-1$ 个位置排成一行，有 $\left(\genfrac{}{}{0ex}{}{n-j}{j}\right)$ 种。两类相加。

正 $n$ 边形选 $3$ 个顶点，把圆周分成 $3$ 段，每段的边数之和是 $n$。圆周角等于所对圆弧的圆心角的一半，所以三角形是钝角三角形，当且仅当某一段弧超过半圈，即这段的边数大于 $\frac{n}{2}$。于是数钝角三角形，就是数空隙有下界的选法。

$a+b+c=m$ 的非负整数解有 $\left(\genfrac{}{}{0ex}{}{m+2}{2}\right)$ 组：$m$ 个球和 $2$ 块隔板排成一行，隔板位置有 $\left(\genfrac{}{}{0ex}{}{m+2}{2}\right)$ 种。把 $1,\dots ,n$ 按顺序切成若干段，就是选切口。要把一些数分入有序的非空组 $A,B,C$，且前一组的数都小于后一组时，先定选了 $k$ 个数（$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 种），再在这 $k$ 个数的 $k-1$ 个间隙里选 $2$ 个切口（$\left(\genfrac{}{}{0ex}{}{k-1}{2}\right)$ 种），对 $k$ 求和。

只能向右、向上、向下走且不重复经过点时，同一列里不能折返，竖直步在这一列是单方向的一段。向右的步数由起点终点决定，所以路径由“每列走哪些竖直步”决定。网格很窄时，竖直步的方向顺序很少，先列顺序，再按列分配。