二项式系数

二项式系数回答的是最基本的计数问题之一："从 $n$ 个互异对象中无序地取出 $k$ 个，有多少种取法"，也就是组合公理库组合Combination · k-subset从有限集合中无序选取固定数量元素所得的子集。的个数。闭式的来历值得体会：先按顺序逐个挑选，第一步有 $n$ 种选择、第二步有 $n-1$ 种，直到选满 $k$ 个，共 $n(n-1)\cdots (n-k+1)$ 个有序结果；但同一个 $k$ 元子集会以 $k!$ 种不同顺序被列举出来，每种恰好一次，所以除以 $k!$ 后每个子集只计一次。换句话说，分母中的 $k!$ 不是技术性修饰，而是"把有序计数折算成无序计数"这一步的精确代价。把 $(\genfrac{}{}{0ex}{}{n}{k})$ 理解为一种基数（子集族的基数公理库基数Cardinality · Size of a set忽略元素性质与排列，只用双射和单射刻画集合的大小及其比较。）而不只是一个分式，很多恒等式就能靠"给两边找同一个计数对象"来证明，而不必做代数变形。

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

这个公式针对互异对象、不重复、无顺序的选取，三个条件改动任何一个都需要换模型：讲究顺序时应数排列数 $n!/(n-k)!$ 而非组合数；允许重复选取时答案是可重组合数 $(\genfrac{}{}{0ex}{}{n+k-1}{k})$，由隔板法公理库隔板法Stars and bars把相同对象分入有标号盒子的整数解计数方法。给出；对象本身有重复（多重集合）时还要再除以各组内部的排列数。混用这些模型是初学计数最常见的错误来源。另外，闭式含 $n!$，直接按阶乘计算很快溢出，实际计算多用逐项乘除或 Pascal 恒等式递推。

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

它既是 Pascal 三角形的生成规则，也是对二项式系数做数学归纳公理库数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。的标准杠杆。二项式系数因二项式定理公理库二项式定理Binomial theorem(x+y)^n 按二项式系数展开为各次幂项之和。得名：它恰是 $(x+y{)}^n$ 展开式的系数，取特值立即得到 $\sum _k(\genfrac{}{}{0ex}{}{n}{k})=2^n$（也可直接解释为 $n$ 元集合的子集总数）。在概率论中它计数 $n$ 次 Bernoulli 试验公理库Bernoulli 随机变量Bernoulli random variable只取 0 与 1 且成功概率为 p 的基本随机变量。中恰好成功 $k$ 次的结果序列，从而给出二项分布的质量函数；在组合学内部，它是多项式系数公理库多项式系数Multinomial coefficient把 n 个可区分对象分入若干有标号组时的计数系数 n!/(n1!⋯nk!)。的二元特例，也是 Catalan 数公理库Catalan 数Catalan number计数正确括号串、凸多边形三角剖分等结构的一族整数。等更精细计数序列的原材料。

固定 $m$ 元集合时，大小至多 $d$ 的子集共有

上限写成 $min\{d,m\}$ 处理了 $d>m$；采用本页的越界约定时也可写到 $d$。Sauer–Shelah 引理公理库Sauer–Shelah 引理Sauer's lemma · Sauer–Shelah–Perles lemma把有限 VC 维转化为假设类在有限样本上的多项式标注数上界。用这一个数限制 VC 维为 $d$ 的函数类在 $m$ 点上的标注数，压缩泛化界公理库压缩泛化界Sample compression generalization bound · Compression bound通过计数压缩子样本和辅助信息，把一致样本压缩方案的描述长度转化为分布无关泛化界。则用类似的“选择少量样本及附加信息”计数控制可输出规则数。两处计数都依赖真正不同的子集或重建结果，不能把同一对象的多种编码重复计算。