hockey-stick · 双计数

组合恒等式与双计数

一条组合恒等式至少有两种读法。代数读法把两边各自展开、对齐同类项；组合读法给两边各配一个计数问题，再论证它们数的是同一批对象。后者称作双计数（double counting）：同一个集合被数了两遍，两个结果只能相等。本页取三条恒等式，每条都按这两种读法各解一次，其中第一条还能在 Pascal 三角上直接看出形状。

1 · 曲棍球棒恒等式

hockey stick · Σᵢ C(i, k) = C(n+1, k+1)

\sum_{i=k}^{n} C(i,\, k) = C(n+1,\, k+1)

组合读法：从 $0, 1, \dots, n$ 这 $n+1$ 个数里选 $k+1$ 个，共 $C(n+1, k+1)$ 种。按选中的最大那个数是 $i$ 分类，剩下的 $k$ 个必须取自比 $i$ 小的那 $i$ 个数，有 $C(i, k)$ 种； $i$ 的取值范围是 $k$ 到 $n$ ，因为 $i < k$ 时凑不出 $k$ 个更小的数。各类互斥且穷尽，相加就是左边。

几何读法要用到 Pascal 三角与二项式定理里的坐标： $C(i, k)$ 是第 $i$ 行第 $k$ 列，固定 $k$ 让 $i$ 递增，就是沿一条斜边往下走。这段斜边上所有格子的和落在 $C(n+1, k+1)$ 那一格，即斜边末端再往下一行、往右一列。杆是求和的那串格子，刃是答案所在的单格，合起来像一支曲棍球棒。

代数读法反复用 Pascal 递推 $C(n+1, k+1) = C(n, k) + C(n, k+1)$ 把右端逐层剥开：剥出 $C(n, k)$ ，余下的 $C(n, k+1)$ 继续剥，直到 $C(k+1, k+1)$ 换成 $C(k, k)$ 收尾。

图 1-1 · Pascal 三角上的恒等式高亮。浅色是左边求和涉及的格子，深色实心是右端那一格，右侧表列出逐项数值与两边的和。可切换恒等式并拖动

n

与

k

，单击表中某一项描出它对应的格。

2 · 委员会与主席

从 $n$ 人里选出一个委员会，再从委员会里指定一名主席。这件事的结果有多少种，取决于按什么次序去数。

先定委员会规模：取 $k$ 人有 $C(n, k)$ 种，再从这 $k$ 人里挑主席有 $k$ 种； $k$ 从 $0$ 遍历到 $n$ 相加，得到 $\sum_k k\, C(n, k)$ 。先定主席： $n$ 种选法，剩下的 $n-1$ 人各自独立地决定参不参加，得到 $n\, 2^{n-1}$ 。两种数法数的是同一批「委员会加主席」的搭配：

\sum_{k=0}^{n} k\, C(n,\, k) = n\, 2^{n-1}

作为热身， $\sum_k C(n, k) = 2^n$ 是同一套路的退化情形：左边按子集大小分类，右边让每个元素独立地二选一。代数上它是二项式定理在 $a = b = 1$ 处的取值，加权和则是 $(1+x)^n$ 求导后再取 $x = 1$ 。

3 · 平方和与对称性

\sum_{k} C(n,\, k)^2 = C(2n,\, n)

组合读法：把 $2n$ 个元素分成前 $n$ 个与后 $n$ 个，从中选 $n$ 个共 $C(2n, n)$ 种；按取自前一组的个数 $k$ 分类，前一组取 $k$ 个、后一组取 $n-k$ 个，该类有 $C(n, k)\, C(n, n-k)$ 种。这一步是范德蒙德卷积在 $m = n$ 、 $k = n$ 处的特例，再用对称性 $C(n, k) = C(n, n-k)$ 把乘积写成平方。

平方的来路值得单记一笔：左边两个因子本来数的是两件不同的事（前一组取几个、后一组取几个），把它们并成同一个数的平方靠的是对称性，而不是某种「自乘」的直觉。

注 · 双计数与双射是同一立场的两副面孔。双计数把同一批对象数两遍，两个计数式只能相等；双射则在两批对象之间造一一对应，两个集合只能一样大。前者不必写出对应关系，后者把它写了出来。§1 的分类求和是双计数；若把「最大元素为 $i$ 的那些子集」逐个映到「从 $i$ 以下取 $k$ 个」的选法，同一条恒等式就成了一族双射（bijection）的并。

4 · 浮点组合数的失守点

combinatorics/core/combinatorics.ts 的 comb 按 $r \leftarrow r \cdot (n-i)/(i+1)$ 逐步浮点乘除，末尾用 Math.round 收回整数。用它逐个 $n$ 验算上面三条恒等式，两边首次不等的位置分别是：平方和在 $n = 28$ ，差 $-1$ ；加权和在 $n = 51$ ，差 $+16$ ；曲棍球棒在 $n = 55$ 且 $k = 22$ ，差 $-1$ 。热身的 $\sum_k C(n, k) = 2^n$ 撑到 $n = 58$ ，差 $-64$ 。这四个数字与差值都写进了 identities.test.ts，实现一改就会报出来。

警示 · 两侧失守的机理不同，且都不是「超出 Number.MAX_SAFE_INTEGER」一句能概括的。 comb 首次返回错值是在 $C(56, 23)$ ：它给出 3167295784216201，精确值是 3167295784216200，而这个数还不到安全整数上限 9007199254740991 的一半，错的是中途几步浮点除法，Math.round 兜不住。平方和在 $n = 28$ 处的表现更反直觉——出错的是右边那一次 $C(56, 28)$ ，29 项平方累加起来的左边反而给出精确值 7648690600760440；曲棍球棒在 $n = 55$ 撞上的还是同一个 $C(56, 23)$ 。加权和与子集和的失守则在左边： $n = 51$ 时左边累加到 $5.74 \times 10^{16}$ ，早已越过安全整数上限，是加法本身开始丢低位，而右边的 $51 \cdot 2^{50}$ 恰好是双精度能精确表示的形式。

5 · 参考文献

Hockey-stick identity. Wikipedia. 曲棍球棒恒等式的组合证明与它在 Pascal 三角上的形状。https://en.wikipedia.org/wiki/Hockey-stick_identity
Double counting (proof technique). Wikipedia. 双计数作为证明手法的定义与经典例子。https://en.wikipedia.org/wiki/Double_counting_(proof_technique)
Binomial coefficient. Wikipedia. 二项式系数的恒等式汇总，含平方和与加权和两条。https://en.wikipedia.org/wiki/Binomial_coefficient
Vandermonde's identity. Wikipedia. 范德蒙德卷积及其 $m = n$ 特例。https://en.wikipedia.org/wiki/Vandermonde%27s_identity