二项式系数 | Codeboy's Blog

形式陈述

对整数 $n\ge0$ 与 $0\le k\le n$ ，二项式系数定义为 $n$ 元集合的 $k$ 元组合个数：

\binom nk=\left|\left\{C\subseteq\{1,\ldots,n\}:|C|=k\right\}\right|.

它有闭式

\binom nk=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots(n-k+1)}{k!}.

通常约定 $k<0$ 或 $k>n$ 时 $\binom nk=0$ ，这使得各种求和恒等式无须额外限定求和范围。

直觉

组合是选出的对象，二项式系数是这些对象的总数。计算它时，可以先顺序挑选，再把同一子集的 $k!$ 种排列合并；这解释了闭式中的除法。但这一个整数并不局限于“选人”：只要能和 $k$ 元子集一一配对，就能使用同一个计数。

例如给五个位置编号，子集 $\{2,5\}$ 对应二进制串 $01001$ ：被选位置写 $1$ ，其余写 $0$ 。反向读取串中 $1$ 的位置，就找回原子集，所以五位中恰有两个 $1$ 的串也有 $\binom52$ 个。若把 $1$ 改读为向右一步、 $0$ 改读为向上一步，同一串又给出从 $(0,0)$ 到 $(2,3)$ 的一条单调格路。三种对象的外观不同，保留的信息都是“哪两个位置被选中”。

把 $\binom nk$ 理解为一个子集族的基数，恒等式就可以通过两种方式数同一批对象来证明。这样往往比展开阶乘更能解释等式为什么成立。

例子与边界

从五人中选两人共有 $\binom52=\frac{5\cdot4}{2!}=10$ 种。对称恒等式 $\binom nk=\binom n{n-k}$ 有一行双射证明：选中 $k$ 人的方案与排除其余 $n-k$ 人的方案一一对应，例如 $\binom52=\binom53=10$ 。边界值 $\binom n0=\binom nn=1$ 分别对应空集与全集这两个唯一的子集。

这个公式针对互异对象、不重复、无顺序的选取。讲究顺序时应数 $n!/(n-k)!$ 个部分排列；允许从 $n\ge1$ 种类型中无限重复选取 $k$ 个时，答案是 $\binom{n+k-1}{k}$ ，由隔板法给出。若每种类型库存有限，就必须另外计入上限，不能统一“除以重复元素的阶乘”。例如从 $a,a,b$ 中无序取两个，可见结果只有 $aa,ab$ ；而排列全部三个符号才适用 $3!/2!=3$ 。前者在计数受限选择，后者在计数固定重数的有序安排。

直接计算三个阶乘很快溢出，即使最终组合数仍能表示也可能发生中间溢出。实际计算可用精确整数逐项乘除，或用 Pascal 恒等式递推；采用模运算时，除法还要求分母可逆，不能直接照搬整数除法。

推论与应用

对 $n\ge1$ ，按某个固定元素是否被选中分类，可得 Pascal 恒等式

\binom nk=\binom{n-1}{k}+\binom{n-1}{k-1},

具体地，固定一个元素 $a$ ：不选 $a$ 的组合从其余 $n-1$ 个元素中选 $k$ 个；选 $a$ 的组合删去 $a$ 后剩下一个 $(k-1)$ 元子集。两类互斥且没有遗漏。例如 $\binom52=\binom42+\binom41=6+4$ 。

它既是 Pascal 三角形的生成规则，也是对二项式系数做数学归纳的标准杠杆。二项式系数因二项式定理得名：它恰是 $(x+y)^n$ 展开式的系数，取特值立即得到 $\sum_k\binom nk=2^n$ （也可直接解释为 $n$ 元集合的子集总数）。在概率论中它计数 $n$ 次 Bernoulli 试验中恰好成功 $k$ 次的结果序列，从而给出二项分布的质量函数；在组合学内部，它是多项式系数的二元特例，也是 Catalan 数等更精细计数序列的原材料。

对整数 $m,d\ge0$ ，固定 $m$ 元集合时，大小至多 $d$ 的子集共有

\sum_{i=0}^{\min\{d,m\}}\binom mi.

上限写成 $\min\{d,m\}$ 处理了 $d>m$ ；采用本页的越界约定时也可写到 $d$ 。Sauer–Shelah 引理用这一个数限制 VC 维为 $d$ 的函数类在 $m$ 点上的标注数，压缩泛化界则用类似的“选择少量样本及附加信息”计数控制可输出规则数。两处计数都依赖真正不同的子集或重建结果，不能把同一对象的多种编码重复计算。

参考资料

Oscar Levin, Discrete Mathematics: An Open Introduction, 3rd ed., 2019，§1.2 Binomial Coefficients，Subsets、Bit Strings、Lattice Paths 与 Pascal’s Triangle。
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019, §6.4.

形式陈述 ​

反向链接

形式陈述