1. 先把数两次这件事想明白组合恒等式的底层逻辑组合恒等式在组合数学里是个很特殊的存在——公式本身短得能背下来但真到了题目里尤其是带权的和式、带交错符号的和式、上下指标都不规则的和式绝大多数人第一反应还是这个我见过但想不起来怎么推。我刚接触这块的时候也是这个状态笔记本上抄了满满两页等式做题时照样卡住。后来才慢慢意识到问题不在于背得少而在于没搞懂这些等式彼此之间是怎么长出来的。一句话概括组合恒等式的本质它是同一个计数问题的两种不同数法。你把一个集合按某种方式数一遍得到 A换个角度再数一遍得到 B那么 A B 就是一个恒等式。这条路叫组合意义证明它不需要任何代数技巧只需要你能讲清楚一个故事。而所有的代数变形、生成函数、归纳法本质上都是在为那些暂时讲不出故事的恒等式准备的备用工具。这篇内容我打算按三个层次来写第一层把十一个最常用的恒等式的来源和用法讲清楚不是干巴巴列公式第二层讲证明方法同一个恒等式我会给出多种证法并说明各自适用的场合第三层讲求和方法也就是当你面对一个从没见过的和式时应该按什么顺序去尝试拆解。最后我会单独拿一节写那些答案差一个符号边界项多算一项的坑这些坑我在推导和写代码验证的时候都实打实踩过。适合谁看正在准备组合数学、离散数学相关课程的读者做算法题经常遇到组合数求和、需要推闭式的同学以及想给概率论、计数问题打底的从业者。不需要微积分基础但至少要熟悉排列组合的基本定义和阶乘的运算。全文统一记号$C(n,k)$ 表示从 $n$ 个不同元素中取 $k$ 个的组合数即 $C(n,k)\frac{n!}{k!(n-k)!}$等价于 $\binom{n}{k}$。约定当 $k0$ 或 $kn$$n$ 为非负整数时 $C(n,k)0$。2. 十一个必须刻进肌肉记忆的组合恒等式下面这十一个我按从地基到塔尖的顺序排建议不要跳着看因为后面的很多式子都是前面几个的直接推论。2.1 基础三件套对称、帕斯卡、吸收恒等式 1对称恒等式$C(n,k)C(n,n-k)$。组合意义明摆着选出 $k$ 个元素等价于选出要剩下的那 $n-k$ 个。这个小东西看着无用实际上在做指标平移的时候极其关键——很多和式的上下标对不上就是靠它翻过来的。恒等式 2帕斯卡恒等式$C(n,k)C(n-1,k)C(n-1,k-1)$。这是整个组合数学里最重要的递推关系也是帕斯卡三角的生成规则。它说的是从 $n$ 个元素里选 $k$ 个固定盯住某一个特定元素 $a$分两类——不选 $a$那就得从剩下 $n-1$ 个里选 $k$ 个选了 $a$那就从剩下 $n-1$ 个里再选 $k-1$ 个。两条路互斥且完备加起来就是总数。恒等式 3吸收恒等式$k,C(n,k)n,C(n-1,k-1)$。这个式子是消灭系数的主力。左边多出来的那个 $k$ 是个累赘用它换成一个常数 $n$ 和指标下移的组合数求和立刻变得可行。代数推导只要两行$$k,C(n,k)k\cdot\frac{n!}{k!(n-k)!}\frac{n!}{(k-1)!(n-k)!}n\cdot\frac{(n-1)!}{(k-1)!(n-1-(k-1))!}n,C(n-1,k-1)$$还有一个反向吸收的变体$C(n,k)\frac{n-k1}{k}C(n,k-1)$在需要把下标往上推的时候用。2.2 一行和式$\sum C(n,k)2^n$ 与它的交错兄弟恒等式 4二项式定理的 $x1$ 特例$\sum_{k0}^{n} C(n,k)2^n$。它其实是二项式定理 $(1x)^n\sum_{k0}^n C(n,k)x^k$ 在 $x1$ 处的取值但更值得记住的是它的组合解释$n$ 个元素的集合一共有 $2^n$ 个子集而按子集大小分类计数就是 $\sum_k C(n,k)$两次数法相等。恒等式 5交错和$\sum_{k0}^{n} (-1)^k C(n,k)0$当 $n\ge 1$当 $n0$ 时和为 $1$。对应二项式定理取 $x-1$。这个式子背后的含义是非空集合中偶数元子集和奇数元子集一样多。我在做题时见过太多次忘了 $n0$ 这个边界导致答案在 $n0$ 处崩掉后面第 5 节会专门说。2.3 带权求和$k$ 的一次方与二次方恒等式 6$\sum_{k0}^{n} k,C(n,k)n,2^{,n-1}$。证明只有一步用吸收恒等式把 $k,C(n,k)$ 换成 $n,C(n-1,k-1)$把 $n$ 提到求和号外面剩下的 $\sum_{k0}^n C(n-1,k-1)\sum_{j0}^{n-1}C(n-1,j)2^{n-1}$。恒等式 7$\sum_{k0}^{n} k^2,C(n,k)n(n1)2^{,n-2}$。这个稍微绕一点。常用做法是把 $k^2$ 拆成 $k(k-1)k$其中 $k$ 的那部分直接用恒等式 6而 $k(k-1)$ 用两次吸收$k(k-1)C(n,k)n(n-1)C(n-2,k-2)$于是 $\sum_k k(k-1)C(n,k)n(n-1)2^{n-2}$。两部分相加得 $n(n-1)2^{n-2}n2^{n-1}n(n1)2^{n-2}$。这个降幂拆项的思路可以一路推到 $k^3$、$k^4$因为 $k^m$ 总能写成若干个 $k(k-1)\cdots(k-j1)$ 的线性组合这就是下降阶乘的威力本质上是把普通幂换成组合数的自然基底。2.4 卷积三连范德蒙德、平方和、曲棍球棒恒等式 8范德蒙德卷积$\sum_{k0}^{r} C(m,k),C(n,r-k)C(mn,r)$。这是卷积型恒等式的祖宗。组合意义从 $m$ 个红球、$n$ 个蓝球中一共取 $r$ 个球按取到的红球个数 $k$ 分类每一类有 $C(m,k)C(n,r-k)$ 种取法全加起来就是 $C(mn,r)$。恒等式 9平方和恒等式$\sum_{k0}^{n} C(n,k)^2C(2n,n)$。它就是范德蒙德在 $mnr$ 处的特例。这个式子在概率和统计里出现频率极高因为 $C(2n,n)$ 的增长量级约为 $4^n/\sqrt{\pi n}$直接从平方和形式看不出这个量级。恒等式 10曲棍球棒恒等式$\sum_{ir}^{n} C(i,r)C(n1,r1)$。沿着帕斯卡三角的某一斜列求和形状像根曲棍球棒名字就是这么来的。它的证明用帕斯卡恒等式逐项合并$C(r,r)C(r1,r1)$加上 $C(r1,r)$ 得 $C(r2,r1)$一路滚到 $C(n1,r1)$。2.5 朱世杰恒等式与上指标求和恒等式 11朱世杰恒等式$\sum_{k0}^{r} C(nk,k)C(nr1,r)$。元代数学家朱世杰在《四元玉鉴》里给出的这个结论本质上是曲棍球棒的一个变体把 $C(nk,k)$ 写成 $C(nk,n)$再用恒等式 10 即可。它专门用来处理上指标在变、下指标跟着变的和式比如 $\sum_{k\ge 0}C(nk,k)x^k$ 这类生成函数的闭式推导中会用到。为方便对照把十一个恒等式集中列一下编号名称表达式主要用途1对称$C(n,k)C(n,n-k)$指标翻转对齐2帕斯卡$C(n,k)C(n-1,k)C(n-1,k-1)$递推、归纳3吸收$k,C(n,k)n,C(n-1,k-1)$消灭线性系数4行和$\sum_k C(n,k)2^n$收尾化简5交错和$\sum_k(-1)^kC(n,k)0$容斥、奇偶相消6一次加权$\sum_k k,C(n,k)n2^{n-1}$期望值计算7二次加权$\sum_k k^2C(n,k)n(n1)2^{n-2}$方差计算8范德蒙德$\sum_k C(m,k)C(n,r-k)C(mn,r)$卷积合并9平方和$\sum_k C(n,k)^2C(2n,n)$中心二项式系数10曲棍球棒$\sum_{ir}^n C(i,r)C(n1,r1)$变上指标求和11朱世杰$\sum_{k0}^r C(nk,k)C(nr1,r)$生成函数闭式3. 证明方法同一个恒等式我能给你四种证法背下来只是第一步。真正拉开差距的是面对一个陌生恒等式你知道从哪条路切进去。我总结下来常用的就四条路各有各的舒适区。3.1 组合意义法会讲故事就能证这是最优先尝试的方法因为它最短、最不容易出错而且往往给你额外的直觉。以范德蒙德卷积为例整个证明就是上面那句分红球蓝球两行字结束不需要任何代数运算。再看恒等式 9 的另一个角度$\sum_k C(n,k)^2$ 可以理解为从一个 $n$ 人男生组和一个 $n$ 人女生组里一共挑 $n$ 个人按挑中男生人数分组计数结果当然是 $C(2n,n)$。这个解释还顺手告诉你为什么它天然就是个整数——它本来就是计数的结果。这类方法适用的信号和式的每一项都能拆成从两个不相交集合里分别取一部分的形状也就是出现了乘积 $C(a,i)C(b,j)$ 且 $ij$ 是常数。3.2 归纳法与递推帕斯卡三角的连锁反应当恒等式两边都带着 $n$ 的时候归纳法是很自然的选择。标准的操作是验证 $n0$或 $n1$的基例然后假设 $n-1$ 成立对 $n$ 的情形用帕斯卡恒等式把 $C(n,k)$ 拆成 $C(n-1,k)C(n-1,k-1)$拆完之后原来的和式就裂成两个可以用归纳假设处理的式子。拿 $\sum_k C(n,k)2^n$ 举例用归纳法做的话就是$\sum_k C(n,k)\sum_k[C(n-1,k)C(n-1,k-1)]2^{n-1}2^{n-1}2^n$。曲棍球棒恒等式的证明本质上也属于这一类只不过它是逐项吸收而不是标准归纳。归纳法的缺点是容易在指标边界上出错拆项之后两个和式的上下限往往不一样必须老老实实把 $k0$ 和 $kn$ 这些端点单独拿出来看。3.3 生成函数法求导、乘 $x$、再取系数这是处理加权和式的核武器。核心观察是$(1x)^n\sum_k C(n,k)x^k$那么对两边求导就得到 $n(1x)^{n-1}\sum_k k,C(n,k)x^{k-1}$两边乘 $x$ 得 $nx(1x)^{n-1}\sum_k k,C(n,k)x^k$再令 $x1$ 就是恒等式 6。整个过程机械得像流水线写出二项式定理的母函数形式需要 $k$ 的一次因子就求一次导再乘 $x$需要 $k^2$ 就重复一遍需要 $1/(k1)$ 这类倒因子就对 $x$ 积分最后代入具体的 $x$ 取值。同一个流程套两遍就能得到恒等式 7而且不用动脑子去想怎么拆项。我在推导复杂和式时基本是先跑一遍这个流程看看能不能得到闭式不行再换别的思路。对于更复杂的和式还可以直接构造乘积型母函数。比如 $\sum_k C(m,k)C(n,r-k)$ 的闭式就是 $(1x)^m(1x)^n(1x)^{mn}$ 两边展开取 $x^r$ 系数一步到位。3.4 容斥与交错和$(-1)^k$ 从哪儿来看到 $(-1)^k$ 就先想到容斥原理。恒等式 5 就是一个典型的奇偶数量相等的结论它对应的是在 $n$ 个元素的集合里偶数元子集和奇数元子集一样多这件事可以构造一个配对证明固定某个元素 $a$把每个子集和它翻转 $a$ 的归属后的子集配成一对一奇一偶完美配对所以总数相抵。推广一步$\sum_k (-1)^k C(n,k) f(k)$ 形式的和式在很多筛法问题里出现处理的套路是先把 $f(k)$ 展开成下降阶乘的组合再用 $\sum_k(-1)^k C(n,k)C(k,j)(-1)^j C(n,j)\cdot[,nj,]$ 这类正交关系来过滤。这个正交关系是反演公式的基础值得单独记一笔$$\sum_{k} (-1)^k C(n,k),C(k,j) \begin{cases} (-1)^n, jn \ 0, jn \end{cases}$$它长得很像克罗内克函数所以常被用来做提取特定项的操作。4. 求和方法实战把陌生和式拽回已知恒等式真正的难处从来不是证明已知恒等式而是给你一个 $\sum_{k} \frac{k^32k}{k1}C(n,k)$ 之类的东西让你求闭式。我一般的处理顺序是这样从成本最低的开始试。4.1 第一步永远是对齐指标不要急着动手算先看和式的上下限和组合数的指标能不能对上。常见三种错位上指标差一个常数、下指标差一个常数、还有个系数需要吸收。对齐的手段就三个——对称恒等式翻转、帕斯卡拆项、吸收恒等式消系数。举个例子$\sum_{k0}^{n}\frac{k}{n}C(n,k)$ 这个和式先把 $\frac{k}{n}$ 用吸收恒等式变成 $\frac{C(n-1,k-1)}{C(n,k)}\cdot\frac{k}{n}$化简后等价于 $\frac{1}{n}\cdot n C(n-1,k-1)/C(n,k)$……实战里更省事的做法是直接看出它等于 $\frac{1}{n}\sum_k kC(n,k)2^{n-1}$。能看出来就别硬推指标对齐的目的是让和式落进已知模板不是炫技。4.2 吸收恒等式拆系数多项式因子怎么处理遇到 $k$ 的多项式因子统一策略是把它改写成下降阶乘的线性组合。$k^2k(k-1)k$$k^3k(k-1)(k-2)3k(k-1)k$这些展开系数就是第二类斯特林数。改写成下降阶乘后每一项用对应的多次吸收$$k(k-1)\cdots(k-j1),C(n,k)n(n-1)\cdots(n-j1),C(n-j,k-j)$$系数变成常数剩下的和式就是一个平移过的行和直接等于 $2^{n-j}$。整条链路清晰得不需要思考。下面这张表是我做题时最常查的对应关系和式形态首选方法结果$\sum_k C(n,k)$行和$2^n$$\sum_k k,C(n,k)$吸收 行和$n2^{n-1}$$\sum_k C(n,k)C(m,r-k)$范德蒙德$C(nm,r)$$\sum_k C(n,k)^2$范德蒙德特例$C(2n,n)$$\sum_{k}(-1)^kC(n,k)$容斥/二项式 $x-1$$0$$n\ge1$$\sum_k \frac{1}{k1}C(n,k)$积分或 $\frac{C(n1,k1)}{n1}$ 变形$\frac{2^{n1}-1}{n1}$$\sum_{ir}^{n}C(i,r)$曲棍球棒$C(n1,r1)$注意倒数第二行那个恒等式很有用它有个漂亮的变形$\frac{1}{k1}C(n,k)\frac{1}{n1}C(n1,k1)$这属于吸收恒等式的反向用法专门把分母上的 $k1$ 干掉。很多人不知道这个变形遇到分数系数就卡住。4.3 卷积视角把求和写成两堆里各取一点如果你看到的和式里有两个组合数相乘且它们各自的下指标加起来是常数比如 $k$ 和 $r-k$基本可以断定它是范德蒙德型。处理方法就是把两个上指标直接相加。比如 $\sum_k C(5,k)C(7,6-k)C(12,6)$一行出结果。如果下指标加起来不是常数可以试试先做变量替换。设 $jr-k$把整个和式改写成关于 $j$ 的形式很多时候一下子就露出常数的形状了。4.4 求导加乘 $x$ 的机械流程这个方法我在第 3.3 节讲过原理这里补一个完整点的操作细节。要处理 $\sum_k k^2C(n,k)$第一步写下 $(1x)^n\sum_k C(n,k)x^k$。 第二步两边对 $x$ 求导得 $n(1x)^{n-1}\sum_k kC(n,k)x^{k-1}$。 第三步两边乘 $x$得 $nx(1x)^{n-1}\sum_k kC(n,k)x^k$。 第四步对第三步的结果再求导一次左边是 $n(1x)^{n-1}n(n-1)x(1x)^{n-2}$右边是 $\sum_k k^2C(n,k)x^{k-1}$。 第五步再乘 $x$ 并令 $x1$左边变成 $n2^{n-1}n(n-1)2^{n-2}$整理即 $n(n1)2^{n-2}$。这套流程的好处是完全不需要灵感只要耐心。缺点是对 $1/k$ 这种因子的处理需要积分而积分会引入常数项得靠 $x0$ 处的取值把这个常数定出来。我踩过这个坑忘了定常数结果整体差一个 $1/(n1)$ 的偏移。4.5 交换求和次序双求和降维遇到 $\sum_i\sum_j C(i,j)$ 这种双求和第一反应应该是交换次序。交换之后往往内层能直接套用一个已知恒等式外层就变成一个简单的和式。经典的例子是证明 $\sum_{i0}^n 2^i 2^{n1}-1$ 可以用组合方法也可以先写成 $\sum_i\sum_j C(i,j)$ 再交换。交换求和次序要注意的一件事是范围改写。原来是 $0\le j\le i\le n$交换后是 $0\le j\le n$ 且 $j\le i\le n$这个不等式组要写对写错了后面全错。我习惯画个坐标图把求和区域画成三角形交换次序就是换个方向切。5. 那些让答案差一个符号的坑这一节是整篇里我自己踩坑最多的部分。这些细节在很多教材里被一句显然带过但真到实际推导时它们就是答案对不上的元凶。5.1 $k$ 超出范围时组合数取 $0$ 的约定只要记住 $C(n,k)0$当 $k0$ 或 $kn$很多麻烦就会自动消失。比如写 $\sum_{k0}^{n}C(n-1,k-1)$你完全可以直接把求和范围放宽成 $\sum_{k-\infty}^{\infty}$因为所有越界的项天然是 $0$。这样一来做变量替换、交换次序的时候就不用反反复复改上下限出错概率大幅下降。提示一旦采用了全域求和 越界为零的约定指标的平移就变成了纯粹的代数操作可以放心地把 $k$ 换成 $k-1$ 而不用管上下限。5.2 交错和的边界$n0$ 与 $n0$ 完全不同$\sum_k(-1)^kC(n,k)$ 在 $n\ge 1$ 时是 $0$在 $n0$ 时是 $1$。这个差异在很多递推题里是致命的——比如你推导一个关于 $n$ 的递推式$n0$ 的基例必须单独拿出来处理否则整个序列从第二项开始就全错了。我的做法是推导完成后用 $n1,2,3$ 手算代入验证一遍特别是 $n1$ 这种退化情形最容易暴露问题。写代码验证的时候把 $n$ 从 $0$ 开始枚举不要图省事从 $1$ 开始。from math import comb # 边界检查n0 与 n1 的交错和 for n in range(0, 6): s sum((-1)**k * comb(n, k) for k in range(n 1)) print(n, s) # n0 输出 1其余输出 05.3 交换求和次序的合法性有限和之间交换次序永远合法这是无条件的。但如果你处理的是无穷级数尤其是那些不是绝对收敛的级数交换次序就可能改变结果。组合数学里大部分和式都是有限的所以问题不大但一旦牵扯到生成函数的系数提取和积分、极限的交换就要格外小心。我自己的经验是只要和式的项数是有限的哪怕上限写成无穷但实际只有有限项非零就放心交换。而涉及无穷级数的场合先在有限截断上验证一遍等式成立再去考虑取极限。5.4 手算验证小规模枚举是最后一道防线不管你的推导多流畅最后一定要拿具体数字代进去算一遍。校验的顺序建议是先验证公式在 $n$ 最小几个值上成立再验证它和已知的等价形式一致最后检查量级是否合理。举个我实际遇到的例子我在推 $\sum_k \frac{k}{k1}C(n,k)$ 时得到了 $2^n-\frac{2^{n1}-1}{n1}$ 这个结果。代 $n2$ 进去左边是 $\frac{1}{2}\cdot2\frac{2}{3}\cdot11\frac{2}{3}\frac{5}{3}$右边是 $4-\frac{7}{3}\frac{5}{3}$。对上了。但如果我当时把 $\frac{1}{k1}C(n,k)$ 的变形记错成 $\frac{1}{n}C(n,k1)$代数字立刻就会露馅。6. 三道实战题从题目到闭式的完整推理链最后用三道题把前面讲的方法串一遍。这三道题的难度是递增的建议先自己想几分钟再看解答思路。6.1 第一题带 $k^2$ 的加权和题目求 $\sum_{k0}^{n} (2k^2k),C(n,k)$。思路拆成两块。$\sum_k k,C(n,k)n2^{n-1}$ 直接用恒等式 6$\sum_k k^2C(n,k)n(n1)2^{n-2}$ 用恒等式 7。所以结果是 $2n(n1)2^{n-2}n2^{n-1}n(n1)2^{n-1}n2^{n-1}n(n2)2^{n-1}$。验证$n1$ 时左边是 $0\cdot13\cdot13$右边是 $1\cdot3\cdot13$。$n2$ 时左边是 $03\cdot210\cdot116$右边是 $2\cdot4\cdot216$。对上。6.2 第二题双下标卷积题目求 $\sum_{k0}^{n}\binom{n}{k}\binom{n}{k-1}$。思路先做指标平移令 $jk-1$和式变成 $\sum_j \binom{n}{j1}\binom{n}{j}$。这时候先别急着找范德蒙德因为两个组合数的上指标相同、下指标差 1直接套范德蒙德是不行的。换个思路用对称恒等式把第二个因子翻过来$\binom{n}{j}\binom{n}{n-j}$于是原式变成 $\sum_j \binom{n}{j1}\binom{n}{n-j}$这回收敛成范德蒙德的标准形状了下指标之和 $(j1)(n-j)n1$ 为常数结果是 $\binom{2n}{n1}$。验证$n2$ 时左边是 $\binom{2}{0}\binom{2}{-1}\binom{2}{1}\binom{2}{0}\binom{2}{2}\binom{2}{1}0224$右边是 $\binom{4}{3}4$对上。这道题的教学价值在于看到两个组合数相乘但下指标之和不是常数时先试对称恒等式翻转这一步经常能把死局盘活。6.3 第三题带 $(-1)^k$ 的变系数和题目求 $\sum_{k0}^{n} (-1)^k \binom{n}{k} \frac{1}{k1}$。思路关键在于处理 $\frac{1}{k1}$。用吸收恒等式的反向形式$\frac{1}{k1}\binom{n}{k}\frac{1}{n1}\binom{n1}{k1}$。代入后有$$\sum_k (-1)^k\binom{n}{k}\frac{1}{k1}\frac{1}{n1}\sum_{k}(-1)^k\binom{n1}{k1}$$把 $k1$ 记作 $j$$(-1)^k(-1)^{j-1}-(-1)^j$于是上式变成 $-\frac{1}{n1}\sum_{j1}^{n1}(-1)^j\binom{n1}{j}$。由交错和恒等式$\sum_{j0}^{n1}(-1)^j\binom{n1}{j}0$$n1\ge1$所以从 $j1$ 开始的求和等于 $-(-1)^0\binom{n1}{0}-1$。最终结果是 $\frac{1}{n1}$。验证$n1$ 时$\binom{1}{0}\cdot1-\binom{1}{1}\cdot\frac{1}{2}1-\frac{1}{2}\frac{1}{2}$右边 $\frac{1}{2}$对上。$n2$ 时$1-2\cdot\frac{1}{2}1\cdot\frac{1}{3}\frac{1}{3}$右边 $\frac{1}{3}$也对上。这个结果其实还有个很漂亮的积分解释$\int_0^1 (1-x)^n dx\frac{1}{n1}$而对 $(1-x)^n$ 二项式展开后逐项积分正好得到上面那个和式。两条路殊途同归。我个人在实际操作中的体会是组合恒等式这块最值得投入时间的地方不是把所有式子背全而是把双向计数吸收降幂生成函数求导这三条主线练到条件反射。真正的题目千变万化但只要你能快速判断它属于哪一类——是卷积型、是加权型、还是交错型——后面就是套流程的事。另外无论推导看起来多顺只要条件允许就代几个小数字进去算一算这个习惯帮我省下的返工时间比我学会任何一个具体恒等式带来的收益都大。