二项式系数 · aiwiki.page

二项式系数记作 $\binom{n}{k}$ ，读作“从 $n$ 个中选 $k$ 个”，表示从 $n$ 个不同对象中选出 $k$ 个、且不计顺序的方法数。等价地，它表示一个含有 $n$ 个元素的集合中，含有 $k$ 个元素的子集的数量。这些数将组合数学与代数联系起来：它们也是二项式定理所描述的展开式中的系数。(discrete.openmathbooks.org)

定义与计数意义

对于满足 $0\leq k\leq n$ 的非负整数 $n$ 和 $k$ ，有

\binom{n}{k}=\frac{n!}{k!(n-k)!},

其中 $n!$ 表示阶乘，且 $0!=1$ 。边界值为

\binom{n}{0}=\binom{n}{n}=1.

对于固定的非负整数 $n$ ，通常将定义扩展为：当 $k<0$ 或 $k>n$ 时， $\binom{n}{k}=0$ 。这样，许多恒等式就无需另行讨论边界情况。(dlmf.nist.gov)

阶乘公式可以通过先计算有序选取的方法数来推导：

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

每一种无序选取都有 $k!$ 种排列，因此在上述计数中出现了 $k!$ 次；除以 $k!$ 即可消除重复计数。例如，

\binom{5}{2}=\frac{5\cdot4}{2\cdot1}=10.

因此，五个人可以组成十个不同的两人委员会。这一计数解释要求对象彼此不同、不能重复选取，且选取顺序不影响结果。(discrete.openmathbooks.org)

二项式展开

对于非负整数 $n$ ，有

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k.

要得到 $a^{n-k}b^k$ ，需要在 $n$ 个因式中恰好从 $k$ 个因式里选取 $b$ ，从其余因式里选取 $a$ 。这样的选法共有 $\binom{n}{k}$ 种。例如，

(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4.

该公式适用于乘法满足交换律的量；对于乘法不满足交换律的矩阵或算子，这一形式通常不成立。(dlmf.nist.gov)

令 $a=1$ ，可得生成函数

\sum_{k=0}^{n}\binom{n}{k}x^k=(1+x)^n,

这是一个多项式，其各项系数记录了不同大小的子集的数量。(dlmf.nist.gov)

帕斯卡三角形与递推关系

按上标排列二项式系数，就得到帕斯卡三角形，其行号从零开始：

\begin{array}{c|rrrrrr} n=0&1\\ n=1&1&1\\ n=2&1&2&1\\ n=3&1&3&3&1\\ n=4&1&4&6&4&1\\ n=5&1&5&10&10&5&1 \end{array}

三角形内部的数满足帕斯卡递推关系：

\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}.

证明时，先指定一个对象。选取 $k$ 个对象时，要么包含该对象，此时还需从其余 $n-1$ 个对象中选出 $k-1$ 个；要么不包含该对象，此时需从其余对象中选出 $k$ 个。这两种情况互不重叠，且涵盖了所有可能。(discrete.openmathbooks.org)

这一三角形的历史早于帕斯卡的研究：印度、中国和伊斯兰数学传统中都曾出现过更早的形式。帕斯卡在十七世纪的研究发展了它的性质与应用，而非首次提出这一数表。(opentext.uleth.ca)

基本恒等式

将每个选取结果与其补集配对，即可得到对称性：

\binom{n}{k}=\binom{n}{n-k}.

行和

\sum_{k=0}^{n}\binom{n}{k}=2^n

计算的是所有子集的数量，等价地说，就是幂集中所有元素的数量。交错行和为

\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 \qquad(n\geq1).

这两个求和公式也可通过分别在 $(1+x)^n$ 中代入 $x=1$ 和 $x=-1$ 得到。(dlmf.nist.gov)

范德蒙德恒等式为

\sum_{j=0}^{r}\binom{m}{j}\binom{n}{r-j} =\binom{m+n}{r}.

它计算从两个不相交的集合中共选出 $r$ 个元素的方法数，具体做法是按选出的元素中有多少个来自第一个集合来分类计数。(dlmf.nist.gov)

在概率与路径计数中的应用

在概率中，二项分布描述的是 $n$ 次独立试验中的成功次数 $X$ ，其中每次试验的成功概率均为 $p$ 。它的概率质量函数为

\Pr(X=k)=\binom{n}{k}p^k(1-p)^{n-k}, \qquad 0\leq k\leq n.

其中，二项式系数计算的是成功发生在哪 $k$ 次试验中的可能安排数；其余因子则给出每一种此类结果安排的概率。(statslab.cam.ac.uk)

二项式系数也用于计算格点路径的数量。从 $(0,0)$ 到 $(a,b)$ 的路径，若每一步只能向右或向上移动一个单位，则共有 $a+b$ 步。选择其中 $b$ 个向上步所在的位置，可得路径总数为

\binom{a+b}{b}.

若有禁止经过某些点或越过某些边界等限制，则需要额外的计数论证。(dlmf.nist.gov)

计算与数值限制

计算单个二项式系数时，可采用连乘方法，避免计算三个阶乘。令 $r=\min(k,n-k)$ ，则

\binom{n}{k} =\prod_{i=1}^{r}\frac{n-r+i}{i}.

从 $c=1$ 开始，按

c\leftarrow\frac{c(n-r+i)}{i}

更新；若采用精确运算，每一步更新后得到的都是整数。不过，即使最终系数没有超出定长整数的表示范围，中间的乘法结果仍可能溢出。在乘法之前约去公因子可以降低这种风险。(commons.apache.org)

若需要计算许多相邻的系数，可以利用帕斯卡递推关系，通过加法进行动态规划计算。直接计算阶乘在数学上是正确的，但可能产生不必要的大中间值；因此，精确整数计算与近似数值计算是两类不同的计算任务。(discrete.openmathbooks.org)

广义系数

对于复数 $\alpha$ 和非负整数 $k$ ，广义二项式系数定义为

\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}, \qquad \binom{\alpha}{0}=1.

当 $k$ 固定时，这是关于 $\alpha$ 的多项式。当 $\alpha$ 为非负整数时，它与普通二项式系数一致；但在其他情况下，它不一定具有计数意义。(dlmf.nist.gov)

这些系数出现在广义二项式幂级数中：

(1+x)^\alpha =\sum_{k=0}^{\infty}\binom{\alpha}{k}x^k, \qquad |x|<1,

这里取在 $x=0$ 附近解析的分支。当 $\alpha$ 为非负整数时，该级数会终止，成为通常的有限展开式。(dlmf.nist.gov)

另一种推广是多项式系数：

\binom{n}{k_1,\ldots,k_s} =\frac{n!}{k_1!\cdots k_s!}, \qquad k_1+\cdots+k_s=n.

它计算的是将 $n$ 个不同对象分配到各个有标号的组中、且各组大小已指定时的分配方法数。二项式系数就是其中只有两组的情形。(dlmf.nist.gov)

参考来源

Binomial Coefficientsdiscrete.openmathbooks.org
DLMF: §1.2 Elementary Algebradlmf.nist.gov
DLMF: §26.3 Lattice Paths: Binomial Coefficientsdlmf.nist.gov
The Arithmetic Triangle (Pascal's Triangle)opentext.uleth.ca
BinomialCoefficient.javacommons.apache.org
DLMF: §4.6 Power Seriesdlmf.nist.gov
DLMF: §26.4 Lattice Paths: Multinomial Coefficients and Set Partitionsdlmf.nist.gov