尧图网站建设 
组合恒等式、证明方法、求和方法这三件事单看任何一个都不难难的是把它们串成一条线。很多人第一次接触组合数学看到 $\sum_{k0}^n \binom{n}{k}^2\binom{2n}{n}$ 这种式子第一反应是这也能相等第二反应是考试要考吗第三反应才是这到底怎么推。我自己的经验是组合恒等式不能孤立地背必须放回“从一堆东西里选”的场景里才知道它为什么长这样。这篇就把我常用的十一个组合恒等式整理出来同时把双计数、母函数、归纳法这几类证明方法以及吸收、卷积、差分这些求和方法拆开讲。适合准备离散数学和组合数学考试的人也适合算法竞赛里推式子、概率统计里化简期望、数据分析里估算组合规模的读者。你不需要把每个证明都背下来但要知道什么时候该用哪一个。1. 十一个组合恒等式的全景地图先知道每个式子管什么1.1 组合数记号先统一别在上指标和下指标上翻车组合数记作 $\binom{n}{k}$读作“n 选 k”意思是“从 n 个不同元素里选 k 个有多少种选法”。它最常见的计算方式是阶乘形式[ \binom{n}{k}\frac{n!}{k!(n-k)!} ]其中默认 $n$ 是非负整数$k$ 是整数。如果 $k0$ 或 $kn$通常约定 $\binom{n}{k}0$。这一点非常关键因为很多求和式看起来范围很大实际上超出范围的项自动变成 0所以你可以放心地把求和范围写成 $k0$ 到 $n$甚至写成所有整数求和。后面讲上指标反转时会看到负的 $n$ 也可以定义组合数但那要额外引入广义组合数不是普通“从负个东西里选”的直观场景。初学阶段先把 $n\ge 0$、$0\le k\le n$ 这一套记稳能避免绝大部分低级错误。我这里说的“低级错误”十有八九是把 $\binom{n}{k}$ 写成 $\binom{k}{n}$或者把 $n$ 和 $k$ 谁该减一搞反。记法上建议每次写公式前先默念“上面是总数下面是取几个”这个习惯能救回很多分数。1.2 十一个恒等式总表名称、表达式、用途和记忆钩子下面这十一个式子是我在推求和时出现频率最高的。它们不是孤立的很多可以互相推导。比如二项式定理能推出全和与交错和吸收恒等式来自二项式定理求导范德蒙德恒等式可以看成两堆元素的卷积曲棍球棒恒等式是帕斯卡恒等式斜着加出来的。编号名称表达式典型用途记忆钩子1对称恒等式$\binom{n}{k}\binom{n}{n-k}$简化大下标选走 k 个等于留下 n-k 个2帕斯卡恒等式$\binom{n}{k}\binom{n-1}{k}\binom{n-1}{k-1}$递推、杨辉三角含某个特殊元素分两类3吸收恒等式$k\binom{n}{k}n\binom{n-1}{k-1}$去掉外面的 k把 k 吸进组合数4二项式定理$\sum_{k0}^n \binom{n}{k}x^k(1x)^n$母函数、系数提取所有组合求和的母体5全和恒等式$\sum_{k0}^n \binom{n}{k}2^n$子集总数每个元素选或不选6交错和恒等式$\sum_{k0}^n (-1)^k\binom{n}{k}0$奇偶抵消、容斥奇数子集和偶数子集一样多7曲棍球棒恒等式$\sum_{ir}^n \binom{i}{r}\binom{n1}{r1}$斜求和斜着加等于下一项8范德蒙德恒等式$\sum_{k0}^r \binom{m}{k}\binom{n}{r-k}\binom{mn}{r}$合并两堆组合数两堆一共选 r 个9平方和恒等式$\sum_{k0}^n \binom{n}{k}^2\binom{2n}{n}$对称卷积两堆各选相同个数10乘积分解恒等式$\binom{n}{k}\binom{k}{r}\binom{n}{r}\binom{n-r}{k-r}$重排乘积、交换求和先选小组再扩成大组11上指标反转$\binom{-n}{k}(-1)^k\binom{nk-1}{k}$负指标、广义二项式负号靠 k 的奇偶决定这张表建议自己手抄一遍不是抄表达式而是抄“用途”和“记忆钩子”。表达式可以查但用途必须变成条件反射。比如看到外面挂着 $k$立刻想到吸收看到两个组合数相乘且下标相加为常数立刻想到范德蒙德看到 $\sum_{ir}^n \binom{i}{r}$立刻想到曲棍球棒。很多时候推不出来不是因为你不会算而是因为没认出式子的形状。1.3 选择标准十一个式子覆盖了哪些求和形态为什么选这十一个而不是六个或者二十个因为我选的标准是“能否覆盖常见求和动作”。第一类是对称和边界处理包括对称恒等式、全和、交错和它们负责把复杂范围变简单。第二类是递推和吸收包括帕斯卡、吸收、曲棍球棒它们负责降指标、消掉外面的 $k$、处理斜向求和。第三类是卷积和乘积重排包括范德蒙德、平方和、乘积分解它们负责把两个组合数相乘的求和合并成一个组合数。第四类是母函数和负指标包括二项式定理和上指标反转它们负责把求和变成系数提取或者把负上指标转成正指标。你把这四类练熟绝大多数本科组合数学题和算法竞赛里的组合求和都能找到切入点。剩下的一些恒等式比如三项式系数、莫比乌斯反演、斯特林数恒等式本质上是这些基础动作的延伸。先把十一个基础动作打牢再扩展会轻松很多。2. 证明方法不玄学双计数、母函数、归纳法到底怎么选2.1 双计数法把等式两边讲成同一个选择故事双计数法是组合证明里最漂亮的方法也是最适合建立直觉的方法。它的核心只有一句话等式两边都在数同一个集合所以相等。以帕斯卡恒等式为例左边 $\binom{n}{k}$ 是从 n 个元素里选 k 个。右边分成两类不选某个特定元素 $a$就要从剩下 $n-1$ 个里选 k 个方案数是 $\binom{n-1}{k}$选 $a$就要从剩下 $n-1$ 个里再选 $k-1$ 个方案数是 $\binom{n-1}{k-1}$。两类不重不漏所以相加相等。范德蒙德恒等式也可以用双计数有 m 个红球和 n 个蓝球一共选 r 个球的方法是 $\binom{mn}{r}$而按红球个数 k 分类就是 $\sum_k \binom{m}{k}\binom{n}{r-k}$。平方和恒等式 $\sum_k \binom{n}{k}^2\binom{2n}{n}$ 可以看成有两组各 n 个元素从第一组选 k 个、第二组选 k 个再让 k 跑遍所有可能等价于从 2n 个元素里选 n 个。双计数法的难点不在于计算而在于你能不能构造出正确的“故事”。我的经验是先看等式两边谁更像“总数”然后把另一边按某个变量分类。分类标准通常就是求和指标比如红球个数、是否包含特殊元素、第一组选了几个。只要分类不重不漏证明就成立。2.2 母函数与代数变形把求和塞进 $(1x)^n$母函数法适合处理带 $x^k$ 或 $x^{n-k}$ 的求和。二项式定理是核心[ (1x)^n\sum_{k0}^n \binom{n}{k}x^k ]这个式子厉害的地方在于它把整个组合数序列打包成一个多项式。你想证明某个求和可以把两边乘以 $x^r$ 再取系数或者令 $x1$、$x-1$ 得到特殊值。全和恒等式令 $x1$ 就得到 $\sum_k \binom{n}{k}2^n$交错和恒等式令 $x-1$ 就得到 $\sum_k (-1)^k\binom{n}{k}0$。吸收恒等式也可以从二项式定理求导得到两边对 $x$ 求导得到 $n(1x)^{n-1}\sum_k k\binom{n}{k}x^{k-1}$再比较系数。母函数法的优点是机械、可复制不需要每次构造组合故事缺点是容易算错系数尤其是求导、乘法和变量替换的时候。我的建议是如果你对组合场景敏感优先用双计数如果你对代数操作更稳或者求和里带变量 $x$优先用母函数。两种方法最好都掌握因为考试和实际推导中经常需要交叉验证。2.3 归纳法与递推适合带 n 的斜求和归纳法适合证明关于 n 的恒等式尤其是曲棍球棒这种带求和上界的式子。以[ \sum_{ir}^n \binom{i}{r}\binom{n1}{r1} ]为例固定 r对 n 做归纳。基础情形 $nr$ 时左边是 $\binom{r}{r}1$右边是 $\binom{r1}{r1}1$成立。假设对 n 成立当 n 变成 n1 时左边增加的是 $\binom{n1}{r}$右边从 $\binom{n1}{r1}$ 变成 $\binom{n2}{r1}$。根据帕斯卡恒等式[ \binom{n2}{r1}\binom{n1}{r1}\binom{n1}{r} ]所以增量正好对上。归纳法写起来规范但关键是找到“增量”和“递推式”的对应关系。很多初学者归纳法失败是因为直接从左边硬推右边而不是先看从 n 到 n1 新增了哪一项。记住一个套路凡是有求和上界且右边是个单独组合数通常都可以考虑归纳。归纳法的缺点是不太能解释“为什么”它证明了正确性但没有告诉你这个式子是怎么被发现的。所以做完归纳之后最好再用双计数或曲棍球棒的图像解释一遍印象会深很多。2.4 证明方法选择表看到什么特征用什么方法等式特征首选证明备选容易踩的坑一边是单个组合数另一边是两个组合数相加双计数、帕斯卡归纳分类过细导致重复带 $x^k$ 或要求特殊值母函数、二项式定理代数变形系数提取时忘记常数项求和上界是 n右边是 n1 的组合数归纳法双计数增量项写错两个组合数相乘下标相加为常数范德蒙德卷积母函数上下指标搞反外面挂着 $k$ 或 $k^2$吸收恒等式求导忘记 $n$ 的因子带 $(-1)^k$交错和、容斥令 $x-1$边界项没有抵消干净上指标为负上指标反转广义二项式负号指数漏写这张表建议贴在书桌前。实际推导时先判断式子形状再选方法比一上来就硬算高效得多。我的体会是组合恒等式证明最怕“无脑展开阶乘”因为阶乘一展开式子会爆炸而且很难看出对称性。先形状、后方法、再计算这个顺序很重要。3. 十一个恒等式逐个拆解证明思路、适用场景和记忆锚点3.1 对称恒等式为什么选 k 个等于留下 n-k 个对称恒等式是[ \binom{n}{k}\binom{n}{n-k} ]它的直观解释是从 n 个元素里选 k 个带走的方案数等于从 n 个元素里留下 n-k 个不带的方案数。选和留是一一对应的你每选出一个 k 元子集就确定了一个 n-k 元的补集。这个式子看起来简单但用途很广。比如 $\binom{100}{98}$ 可以直接写成 $\binom{100}{2}$计算量瞬间下降。再比如在求和时如果出现 $\binom{n}{k}$ 和 $\binom{n}{n-k}$可以利用对称性把两项合并或者配对。注意对称恒等式只对普通的非负整数 n 和整数 k 成立如果引入负上指标形式会变成上指标反转那个样子。记忆锚点选走的就是留下的补集所以“选 k 个”和“选 n-k 个”等价。3.2 帕斯卡恒等式杨辉三角的加法规则帕斯卡恒等式是[ \binom{n}{k}\binom{n-1}{k}\binom{n-1}{k-1} ]杨辉三角里每个数等于上方两个数之和就是它在驱动。双计数证明很干净固定一个元素 a从 n 个里选 k 个。如果不选 a就从剩下 n-1 个里选 k 个如果选 a就从剩下 n-1 个里选 k-1 个。两类合起来就是全部。这个式子是递推计算组合数的基础也是很多恒等式的源头。曲棍球棒恒等式就是沿着杨辉三角的斜线累加。用帕斯卡恒等式时要注意边界当 $k0$ 时$\binom{n-1}{-1}$ 约定为 0当 $kn$ 时$\binom{n-1}{n}$ 约定为 0。很多人写递推代码时忘记处理这两个边界导致数组越界。记忆锚点分“含特殊元素”和“不含特殊元素”两类。3.3 吸收恒等式把外面的 k 收进组合数吸收恒等式是[ k\binom{n}{k}n\binom{n-1}{k-1} ]它解决的是求和里最烦人的“外面挂着一个 k”。证明可以用双计数从 n 个人里选 k 个人组成小队再从 k 个人里选一个队长方案数是 $k\binom{n}{k}$也可以先选队长n 种再从剩下 n-1 个人里选 k-1 个队员方案数是 $n\binom{n-1}{k-1}$。两种数法结果一样。这个式子可以把 $k$ 从组合数外面“吸”进去同时把 n 降成 n-1k 降成 k-1。比如求 $\sum_k k\binom{n}{k}$直接用吸收恒等式变成 $n\sum_k \binom{n-1}{k-1}n2^{n-1}$。如果外面是 $k^2$可以连续用两次吸收或者把 $k^2$ 写成 $k(k-1)k$再分别吸收。注意吸收时不要漏掉 n 这个因子也不要忘记下标同时减一。记忆锚点选队长模型先选人再选队长或者先选队长再选人。3.4 二项式定理所有组合求和的母体二项式定理是[ (1x)^n\sum_{k0}^n \binom{n}{k}x^k ]它不仅是代数公式更是组合求和的母函数。你可以把它看成“每个元素要么贡献 1要么贡献 x”的生成过程展开时每个括号选 1 还是选 x选 x 的元素个数为 k对应项就是 $\binom{n}{k}x^k$。令 $x1$ 得到全和令 $x-1$ 得到交错和求导可以得到带 k 的求和乘以 $x$ 再求导可以得到带 $k^2$ 的求和。二项式定理的推广是广义二项式定理[ (1x)^\alpha\sum_{k0}^\infty \binom{\alpha}{k}x^k ]其中 $\alpha$ 可以是负数或实数这也是上指标反转的来源之一。使用二项式定理时最常见的问题是把 $(1x)^n$ 和 $(x1)^n$ 混了其实它们相等但系数提取时要注意哪个变量对应哪个指数。记忆锚点所有子集按大小打包系数就是组合数。3.5 全和恒等式所有子集数就是 2 的 n 次方全和恒等式是[ \sum_{k0}^n \binom{n}{k}2^n ]它的组合意义最直接n 个元素组成的集合所有子集的总数是 $2^n$因为每个元素都有“选”和“不选”两种状态。按子集大小 k 分类大小为 k 的子集有 $\binom{n}{k}$ 个所以求和就是子集总数。这个式子是很多概率计算的基础。比如抛 n 次硬币所有可能结果数是 $2^n$恰好出现 k 次正面的结果数是 $\binom{n}{k}$把它们加起来还是 $2^n$。注意当 n 为 0 时左边是 $\binom{0}{0}1$右边是 $2^01$也成立。使用全和恒等式时要确保求和范围覆盖所有可能的 k如果只求一部分比如 $\sum_{k0}^m \binom{n}{k}$那就没有简单的单项闭式不能直接写成 $2^n$ 的一部分。记忆锚点每个元素选或不选总共 $2^n$ 种。3.6 交错和恒等式奇偶子集一样多交错和恒等式是[ \sum_{k0}^n (-1)^k\binom{n}{k}0 \quad (n\ge 1) ]它的含义是当 n 至少为 1 时偶数大小子集的数量等于奇数大小子集的数量。证明可以用二项式定理令 $x-1$也可以构造配对固定一个元素 a把子集分成含 a 和不含 a 的两类含 a 的子集与不含 a 的子集奇偶性相反可以一一配对。当 n0 时左边只有 $\binom{0}{0}1$右边不是 0所以通常要求 n≥1。这个恒等式在容斥原理、二项式反演、差分算子中非常重要。遇到带 $(-1)^k$ 的求和第一反应就是看能不能用交错和或配对消去。注意符号不要漏尤其是 $(-1)^k$ 和 $(-1)^{k1}$ 的转换。记忆锚点奇偶子集成对抵消除了空集那种特殊情况。3.7 曲棍球棒恒等式斜着加为什么等于下一项曲棍球棒恒等式是[ \sum_{ir}^n \binom{i}{r}\binom{n1}{r1} ]在杨辉三角里从某一项开始沿着左下到右上的斜线累加结果等于斜线末端下一行的数形状像曲棍球棒。证明可以用帕斯卡恒等式反复展开[ \binom{n1}{r1}\binom{n}{r1}\binom{n}{r} ]而 $\binom{n}{r1}$ 又可以继续拆最后得到从 $\binom{r}{r}$ 到 $\binom{n}{r}$ 的和。也可以双计数从 n1 个元素里选 r1 个按最大元素的位置分类。这个恒等式在求 $\sum_{ir}^n \binom{i}{r}$ 这种斜求和时非常有用。注意求和下限必须是 r因为当 ir 时 $\binom{i}{r}0$写成 i0 也可以但下限写 r 更直观。记忆锚点斜线累加等于下一行右斜一项。3.8 范德蒙德恒等式两堆东西分成 r 个的卷积范德蒙德恒等式是[ \sum_{k0}^r \binom{m}{k}\binom{n}{r-k}\binom{mn}{r} ]它描述的是两堆元素的合并选择有 m 个红球和 n 个蓝球一共选 r 个球按选了多少个红球分类就是左边直接看成从 mn 个球里选 r 个就是右边。这个式子是组合卷积的核心平方和恒等式就是 mnr 的特殊情形。范德蒙德恒等式还可以推广到多项式系数但基础版本足够处理大多数求和。使用时要注意上下标第一个组合数从 m 里选 k第二个从 n 里选 r-kk 的范围是 0 到 r但如果 km 或 r-kn对应项自动为 0。很多人会把两个组合数的上指标写反或者把 r-k 写成 k-r。记忆锚点红蓝两堆按红球个数分类。3.9 平方和恒等式两堆各选相同个数平方和恒等式是[ \sum_{k0}^n \binom{n}{k}^2\binom{2n}{n} ]它看起来像是范德蒙德恒等式在 $mnr$ 时的特例[ \sum_{k0}^n \binom{n}{k}\binom{n}{n-k}\binom{2n}{n} ]再利用对称恒等式 $\binom{n}{n-k}\binom{n}{k}$就得到平方和。组合意义也很清楚有两组各 n 个元素先从第一组选 k 个再从第二组选 k 个总共选 n 个也可以直接从 2n 个元素里选 n 个。这个恒等式在概率论中经常出现比如超几何分布、随机游走、中心二项式系数估计。注意平方和恒等式没有简单的“部分和”版本如果你把求和上限改成 mn一般不能写成单个组合数。记忆锚点两组各选 k 个合起来是 2n 里选 n 个。3.10 乘积分解恒等式先选小组再扩成大组乘积分解恒等式是[ \binom{n}{k}\binom{k}{r}\binom{n}{r}\binom{n-r}{k-r} ]它的组合意义是从 n 个人里先选 k 个人再从这 k 个人里选 r 个人当核心成员等价于先从 n 个人里直接选 r 个人当核心成员再从剩下的 n-r 个人里选 k-r 个人加入外围。两边数的都是“n 个人里有一个 r 人核心组和一个 k 人小组核心组包含于小组”的方案数。这个恒等式在交换求和次序时特别好用因为它可以把依赖 k 的组合数拆成两个独立部分或者把内层求和变成曲棍球棒。使用时注意下标$k-r$ 必须非负所以 k≥r。如果求和里出现 $\binom{n}{k}\binom{k}{r}$不要急着展开阶乘先用这个恒等式重排往往能直接看出曲棍球棒或范德蒙德。记忆锚点先选核心再选外围。3.11 上指标反转负上指标怎么变正上指标反转恒等式是[ \binom{-n}{k}(-1)^k\binom{nk-1}{k} ]它处理的是负上指标的组合数。普通组合数要求上指标非负但在广义二项式定理和某些求和里会出现负数。这个式子把负上指标转成正的代价是前面多一个 $(-1)^k$。例如[ \binom{-1}{k}(-1)^k ]因为 $\binom{1k-1}{k}\binom{k}{k}1$。这个恒等式在生成函数中很常见比如 $(1-x)^{-n}$ 的展开。使用时要注意负号只由 k 的奇偶决定与 n 无关右边的组合数是 $\binom{nk-1}{k}$不是 $\binom{n}{k}$。很多初学者会把上指标反转和对称恒等式混用导致符号错误。记忆锚点负上指标转正符号看 k 的奇偶。4. 组合求和方法遇到和式先做这四步4.1 第一步统一上下指标和求和范围拿到一个组合求和不要立刻算。先做三件事统一组合数的上指标统一求和范围检查边界项是否为零。比如和式里同时出现 $\binom{n}{k}$ 和 $\binom{n}{n-k}$先用对称恒等式统一成一种形式。如果求和范围从 0 到 n但某一项在 k 超出实际范围时为零可以放心扩展范围。很多题目的关键就是把求和范围改写成“所有整数”然后利用范德蒙德或母函数。举个例子[ \sum_{k0}^n \binom{n}{k}\binom{n}{n-k} ]看起来是两个组合数范围是 0 到 n。其实第二个组合数在 $n-k$ 超出 0 到 n 时为零所以可以看成 $k$ 从所有整数求和直接套范德蒙德得到 $\binom{2n}{n}$。这一步不需要复杂计算但能决定后面能不能用标准恒等式。我的习惯是先用铅笔把范围改成“所有整数”再在旁边标注哪些项自动为零。这个动作很小但能避免很多范围错误。4.2 第二步吸收法降幂把 k 或 k^2 处理掉如果和式外面挂着 k优先考虑吸收恒等式[ k\binom{n}{k}n\binom{n-1}{k-1} ]比如[ \sum_{k0}^n k\binom{n}{k}n\sum_{k0}^n \binom{n-1}{k-1}n2^{n-1} ]如果外面是 $k^2$有两种处理方式。第一种是拆成 $k(k-1)k$[ k^2k(k-1)k ]然后利用[ k(k-1)\binom{n}{k}n(n-1)\binom{n-2}{k-2} ]第二种是连续用两次吸收但第二次吸收时要小心上指标从 $n-1$ 再降到 $n-2$。拆成 $k(k-1)k$ 更稳妥因为每一步都对应一个标准吸收。注意吸收法只适合处理多项式乘以组合数的情况。如果外面是 $1/(k1)$那要用积分或者其他恒等式不能硬吸。我的经验是看到 k 就试吸收看到 $k^2$ 就拆成降幂形式看到 $1/(k1)$ 就考虑 $\binom{n}{k}/(k1)\binom{n1}{k1}/(n1)$ 这类变形。4.3 第三步母函数法提取系数处理卷积和如果和式是两个组合数相乘且上下标满足某种相加关系优先考虑母函数。母函数法的核心操作是把组合数序列看成多项式系数利用乘法对应卷积。例如[ (1x)^m(1x)^n(1x)^{mn} ]左边展开[ \left(\sum_i \binom{m}{i}x^i\right)\left(\sum_j \binom{n}{j}x^j\right) ]比较 $x^r$ 的系数得到[ \sum_{ijr}\binom{m}{i}\binom{n}{j}\binom{mn}{r} ]这就是范德蒙德恒等式。母函数法的优点是不需要构造组合故事只要你会多项式乘法。遇到平方和[ \sum_k \binom{n}{k}^2 ]可以看成 $(1x)^n(1x)^n(1x)^{2n}$ 中 $x^n$ 的系数左边是 $\sum_k \binom{n}{k}\binom{n}{n-k}$再用对称恒等式变成平方和。注意母函数法处理无穷级数时要小心收敛性但组合数通常是有限项问题不大。比较系数时不要漏掉 $x$ 的指数。4.4 第四步差分与交错和处理 (-1)^k如果和式里带 $(-1)^k$优先考虑交错和、二项式反演或差分。最基本的是[ \sum_{k0}^n (-1)^k\binom{n}{k}0 ]更一般地如果你看到[ \sum_{k0}^n (-1)^k\binom{n}{k}f(k) ]可以考虑用有限差分表示。如果 $f(k)$ 是多项式这个求和通常可以用差分展开最终变成 0 或少数项。另一个常见套路是配对把 k 为奇数的项和 k 为偶数的项配对利用帕斯卡恒等式证明它们相等。注意交错和的边界项有时不能抵消比如 n0 时结果是 1不是 0。所以使用前先检查 n 的范围。我的建议是遇到 $(-1)^k$ 先别慌先看它是不是二项式定理令 $x-1$ 的结果再看能不能配对。大部分情况都能化简。4.5 求和方法速查表和式形态优先方法目标恒等式示例$\sum_k \binom{n}{k}$全和全和恒等式$2^n$$\sum_k (-1)^k\binom{n}{k}$交错和交错和恒等式$0$ (n≥1)$\sum_k k\binom{n}{k}$吸收吸收恒等式$n2^{n-1}$$\sum_k k^2\binom{n}{k}$降幂吸收吸收恒等式$n(n1)2^{n-2}$$\sum_{ir}^n \binom{i}{r}$曲棍球棒曲棍球棒恒等式$\binom{n1}{r1}$$\sum_k \binom{m}{k}\binom{n}{r-k}$范德蒙德范德蒙德恒等式$\binom{mn}{r}$$\sum_k \binom{n}{k}^2$范德蒙德/母函数平方和恒等式$\binom{2n}{n}$$\sum_k \binom{n}{k}\binom{k}{r}$乘积分解乘积分解恒等式$\binom{n}{r}2^{n-r}$$\sum_k (-1)^k\binom{n}{k}f(k)$差分/反演交错和视 f 而定这张表不是让你死记而是让你在推导时快速定位。实际题目往往需要组合使用两三种方法比如先用乘积分解再用曲棍球棒最后用全和。5. 实操案例四个典型求和从零推到闭式5.1 案例一$\sum k\binom{n}{k}n2^{n-1}$这是最经典的吸收法案例。原式[ S\sum_{k0}^n k\binom{n}{k} ]第一步用吸收恒等式[ k\binom{n}{k}n\binom{n-1}{k-1} ]代入[ Sn\sum_{k0}^n \binom{n-1}{k-1} ]当 k0 时$\binom{n-1}{-1}0$所以可以从 k1 开始[ Sn\sum_{k1}^n \binom{n-1}{k-1} ]令 $jk-1$则 j 从 0 到 n-1[ Sn\sum_{j0}^{n-1}\binom{n-1}{j}n2^{n-1} ]注意这里用到了全和恒等式。整个过程没有展开阶乘非常干净。如果外面是 $k-1$ 或者 $k1$也可以类似处理。这个案例说明吸收法的关键是“把外面的 k 收进去同时降低上指标”。5.2 案例二$\sum k^2\binom{n}{k}n(n1)2^{n-2}$这个求和比上一个复杂一点但拆降幂就很简单。先写[ k^2k(k-1)k ]所以[ S\sum_k k(k-1)\binom{n}{k}\sum_k k\binom{n}{k} ]第二项已经知道是 $n2^{n-1}$。第一项用两次吸收[ k(k-1)\binom{n}{k}n(n-1)\binom{n-2}{k-2} ]于是[ \sum_k k(k-1)\binom{n}{k}n(n-1)\sum_k \binom{n-2}{k-2}n(n-1)2^{n-2} ]合起来[ Sn(n-1)2^{n-2}n2^{n-1}n(n1)2^{n-2} ]这个结果在概率论里很有用比如二项分布的方差。注意$n0$ 或 $n1$ 时公式要单独验证。我的经验是凡是遇到 $k^2$ 乘以组合数先拆成 $k(k-1)k$不要直接连续吸收两次因为拆开之后每一步都更清晰不容易漏项。5.3 案例三$\sum \binom{n}{k}^2\binom{2n}{n}$用母函数法最快。考虑[ (1x)^n\sum_{k0}^n \binom{n}{k}x^k ]两边相乘[ (1x)^{2n}\left(\sum_k \binom{n}{k}x^k\right)\left(\sum_j \binom{n}{j}x^j\right) ]右边 $x^n$ 的系数是[ \sum_{k0}^n \binom{n}{k}\binom{n}{n-k} ]根据对称恒等式$\binom{n}{n-k}\binom{n}{k}$所以系数变成[ \sum_{k0}^n \binom{n}{k}^2 ]左边 $(1x)^{2n}$ 中 $x^n$ 的系数是 $\binom{2n}{n}$因此等式成立。这个证明非常机械适合考试写。如果要用双计数可以看成从 n 个红球和 n 个蓝球里选 n 个球按红球个数分类。两种方法都值得掌握母函数法更快双计数法更有直觉。5.4 案例四$\sum_{kr}^n \binom{n}{k}\binom{k}{r}\binom{n}{r}2^{n-r}$这个求和里两个组合数相乘而且下面的指标有关联。直接用乘积分解恒等式[ \binom{n}{k}\binom{k}{r}\binom{n}{r}\binom{n-r}{k-r} ]代入[ \sum_{kr}^n \binom{n}{k}\binom{k}{r} \binom{n}{r}\sum_{kr}^n \binom{n-r}{k-r} ]令 $jk-r$则 j 从 0 到 n-r[ \binom{n}{r}\sum_{j0}^{n-r}\binom{n-r}{j} \binom{n}{r}2^{n-r} ]这个案例把乘积分解和全和恒等式串起来了。很多初学者会尝试把 $\binom{n}{k}\binom{k}{r}$ 展开成阶乘结果越算越乱。先乘积分解再换元最后全和这是标准套路。注意乘积分解要求 $k\ge r$所以求和下限从 r 开始是自然的。5.5 用 Python 做交叉验证几行代码检查恒等式推完公式之后最好用代码验证几个小 n防止符号写错。下面这段 Python 只使用标准库适合随手检查from math import comb # 检查全和、交错和、吸收、平方和 for n in range(0, 8): assert sum(comb(n, k) for k in range(n 1)) 2 ** n if n 1: assert sum((-1) ** k * comb(n, k) for k in range(n 1)) 0 assert sum(k * comb(n, k) for k in range(n 1)) n * 2 ** (n - 1) if n 1 else 0 assert sum(comb(n, k) ** 2 for k in range(n 1)) comb(2 * n, n) # 检查曲棍球棒 for n in range(1, 8): for r in range(0, n 1): assert sum(comb(i, r) for i in range(r, n 1)) comb(n 1, r 1) # 检查范德蒙德 for m in range(0, 6): for n in range(0, 6): for r in range(0, m n 1): lhs sum(comb(m, k) * comb(n, r - k) for k in range(0, r 1)) assert lhs comb(m n, r) print(all checks passed)这种验证不能代替证明但能快速发现“负号漏了”“上下标反了”“边界项多算了”这类错误。我习惯在草稿纸上推完公式后立刻用 n3、n4 手算一遍再用代码跑一遍。两次都过基本就稳了。6. 常见问题与排查技巧实录6.1 上下指标混淆n 和 k 谁在动组合恒等式最容易错的地方就是分不清哪个指标在变。记住$\binom{n}{k}$ 中n 是总数k 是选取个数。求和变量通常是 k所以 k 在动n 相对固定。吸收恒等式 $k\binom{n}{k}n\binom{n-1}{k-1}$ 中n 和 k 同时减一但外面的因子是 n 不是 k。范德蒙德恒等式里两个上指标 m 和 n 不动k 是求和变量。曲棍球棒里i 是求和变量r 固定。我的排查方法是把每个组合数的“总数”和“选取数”用不同颜色的笔圈出来求和变量用箭头标出来。如果发现某个上指标跟着求和变量跑了就要检查是不是用错了恒等式。另一个技巧是代入具体数字比如 n3、k1看看等式两边是否相等。数值验证能立刻暴露上下标错误。6.2 求和边界从 0 还是从 r 开始求和边界是第二个高频错误点。很多恒等式写成 $\sum_{k0}^n$但实际上超出范围的组合数会变成 0所以写成从 0 开始是安全的。但有些恒等式比如曲棍球棒写成从 r 开始更直观因为 ir 时 $\binom{i}{r}0$。乘积分解恒等式要求 k≥r所以求和从 r 开始。交错和恒等式要求 n≥1因为 n0 时结果不是 0。排查方法是先写下组合数的有效范围再和求和范围比对。如果有效范围比求和范围小多出来的项自动为零可以放心。如果有效范围比求和范围大说明你漏掉了某些项。我的习惯是每次换元之后重新检查一次边界比如令 $jk-1$ 后k0 对应 j-1而 $\binom{n-1}{-1}0$所以 j 可以从 0 开始。这个检查花不了几秒钟但能避免整道题白做。6.3 负指标和广义组合数什么时候能用普通组合数只定义非负上指标但广义二项式定理允许负上指标。上指标反转恒等式[ \binom{-n}{k}(-1)^k\binom{nk-1}{k} ]在处理 $(1-x)^{-n}$ 或某些递归求和时会用到。使用负指标时要注意三点第一负号的位置是 $\binom{-n}{k}$ 还是 $\binom{n}{-k}$前者有定义后者一般不用第二符号由 $(-1)^k$ 决定和 n 无关第三右边的上指标是 $nk-1$不是 $n$。如果你不确定能不能用就先把负指标转成正指标再继续推导。我的经验是本科阶段大多数题目不会故意用负指标除非是组合数学或生成函数专题。遇到负指标时先回忆广义二项式公式[ (1x)^{-n}\sum_{k0}^\infty \binom{-n}{k}x^k ]再用上指标反转转成[ \sum_{k0}^\infty (-1)^k\binom{nk-1}{k}x^k ]这样就能和正指标的组合数打交道了。6.4 常见错误速查表错误现象可能原因修正方法结果差一个 n 因子吸收时漏了 n检查 $k\binom{n}{k}n\binom{n-1}{k-1}$符号不对$(-1)^k$ 漏写或写成 $(-1)^{k1}$重新代入 x-1 验证求和范围多一项边界项未检查单独代入 k0 或 kn 验证两个组合数下标不匹配范德蒙德上下标写反用红蓝球模型检查平方和推出错误忘记对称恒等式检查 $\binom{n}{n-k}\binom{n}{k}$曲棍球棒算错上限写成 n 而不是 n1手算 n2,r1 验证负指标符号错上指标反转记错用 $\binom{-1}{k}(-1)^k$ 验证这张表建议在刷题时对照使用。很多错误看起来是计算错误其实是恒等式记忆模糊。把错误归类之后复习效率会高很多。6.5 我踩过的坑先化简再证明不要一上来就硬算我刚开始学组合恒等式时最大的毛病是看到求和就展开阶乘。比如遇到 $\sum_k \binom{n}{k}\binom{k}{r}$直接把两个阶乘写开然后试图约分。结果式子越写越长最后自己都看不懂。后来我才明白组合恒等式的正确顺序是先看形状再选恒等式最后才计算。形状识别包括有没有 $(-1)^k$外面有没有 k两个组合数的下标有没有相加关系求和上界是不是 n右边是不是单个组合数。只要形状对上了直接套恒等式通常两三步就能出结果。硬算阶乘不仅慢而且容易出错最重要的是会掩盖组合意义。另一个坑是忽略边界。有一次我推一个恒等式n2、n3 都对n1 不对原因就是交错和在 n1 时边界项没有完全抵消。后来我养成了习惯推完公式先代入 n0、n1、n2 检查。这三个值能覆盖大部分边界情况。7. 把十一个恒等式练成肌肉记忆我的训练路径和应用地图7.1 纸笔训练每天推三个连续七天组合恒等式和骑自行车一样看会了不代表会推。我的训练方法是每天挑三个恒等式不看答案自己用双计数和母函数各推一遍。第一天推对称、帕斯卡、全和第二天推吸收、二项式定理、交错和第三天推曲棍球棒、范德蒙德、平方和第四天推乘积分解、上指标反转第五天做混合求和第六天限时训练第七天复盘错题。每个恒等式至少写两种证明比如帕斯卡用双计数和代数各写一遍范德蒙德用红蓝球模型和母函数各写一遍。这样做虽然慢但一周之后看到求和式就能条件反射地想到对应方法。注意不要只抄公式要写“为什么这一步能推下一步”。推导过程中的每一步都要有依据是双计数分类还是系数提取还是吸收降幂。写得越清楚后面越不容易忘。7.2 代码验证用 Python 小脚本做数值检查纸笔推导容易受疲劳和笔误影响代码验证是很好的补充。我的做法是每推完一个恒等式就用 Python 写一个五行左右的验证脚本枚举小范围的 n 和 k断言两边相等。比如验证范德蒙德from math import comb for m in range(0, 6): for n in range(0, 6): for r in range(0, m n 1): lhs sum(comb(m, k) * comb(n, r - k) for k in range(0, r 1)) rhs comb(m n, r) assert lhs rhs如果断言失败就打印出具体的 m、n、r再手算那一组。这种“数值试验”能快速定位符号错误和边界错误。注意代码验证不能代替证明它只能告诉你“这个公式在小范围内是对的”不能告诉你“对所有 n 都成立”。所以正确顺序是先证明再验证。先用双计数或母函数给出逻辑证明再用代码检查实现细节。两者结合效率最高。7.3 应用地图算法竞赛、概率统计、工程估算分别用哪几个在算法竞赛里最常用的是吸收恒等式、曲棍球棒、范德蒙德和全和。很多计数题最后都归结为 $\sum \binom{n}{k}2^n$ 或 $\sum_{ir}^n \binom{i}{r}\binom{n1}{r1}$。概率统计里二项式定理、全和、平方和和吸收恒等式出现频率最高比如求二项分布的期望和方差。工程估算里平方和恒等式和范德蒙德可以用来估计组合规模比如哈希冲突概率、随机抽样分布。机器学习中组合数出现在贝叶斯模型、组合特征选择、采样算法里掌握这些恒等式能帮助你化简复杂度表达式。我的建议是不要为了“用”而用而是遇到求和先判断形状如果是指数型求和想二项式定理如果外面有 k想吸收如果两个组合数相乘想范德蒙德如果斜着加想曲棍球棒。用得多了自然会形成条件反射。7.4 后续扩展从十一个走向更复杂的组合世界这十一个恒等式是基础不是终点。学完之后可以继续看二项式反演、斯特林数、卡特兰数、生成函数、容斥原理、莫比乌斯反演。二项式反演可以看成交错和的推广斯特林数可以把普通幂和组合数互相转换卡特兰数有自己的一套递推和母函数。我的经验是先把基础恒等式练到能默写、能推导、能识别形状再往扩展内容走。基础不牢后面的反演和生成函数会变成天书。反过来基础扎实之后你会发现很多复杂公式都是十一个基础动作的组合。比如斯特林数恒等式里经常出现 $\binom{n}{k}$ 和曲棍球棒卡特兰数的递推也可以用帕斯卡恒等式改写。最后分享一个我自己的小习惯每次复习组合数学先拿一张白纸把十一个恒等式默写出来不写表达式只写名称和用途。如果能默出八个以上说明状态还在如果只能默出三四个那就重新推一遍。这个方法很笨但对我很管用。 组合恒等式与求和证明：十一个恒等式、双计数与母函数实战
组合恒等式、证明方法、求和方法这三件事单看任何一个都不难难的是把它们串成一条线。很多人第一次接触组合数学看到 $\sum_{k0}^n \binom{n}{k}^2\binom{2n}{n}$ 这种式子第一反应是这也能相等第二反应是考试要考吗第三反应才是这到底怎么推。我自己的经验是组合恒等式不能孤立地背必须放回“从一堆东西里选”的场景里才知道它为什么长这样。这篇就把我常用的十一个组合恒等式整理出来同时把双计数、母函数、归纳法这几类证明方法以及吸收、卷积、差分这些求和方法拆开讲。适合准备离散数学和组合数学考试的人也适合算法竞赛里推式子、概率统计里化简期望、数据分析里估算组合规模的读者。你不需要把每个证明都背下来但要知道什么时候该用哪一个。1. 十一个组合恒等式的全景地图先知道每个式子管什么1.1 组合数记号先统一别在上指标和下指标上翻车组合数记作 $\binom{n}{k}$读作“n 选 k”意思是“从 n 个不同元素里选 k 个有多少种选法”。它最常见的计算方式是阶乘形式[ \binom{n}{k}\frac{n!}{k!(n-k)!} ]其中默认 $n$ 是非负整数$k$ 是整数。如果 $k0$ 或 $kn$通常约定 $\binom{n}{k}0$。这一点非常关键因为很多求和式看起来范围很大实际上超出范围的项自动变成 0所以你可以放心地把求和范围写成 $k0$ 到 $n$甚至写成所有整数求和。后面讲上指标反转时会看到负的 $n$ 也可以定义组合数但那要额外引入广义组合数不是普通“从负个东西里选”的直观场景。初学阶段先把 $n\ge 0$、$0\le k\le n$ 这一套记稳能避免绝大部分低级错误。我这里说的“低级错误”十有八九是把 $\binom{n}{k}$ 写成 $\binom{k}{n}$或者把 $n$ 和 $k$ 谁该减一搞反。记法上建议每次写公式前先默念“上面是总数下面是取几个”这个习惯能救回很多分数。1.2 十一个恒等式总表名称、表达式、用途和记忆钩子下面这十一个式子是我在推求和时出现频率最高的。它们不是孤立的很多可以互相推导。比如二项式定理能推出全和与交错和吸收恒等式来自二项式定理求导范德蒙德恒等式可以看成两堆元素的卷积曲棍球棒恒等式是帕斯卡恒等式斜着加出来的。编号名称表达式典型用途记忆钩子1对称恒等式$\binom{n}{k}\binom{n}{n-k}$简化大下标选走 k 个等于留下 n-k 个2帕斯卡恒等式$\binom{n}{k}\binom{n-1}{k}\binom{n-1}{k-1}$递推、杨辉三角含某个特殊元素分两类3吸收恒等式$k\binom{n}{k}n\binom{n-1}{k-1}$去掉外面的 k把 k 吸进组合数4二项式定理$\sum_{k0}^n \binom{n}{k}x^k(1x)^n$母函数、系数提取所有组合求和的母体5全和恒等式$\sum_{k0}^n \binom{n}{k}2^n$子集总数每个元素选或不选6交错和恒等式$\sum_{k0}^n (-1)^k\binom{n}{k}0$奇偶抵消、容斥奇数子集和偶数子集一样多7曲棍球棒恒等式$\sum_{ir}^n \binom{i}{r}\binom{n1}{r1}$斜求和斜着加等于下一项8范德蒙德恒等式$\sum_{k0}^r \binom{m}{k}\binom{n}{r-k}\binom{mn}{r}$合并两堆组合数两堆一共选 r 个9平方和恒等式$\sum_{k0}^n \binom{n}{k}^2\binom{2n}{n}$对称卷积两堆各选相同个数10乘积分解恒等式$\binom{n}{k}\binom{k}{r}\binom{n}{r}\binom{n-r}{k-r}$重排乘积、交换求和先选小组再扩成大组11上指标反转$\binom{-n}{k}(-1)^k\binom{nk-1}{k}$负指标、广义二项式负号靠 k 的奇偶决定这张表建议自己手抄一遍不是抄表达式而是抄“用途”和“记忆钩子”。表达式可以查但用途必须变成条件反射。比如看到外面挂着 $k$立刻想到吸收看到两个组合数相乘且下标相加为常数立刻想到范德蒙德看到 $\sum_{ir}^n \binom{i}{r}$立刻想到曲棍球棒。很多时候推不出来不是因为你不会算而是因为没认出式子的形状。1.3 选择标准十一个式子覆盖了哪些求和形态为什么选这十一个而不是六个或者二十个因为我选的标准是“能否覆盖常见求和动作”。第一类是对称和边界处理包括对称恒等式、全和、交错和它们负责把复杂范围变简单。第二类是递推和吸收包括帕斯卡、吸收、曲棍球棒它们负责降指标、消掉外面的 $k$、处理斜向求和。第三类是卷积和乘积重排包括范德蒙德、平方和、乘积分解它们负责把两个组合数相乘的求和合并成一个组合数。第四类是母函数和负指标包括二项式定理和上指标反转它们负责把求和变成系数提取或者把负上指标转成正指标。你把这四类练熟绝大多数本科组合数学题和算法竞赛里的组合求和都能找到切入点。剩下的一些恒等式比如三项式系数、莫比乌斯反演、斯特林数恒等式本质上是这些基础动作的延伸。先把十一个基础动作打牢再扩展会轻松很多。2. 证明方法不玄学双计数、母函数、归纳法到底怎么选2.1 双计数法把等式两边讲成同一个选择故事双计数法是组合证明里最漂亮的方法也是最适合建立直觉的方法。它的核心只有一句话等式两边都在数同一个集合所以相等。以帕斯卡恒等式为例左边 $\binom{n}{k}$ 是从 n 个元素里选 k 个。右边分成两类不选某个特定元素 $a$就要从剩下 $n-1$ 个里选 k 个方案数是 $\binom{n-1}{k}$选 $a$就要从剩下 $n-1$ 个里再选 $k-1$ 个方案数是 $\binom{n-1}{k-1}$。两类不重不漏所以相加相等。范德蒙德恒等式也可以用双计数有 m 个红球和 n 个蓝球一共选 r 个球的方法是 $\binom{mn}{r}$而按红球个数 k 分类就是 $\sum_k \binom{m}{k}\binom{n}{r-k}$。平方和恒等式 $\sum_k \binom{n}{k}^2\binom{2n}{n}$ 可以看成有两组各 n 个元素从第一组选 k 个、第二组选 k 个再让 k 跑遍所有可能等价于从 2n 个元素里选 n 个。双计数法的难点不在于计算而在于你能不能构造出正确的“故事”。我的经验是先看等式两边谁更像“总数”然后把另一边按某个变量分类。分类标准通常就是求和指标比如红球个数、是否包含特殊元素、第一组选了几个。只要分类不重不漏证明就成立。2.2 母函数与代数变形把求和塞进 $(1x)^n$母函数法适合处理带 $x^k$ 或 $x^{n-k}$ 的求和。二项式定理是核心[ (1x)^n\sum_{k0}^n \binom{n}{k}x^k ]这个式子厉害的地方在于它把整个组合数序列打包成一个多项式。你想证明某个求和可以把两边乘以 $x^r$ 再取系数或者令 $x1$、$x-1$ 得到特殊值。全和恒等式令 $x1$ 就得到 $\sum_k \binom{n}{k}2^n$交错和恒等式令 $x-1$ 就得到 $\sum_k (-1)^k\binom{n}{k}0$。吸收恒等式也可以从二项式定理求导得到两边对 $x$ 求导得到 $n(1x)^{n-1}\sum_k k\binom{n}{k}x^{k-1}$再比较系数。母函数法的优点是机械、可复制不需要每次构造组合故事缺点是容易算错系数尤其是求导、乘法和变量替换的时候。我的建议是如果你对组合场景敏感优先用双计数如果你对代数操作更稳或者求和里带变量 $x$优先用母函数。两种方法最好都掌握因为考试和实际推导中经常需要交叉验证。2.3 归纳法与递推适合带 n 的斜求和归纳法适合证明关于 n 的恒等式尤其是曲棍球棒这种带求和上界的式子。以[ \sum_{ir}^n \binom{i}{r}\binom{n1}{r1} ]为例固定 r对 n 做归纳。基础情形 $nr$ 时左边是 $\binom{r}{r}1$右边是 $\binom{r1}{r1}1$成立。假设对 n 成立当 n 变成 n1 时左边增加的是 $\binom{n1}{r}$右边从 $\binom{n1}{r1}$ 变成 $\binom{n2}{r1}$。根据帕斯卡恒等式[ \binom{n2}{r1}\binom{n1}{r1}\binom{n1}{r} ]所以增量正好对上。归纳法写起来规范但关键是找到“增量”和“递推式”的对应关系。很多初学者归纳法失败是因为直接从左边硬推右边而不是先看从 n 到 n1 新增了哪一项。记住一个套路凡是有求和上界且右边是个单独组合数通常都可以考虑归纳。归纳法的缺点是不太能解释“为什么”它证明了正确性但没有告诉你这个式子是怎么被发现的。所以做完归纳之后最好再用双计数或曲棍球棒的图像解释一遍印象会深很多。2.4 证明方法选择表看到什么特征用什么方法等式特征首选证明备选容易踩的坑一边是单个组合数另一边是两个组合数相加双计数、帕斯卡归纳分类过细导致重复带 $x^k$ 或要求特殊值母函数、二项式定理代数变形系数提取时忘记常数项求和上界是 n右边是 n1 的组合数归纳法双计数增量项写错两个组合数相乘下标相加为常数范德蒙德卷积母函数上下指标搞反外面挂着 $k$ 或 $k^2$吸收恒等式求导忘记 $n$ 的因子带 $(-1)^k$交错和、容斥令 $x-1$边界项没有抵消干净上指标为负上指标反转广义二项式负号指数漏写这张表建议贴在书桌前。实际推导时先判断式子形状再选方法比一上来就硬算高效得多。我的体会是组合恒等式证明最怕“无脑展开阶乘”因为阶乘一展开式子会爆炸而且很难看出对称性。先形状、后方法、再计算这个顺序很重要。3. 十一个恒等式逐个拆解证明思路、适用场景和记忆锚点3.1 对称恒等式为什么选 k 个等于留下 n-k 个对称恒等式是[ \binom{n}{k}\binom{n}{n-k} ]它的直观解释是从 n 个元素里选 k 个带走的方案数等于从 n 个元素里留下 n-k 个不带的方案数。选和留是一一对应的你每选出一个 k 元子集就确定了一个 n-k 元的补集。这个式子看起来简单但用途很广。比如 $\binom{100}{98}$ 可以直接写成 $\binom{100}{2}$计算量瞬间下降。再比如在求和时如果出现 $\binom{n}{k}$ 和 $\binom{n}{n-k}$可以利用对称性把两项合并或者配对。注意对称恒等式只对普通的非负整数 n 和整数 k 成立如果引入负上指标形式会变成上指标反转那个样子。记忆锚点选走的就是留下的补集所以“选 k 个”和“选 n-k 个”等价。3.2 帕斯卡恒等式杨辉三角的加法规则帕斯卡恒等式是[ \binom{n}{k}\binom{n-1}{k}\binom{n-1}{k-1} ]杨辉三角里每个数等于上方两个数之和就是它在驱动。双计数证明很干净固定一个元素 a从 n 个里选 k 个。如果不选 a就从剩下 n-1 个里选 k 个如果选 a就从剩下 n-1 个里选 k-1 个。两类合起来就是全部。这个式子是递推计算组合数的基础也是很多恒等式的源头。曲棍球棒恒等式就是沿着杨辉三角的斜线累加。用帕斯卡恒等式时要注意边界当 $k0$ 时$\binom{n-1}{-1}$ 约定为 0当 $kn$ 时$\binom{n-1}{n}$ 约定为 0。很多人写递推代码时忘记处理这两个边界导致数组越界。记忆锚点分“含特殊元素”和“不含特殊元素”两类。3.3 吸收恒等式把外面的 k 收进组合数吸收恒等式是[ k\binom{n}{k}n\binom{n-1}{k-1} ]它解决的是求和里最烦人的“外面挂着一个 k”。证明可以用双计数从 n 个人里选 k 个人组成小队再从 k 个人里选一个队长方案数是 $k\binom{n}{k}$也可以先选队长n 种再从剩下 n-1 个人里选 k-1 个队员方案数是 $n\binom{n-1}{k-1}$。两种数法结果一样。这个式子可以把 $k$ 从组合数外面“吸”进去同时把 n 降成 n-1k 降成 k-1。比如求 $\sum_k k\binom{n}{k}$直接用吸收恒等式变成 $n\sum_k \binom{n-1}{k-1}n2^{n-1}$。如果外面是 $k^2$可以连续用两次吸收或者把 $k^2$ 写成 $k(k-1)k$再分别吸收。注意吸收时不要漏掉 n 这个因子也不要忘记下标同时减一。记忆锚点选队长模型先选人再选队长或者先选队长再选人。3.4 二项式定理所有组合求和的母体二项式定理是[ (1x)^n\sum_{k0}^n \binom{n}{k}x^k ]它不仅是代数公式更是组合求和的母函数。你可以把它看成“每个元素要么贡献 1要么贡献 x”的生成过程展开时每个括号选 1 还是选 x选 x 的元素个数为 k对应项就是 $\binom{n}{k}x^k$。令 $x1$ 得到全和令 $x-1$ 得到交错和求导可以得到带 k 的求和乘以 $x$ 再求导可以得到带 $k^2$ 的求和。二项式定理的推广是广义二项式定理[ (1x)^\alpha\sum_{k0}^\infty \binom{\alpha}{k}x^k ]其中 $\alpha$ 可以是负数或实数这也是上指标反转的来源之一。使用二项式定理时最常见的问题是把 $(1x)^n$ 和 $(x1)^n$ 混了其实它们相等但系数提取时要注意哪个变量对应哪个指数。记忆锚点所有子集按大小打包系数就是组合数。3.5 全和恒等式所有子集数就是 2 的 n 次方全和恒等式是[ \sum_{k0}^n \binom{n}{k}2^n ]它的组合意义最直接n 个元素组成的集合所有子集的总数是 $2^n$因为每个元素都有“选”和“不选”两种状态。按子集大小 k 分类大小为 k 的子集有 $\binom{n}{k}$ 个所以求和就是子集总数。这个式子是很多概率计算的基础。比如抛 n 次硬币所有可能结果数是 $2^n$恰好出现 k 次正面的结果数是 $\binom{n}{k}$把它们加起来还是 $2^n$。注意当 n 为 0 时左边是 $\binom{0}{0}1$右边是 $2^01$也成立。使用全和恒等式时要确保求和范围覆盖所有可能的 k如果只求一部分比如 $\sum_{k0}^m \binom{n}{k}$那就没有简单的单项闭式不能直接写成 $2^n$ 的一部分。记忆锚点每个元素选或不选总共 $2^n$ 种。3.6 交错和恒等式奇偶子集一样多交错和恒等式是[ \sum_{k0}^n (-1)^k\binom{n}{k}0 \quad (n\ge 1) ]它的含义是当 n 至少为 1 时偶数大小子集的数量等于奇数大小子集的数量。证明可以用二项式定理令 $x-1$也可以构造配对固定一个元素 a把子集分成含 a 和不含 a 的两类含 a 的子集与不含 a 的子集奇偶性相反可以一一配对。当 n0 时左边只有 $\binom{0}{0}1$右边不是 0所以通常要求 n≥1。这个恒等式在容斥原理、二项式反演、差分算子中非常重要。遇到带 $(-1)^k$ 的求和第一反应就是看能不能用交错和或配对消去。注意符号不要漏尤其是 $(-1)^k$ 和 $(-1)^{k1}$ 的转换。记忆锚点奇偶子集成对抵消除了空集那种特殊情况。3.7 曲棍球棒恒等式斜着加为什么等于下一项曲棍球棒恒等式是[ \sum_{ir}^n \binom{i}{r}\binom{n1}{r1} ]在杨辉三角里从某一项开始沿着左下到右上的斜线累加结果等于斜线末端下一行的数形状像曲棍球棒。证明可以用帕斯卡恒等式反复展开[ \binom{n1}{r1}\binom{n}{r1}\binom{n}{r} ]而 $\binom{n}{r1}$ 又可以继续拆最后得到从 $\binom{r}{r}$ 到 $\binom{n}{r}$ 的和。也可以双计数从 n1 个元素里选 r1 个按最大元素的位置分类。这个恒等式在求 $\sum_{ir}^n \binom{i}{r}$ 这种斜求和时非常有用。注意求和下限必须是 r因为当 ir 时 $\binom{i}{r}0$写成 i0 也可以但下限写 r 更直观。记忆锚点斜线累加等于下一行右斜一项。3.8 范德蒙德恒等式两堆东西分成 r 个的卷积范德蒙德恒等式是[ \sum_{k0}^r \binom{m}{k}\binom{n}{r-k}\binom{mn}{r} ]它描述的是两堆元素的合并选择有 m 个红球和 n 个蓝球一共选 r 个球按选了多少个红球分类就是左边直接看成从 mn 个球里选 r 个就是右边。这个式子是组合卷积的核心平方和恒等式就是 mnr 的特殊情形。范德蒙德恒等式还可以推广到多项式系数但基础版本足够处理大多数求和。使用时要注意上下标第一个组合数从 m 里选 k第二个从 n 里选 r-kk 的范围是 0 到 r但如果 km 或 r-kn对应项自动为 0。很多人会把两个组合数的上指标写反或者把 r-k 写成 k-r。记忆锚点红蓝两堆按红球个数分类。3.9 平方和恒等式两堆各选相同个数平方和恒等式是[ \sum_{k0}^n \binom{n}{k}^2\binom{2n}{n} ]它看起来像是范德蒙德恒等式在 $mnr$ 时的特例[ \sum_{k0}^n \binom{n}{k}\binom{n}{n-k}\binom{2n}{n} ]再利用对称恒等式 $\binom{n}{n-k}\binom{n}{k}$就得到平方和。组合意义也很清楚有两组各 n 个元素先从第一组选 k 个再从第二组选 k 个总共选 n 个也可以直接从 2n 个元素里选 n 个。这个恒等式在概率论中经常出现比如超几何分布、随机游走、中心二项式系数估计。注意平方和恒等式没有简单的“部分和”版本如果你把求和上限改成 mn一般不能写成单个组合数。记忆锚点两组各选 k 个合起来是 2n 里选 n 个。3.10 乘积分解恒等式先选小组再扩成大组乘积分解恒等式是[ \binom{n}{k}\binom{k}{r}\binom{n}{r}\binom{n-r}{k-r} ]它的组合意义是从 n 个人里先选 k 个人再从这 k 个人里选 r 个人当核心成员等价于先从 n 个人里直接选 r 个人当核心成员再从剩下的 n-r 个人里选 k-r 个人加入外围。两边数的都是“n 个人里有一个 r 人核心组和一个 k 人小组核心组包含于小组”的方案数。这个恒等式在交换求和次序时特别好用因为它可以把依赖 k 的组合数拆成两个独立部分或者把内层求和变成曲棍球棒。使用时注意下标$k-r$ 必须非负所以 k≥r。如果求和里出现 $\binom{n}{k}\binom{k}{r}$不要急着展开阶乘先用这个恒等式重排往往能直接看出曲棍球棒或范德蒙德。记忆锚点先选核心再选外围。3.11 上指标反转负上指标怎么变正上指标反转恒等式是[ \binom{-n}{k}(-1)^k\binom{nk-1}{k} ]它处理的是负上指标的组合数。普通组合数要求上指标非负但在广义二项式定理和某些求和里会出现负数。这个式子把负上指标转成正的代价是前面多一个 $(-1)^k$。例如[ \binom{-1}{k}(-1)^k ]因为 $\binom{1k-1}{k}\binom{k}{k}1$。这个恒等式在生成函数中很常见比如 $(1-x)^{-n}$ 的展开。使用时要注意负号只由 k 的奇偶决定与 n 无关右边的组合数是 $\binom{nk-1}{k}$不是 $\binom{n}{k}$。很多初学者会把上指标反转和对称恒等式混用导致符号错误。记忆锚点负上指标转正符号看 k 的奇偶。4. 组合求和方法遇到和式先做这四步4.1 第一步统一上下指标和求和范围拿到一个组合求和不要立刻算。先做三件事统一组合数的上指标统一求和范围检查边界项是否为零。比如和式里同时出现 $\binom{n}{k}$ 和 $\binom{n}{n-k}$先用对称恒等式统一成一种形式。如果求和范围从 0 到 n但某一项在 k 超出实际范围时为零可以放心扩展范围。很多题目的关键就是把求和范围改写成“所有整数”然后利用范德蒙德或母函数。举个例子[ \sum_{k0}^n \binom{n}{k}\binom{n}{n-k} ]看起来是两个组合数范围是 0 到 n。其实第二个组合数在 $n-k$ 超出 0 到 n 时为零所以可以看成 $k$ 从所有整数求和直接套范德蒙德得到 $\binom{2n}{n}$。这一步不需要复杂计算但能决定后面能不能用标准恒等式。我的习惯是先用铅笔把范围改成“所有整数”再在旁边标注哪些项自动为零。这个动作很小但能避免很多范围错误。4.2 第二步吸收法降幂把 k 或 k^2 处理掉如果和式外面挂着 k优先考虑吸收恒等式[ k\binom{n}{k}n\binom{n-1}{k-1} ]比如[ \sum_{k0}^n k\binom{n}{k}n\sum_{k0}^n \binom{n-1}{k-1}n2^{n-1} ]如果外面是 $k^2$有两种处理方式。第一种是拆成 $k(k-1)k$[ k^2k(k-1)k ]然后利用[ k(k-1)\binom{n}{k}n(n-1)\binom{n-2}{k-2} ]第二种是连续用两次吸收但第二次吸收时要小心上指标从 $n-1$ 再降到 $n-2$。拆成 $k(k-1)k$ 更稳妥因为每一步都对应一个标准吸收。注意吸收法只适合处理多项式乘以组合数的情况。如果外面是 $1/(k1)$那要用积分或者其他恒等式不能硬吸。我的经验是看到 k 就试吸收看到 $k^2$ 就拆成降幂形式看到 $1/(k1)$ 就考虑 $\binom{n}{k}/(k1)\binom{n1}{k1}/(n1)$ 这类变形。4.3 第三步母函数法提取系数处理卷积和如果和式是两个组合数相乘且上下标满足某种相加关系优先考虑母函数。母函数法的核心操作是把组合数序列看成多项式系数利用乘法对应卷积。例如[ (1x)^m(1x)^n(1x)^{mn} ]左边展开[ \left(\sum_i \binom{m}{i}x^i\right)\left(\sum_j \binom{n}{j}x^j\right) ]比较 $x^r$ 的系数得到[ \sum_{ijr}\binom{m}{i}\binom{n}{j}\binom{mn}{r} ]这就是范德蒙德恒等式。母函数法的优点是不需要构造组合故事只要你会多项式乘法。遇到平方和[ \sum_k \binom{n}{k}^2 ]可以看成 $(1x)^n(1x)^n(1x)^{2n}$ 中 $x^n$ 的系数左边是 $\sum_k \binom{n}{k}\binom{n}{n-k}$再用对称恒等式变成平方和。注意母函数法处理无穷级数时要小心收敛性但组合数通常是有限项问题不大。比较系数时不要漏掉 $x$ 的指数。4.4 第四步差分与交错和处理 (-1)^k如果和式里带 $(-1)^k$优先考虑交错和、二项式反演或差分。最基本的是[ \sum_{k0}^n (-1)^k\binom{n}{k}0 ]更一般地如果你看到[ \sum_{k0}^n (-1)^k\binom{n}{k}f(k) ]可以考虑用有限差分表示。如果 $f(k)$ 是多项式这个求和通常可以用差分展开最终变成 0 或少数项。另一个常见套路是配对把 k 为奇数的项和 k 为偶数的项配对利用帕斯卡恒等式证明它们相等。注意交错和的边界项有时不能抵消比如 n0 时结果是 1不是 0。所以使用前先检查 n 的范围。我的建议是遇到 $(-1)^k$ 先别慌先看它是不是二项式定理令 $x-1$ 的结果再看能不能配对。大部分情况都能化简。4.5 求和方法速查表和式形态优先方法目标恒等式示例$\sum_k \binom{n}{k}$全和全和恒等式$2^n$$\sum_k (-1)^k\binom{n}{k}$交错和交错和恒等式$0$ (n≥1)$\sum_k k\binom{n}{k}$吸收吸收恒等式$n2^{n-1}$$\sum_k k^2\binom{n}{k}$降幂吸收吸收恒等式$n(n1)2^{n-2}$$\sum_{ir}^n \binom{i}{r}$曲棍球棒曲棍球棒恒等式$\binom{n1}{r1}$$\sum_k \binom{m}{k}\binom{n}{r-k}$范德蒙德范德蒙德恒等式$\binom{mn}{r}$$\sum_k \binom{n}{k}^2$范德蒙德/母函数平方和恒等式$\binom{2n}{n}$$\sum_k \binom{n}{k}\binom{k}{r}$乘积分解乘积分解恒等式$\binom{n}{r}2^{n-r}$$\sum_k (-1)^k\binom{n}{k}f(k)$差分/反演交错和视 f 而定这张表不是让你死记而是让你在推导时快速定位。实际题目往往需要组合使用两三种方法比如先用乘积分解再用曲棍球棒最后用全和。5. 实操案例四个典型求和从零推到闭式5.1 案例一$\sum k\binom{n}{k}n2^{n-1}$这是最经典的吸收法案例。原式[ S\sum_{k0}^n k\binom{n}{k} ]第一步用吸收恒等式[ k\binom{n}{k}n\binom{n-1}{k-1} ]代入[ Sn\sum_{k0}^n \binom{n-1}{k-1} ]当 k0 时$\binom{n-1}{-1}0$所以可以从 k1 开始[ Sn\sum_{k1}^n \binom{n-1}{k-1} ]令 $jk-1$则 j 从 0 到 n-1[ Sn\sum_{j0}^{n-1}\binom{n-1}{j}n2^{n-1} ]注意这里用到了全和恒等式。整个过程没有展开阶乘非常干净。如果外面是 $k-1$ 或者 $k1$也可以类似处理。这个案例说明吸收法的关键是“把外面的 k 收进去同时降低上指标”。5.2 案例二$\sum k^2\binom{n}{k}n(n1)2^{n-2}$这个求和比上一个复杂一点但拆降幂就很简单。先写[ k^2k(k-1)k ]所以[ S\sum_k k(k-1)\binom{n}{k}\sum_k k\binom{n}{k} ]第二项已经知道是 $n2^{n-1}$。第一项用两次吸收[ k(k-1)\binom{n}{k}n(n-1)\binom{n-2}{k-2} ]于是[ \sum_k k(k-1)\binom{n}{k}n(n-1)\sum_k \binom{n-2}{k-2}n(n-1)2^{n-2} ]合起来[ Sn(n-1)2^{n-2}n2^{n-1}n(n1)2^{n-2} ]这个结果在概率论里很有用比如二项分布的方差。注意$n0$ 或 $n1$ 时公式要单独验证。我的经验是凡是遇到 $k^2$ 乘以组合数先拆成 $k(k-1)k$不要直接连续吸收两次因为拆开之后每一步都更清晰不容易漏项。5.3 案例三$\sum \binom{n}{k}^2\binom{2n}{n}$用母函数法最快。考虑[ (1x)^n\sum_{k0}^n \binom{n}{k}x^k ]两边相乘[ (1x)^{2n}\left(\sum_k \binom{n}{k}x^k\right)\left(\sum_j \binom{n}{j}x^j\right) ]右边 $x^n$ 的系数是[ \sum_{k0}^n \binom{n}{k}\binom{n}{n-k} ]根据对称恒等式$\binom{n}{n-k}\binom{n}{k}$所以系数变成[ \sum_{k0}^n \binom{n}{k}^2 ]左边 $(1x)^{2n}$ 中 $x^n$ 的系数是 $\binom{2n}{n}$因此等式成立。这个证明非常机械适合考试写。如果要用双计数可以看成从 n 个红球和 n 个蓝球里选 n 个球按红球个数分类。两种方法都值得掌握母函数法更快双计数法更有直觉。5.4 案例四$\sum_{kr}^n \binom{n}{k}\binom{k}{r}\binom{n}{r}2^{n-r}$这个求和里两个组合数相乘而且下面的指标有关联。直接用乘积分解恒等式[ \binom{n}{k}\binom{k}{r}\binom{n}{r}\binom{n-r}{k-r} ]代入[ \sum_{kr}^n \binom{n}{k}\binom{k}{r} \binom{n}{r}\sum_{kr}^n \binom{n-r}{k-r} ]令 $jk-r$则 j 从 0 到 n-r[ \binom{n}{r}\sum_{j0}^{n-r}\binom{n-r}{j} \binom{n}{r}2^{n-r} ]这个案例把乘积分解和全和恒等式串起来了。很多初学者会尝试把 $\binom{n}{k}\binom{k}{r}$ 展开成阶乘结果越算越乱。先乘积分解再换元最后全和这是标准套路。注意乘积分解要求 $k\ge r$所以求和下限从 r 开始是自然的。5.5 用 Python 做交叉验证几行代码检查恒等式推完公式之后最好用代码验证几个小 n防止符号写错。下面这段 Python 只使用标准库适合随手检查from math import comb # 检查全和、交错和、吸收、平方和 for n in range(0, 8): assert sum(comb(n, k) for k in range(n 1)) 2 ** n if n 1: assert sum((-1) ** k * comb(n, k) for k in range(n 1)) 0 assert sum(k * comb(n, k) for k in range(n 1)) n * 2 ** (n - 1) if n 1 else 0 assert sum(comb(n, k) ** 2 for k in range(n 1)) comb(2 * n, n) # 检查曲棍球棒 for n in range(1, 8): for r in range(0, n 1): assert sum(comb(i, r) for i in range(r, n 1)) comb(n 1, r 1) # 检查范德蒙德 for m in range(0, 6): for n in range(0, 6): for r in range(0, m n 1): lhs sum(comb(m, k) * comb(n, r - k) for k in range(0, r 1)) assert lhs comb(m n, r) print(all checks passed)这种验证不能代替证明但能快速发现“负号漏了”“上下标反了”“边界项多算了”这类错误。我习惯在草稿纸上推完公式后立刻用 n3、n4 手算一遍再用代码跑一遍。两次都过基本就稳了。6. 常见问题与排查技巧实录6.1 上下指标混淆n 和 k 谁在动组合恒等式最容易错的地方就是分不清哪个指标在变。记住$\binom{n}{k}$ 中n 是总数k 是选取个数。求和变量通常是 k所以 k 在动n 相对固定。吸收恒等式 $k\binom{n}{k}n\binom{n-1}{k-1}$ 中n 和 k 同时减一但外面的因子是 n 不是 k。范德蒙德恒等式里两个上指标 m 和 n 不动k 是求和变量。曲棍球棒里i 是求和变量r 固定。我的排查方法是把每个组合数的“总数”和“选取数”用不同颜色的笔圈出来求和变量用箭头标出来。如果发现某个上指标跟着求和变量跑了就要检查是不是用错了恒等式。另一个技巧是代入具体数字比如 n3、k1看看等式两边是否相等。数值验证能立刻暴露上下标错误。6.2 求和边界从 0 还是从 r 开始求和边界是第二个高频错误点。很多恒等式写成 $\sum_{k0}^n$但实际上超出范围的组合数会变成 0所以写成从 0 开始是安全的。但有些恒等式比如曲棍球棒写成从 r 开始更直观因为 ir 时 $\binom{i}{r}0$。乘积分解恒等式要求 k≥r所以求和从 r 开始。交错和恒等式要求 n≥1因为 n0 时结果不是 0。排查方法是先写下组合数的有效范围再和求和范围比对。如果有效范围比求和范围小多出来的项自动为零可以放心。如果有效范围比求和范围大说明你漏掉了某些项。我的习惯是每次换元之后重新检查一次边界比如令 $jk-1$ 后k0 对应 j-1而 $\binom{n-1}{-1}0$所以 j 可以从 0 开始。这个检查花不了几秒钟但能避免整道题白做。6.3 负指标和广义组合数什么时候能用普通组合数只定义非负上指标但广义二项式定理允许负上指标。上指标反转恒等式[ \binom{-n}{k}(-1)^k\binom{nk-1}{k} ]在处理 $(1-x)^{-n}$ 或某些递归求和时会用到。使用负指标时要注意三点第一负号的位置是 $\binom{-n}{k}$ 还是 $\binom{n}{-k}$前者有定义后者一般不用第二符号由 $(-1)^k$ 决定和 n 无关第三右边的上指标是 $nk-1$不是 $n$。如果你不确定能不能用就先把负指标转成正指标再继续推导。我的经验是本科阶段大多数题目不会故意用负指标除非是组合数学或生成函数专题。遇到负指标时先回忆广义二项式公式[ (1x)^{-n}\sum_{k0}^\infty \binom{-n}{k}x^k ]再用上指标反转转成[ \sum_{k0}^\infty (-1)^k\binom{nk-1}{k}x^k ]这样就能和正指标的组合数打交道了。6.4 常见错误速查表错误现象可能原因修正方法结果差一个 n 因子吸收时漏了 n检查 $k\binom{n}{k}n\binom{n-1}{k-1}$符号不对$(-1)^k$ 漏写或写成 $(-1)^{k1}$重新代入 x-1 验证求和范围多一项边界项未检查单独代入 k0 或 kn 验证两个组合数下标不匹配范德蒙德上下标写反用红蓝球模型检查平方和推出错误忘记对称恒等式检查 $\binom{n}{n-k}\binom{n}{k}$曲棍球棒算错上限写成 n 而不是 n1手算 n2,r1 验证负指标符号错上指标反转记错用 $\binom{-1}{k}(-1)^k$ 验证这张表建议在刷题时对照使用。很多错误看起来是计算错误其实是恒等式记忆模糊。把错误归类之后复习效率会高很多。6.5 我踩过的坑先化简再证明不要一上来就硬算我刚开始学组合恒等式时最大的毛病是看到求和就展开阶乘。比如遇到 $\sum_k \binom{n}{k}\binom{k}{r}$直接把两个阶乘写开然后试图约分。结果式子越写越长最后自己都看不懂。后来我才明白组合恒等式的正确顺序是先看形状再选恒等式最后才计算。形状识别包括有没有 $(-1)^k$外面有没有 k两个组合数的下标有没有相加关系求和上界是不是 n右边是不是单个组合数。只要形状对上了直接套恒等式通常两三步就能出结果。硬算阶乘不仅慢而且容易出错最重要的是会掩盖组合意义。另一个坑是忽略边界。有一次我推一个恒等式n2、n3 都对n1 不对原因就是交错和在 n1 时边界项没有完全抵消。后来我养成了习惯推完公式先代入 n0、n1、n2 检查。这三个值能覆盖大部分边界情况。7. 把十一个恒等式练成肌肉记忆我的训练路径和应用地图7.1 纸笔训练每天推三个连续七天组合恒等式和骑自行车一样看会了不代表会推。我的训练方法是每天挑三个恒等式不看答案自己用双计数和母函数各推一遍。第一天推对称、帕斯卡、全和第二天推吸收、二项式定理、交错和第三天推曲棍球棒、范德蒙德、平方和第四天推乘积分解、上指标反转第五天做混合求和第六天限时训练第七天复盘错题。每个恒等式至少写两种证明比如帕斯卡用双计数和代数各写一遍范德蒙德用红蓝球模型和母函数各写一遍。这样做虽然慢但一周之后看到求和式就能条件反射地想到对应方法。注意不要只抄公式要写“为什么这一步能推下一步”。推导过程中的每一步都要有依据是双计数分类还是系数提取还是吸收降幂。写得越清楚后面越不容易忘。7.2 代码验证用 Python 小脚本做数值检查纸笔推导容易受疲劳和笔误影响代码验证是很好的补充。我的做法是每推完一个恒等式就用 Python 写一个五行左右的验证脚本枚举小范围的 n 和 k断言两边相等。比如验证范德蒙德from math import comb for m in range(0, 6): for n in range(0, 6): for r in range(0, m n 1): lhs sum(comb(m, k) * comb(n, r - k) for k in range(0, r 1)) rhs comb(m n, r) assert lhs rhs如果断言失败就打印出具体的 m、n、r再手算那一组。这种“数值试验”能快速定位符号错误和边界错误。注意代码验证不能代替证明它只能告诉你“这个公式在小范围内是对的”不能告诉你“对所有 n 都成立”。所以正确顺序是先证明再验证。先用双计数或母函数给出逻辑证明再用代码检查实现细节。两者结合效率最高。7.3 应用地图算法竞赛、概率统计、工程估算分别用哪几个在算法竞赛里最常用的是吸收恒等式、曲棍球棒、范德蒙德和全和。很多计数题最后都归结为 $\sum \binom{n}{k}2^n$ 或 $\sum_{ir}^n \binom{i}{r}\binom{n1}{r1}$。概率统计里二项式定理、全和、平方和和吸收恒等式出现频率最高比如求二项分布的期望和方差。工程估算里平方和恒等式和范德蒙德可以用来估计组合规模比如哈希冲突概率、随机抽样分布。机器学习中组合数出现在贝叶斯模型、组合特征选择、采样算法里掌握这些恒等式能帮助你化简复杂度表达式。我的建议是不要为了“用”而用而是遇到求和先判断形状如果是指数型求和想二项式定理如果外面有 k想吸收如果两个组合数相乘想范德蒙德如果斜着加想曲棍球棒。用得多了自然会形成条件反射。7.4 后续扩展从十一个走向更复杂的组合世界这十一个恒等式是基础不是终点。学完之后可以继续看二项式反演、斯特林数、卡特兰数、生成函数、容斥原理、莫比乌斯反演。二项式反演可以看成交错和的推广斯特林数可以把普通幂和组合数互相转换卡特兰数有自己的一套递推和母函数。我的经验是先把基础恒等式练到能默写、能推导、能识别形状再往扩展内容走。基础不牢后面的反演和生成函数会变成天书。反过来基础扎实之后你会发现很多复杂公式都是十一个基础动作的组合。比如斯特林数恒等式里经常出现 $\binom{n}{k}$ 和曲棍球棒卡特兰数的递推也可以用帕斯卡恒等式改写。最后分享一个我自己的小习惯每次复习组合数学先拿一张白纸把十一个恒等式默写出来不写表达式只写名称和用途。如果能默出八个以上说明状态还在如果只能默出三四个那就重新推一遍。这个方法很笨但对我很管用。