二项式系数

二项式系数 $\binom{n}{k}$ 表示从 $n$ 个不同元素中取出 $k$ 个的组合数（不计顺序），也是 $(1+x)^n$ 展开式中 $x^k$ 的系数。中文教材常记作 $C_n^k$，英文文献记作 $C(n,k)$ 或 ${}_nC_k$；注意 $C_n^k$ 与 $\binom{n}{k}$ 的上下标位置相反：前者下标 $n$ 是元素总数，上标 $k$ 是取出个数。

定义

• 组合意义：$\binom{n}{k}$ 是从 $n$ 个不同元素中取出 $k$ 个（不考虑顺序）的组合数。
• 多项式意义：$\binom{n}{k}$ 是多项式 $(1+x)^n$ 展开式中 $x^k$ 的系数：

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

若 $x,y$ 是同一个交换环上的元素，则 $(x+y)^n$ 的展开满足二项式定理：

$$(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k$$

指数推广到任意实数或复数时即广义二项式定理。

阶乘公式

二项式系数最简洁的表达式是阶乘：

$$\binom{n}{k}=\frac{n!}{k!(n-k)!},\quad 0\le k\le n$$

对称性：$\binom{n}{k}=\binom{n}{n-k}$；更一般地

$$\binom{m+n}{n}=\frac{(m+n)!}{m!\cdot n!}=\binom{m+n}{m}$$

即从 $m+n$ 个元素中取出 $m$ 个或 $n$ 个，两种情形的组合数相等。

求和：$\sum_{k=0}^{n}\binom{n}{k}=2^n$，即 $n$ 元集的子集总数。$\binom{n}{k}$ 还作为概率权重出现在二项分布的分布列中。

示例：从 5 个不同元素中取 2 个，有

$$\binom{5}{2}=\frac{5!}{2!\cdot 3!}=\frac{5\cdot4}{2}=10$$

种方式。

递归公式

$$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},\quad 1\le k\le n-1$$

配合边界条件：

$$\binom{n}{0}=1\ (n\ge0),\qquad \binom{0}{k}=0\ (k\ge1)$$

当 $k>n$ 时 $\binom{n}{k}=0$，且对所有 $n$ 有 $\binom{n}{n}=1$，递推可在这些情形中断。该式可由计算 $(1+x)^{n-1}(1+x)$ 中 $x^k$ 的系数得出，也可点算集合 $\{1,2,\cdots,n\}$ 的 $k$ 元子集：包含元素 $n$ 的有 $\binom{n-1}{k-1}$ 个，不包含元素 $n$ 的有 $\binom{n-1}{k}$ 个。递推公式可用作建构帕斯卡三角形。

乘数公式

个别二项式系数可用以下公式计算：

$$\binom{n}{k}=\frac{n^{\underline{k}}}{k!}=\frac{n(n-1)(n-2)\cdots[n-(k-1)]}{k(k-1)(k-2)\cdots1}=\prod_{i=1}^{k}\frac{n-(k-i)}{i}$$

其中分子 $n^{\underline{k}}=n(n-1)\cdots(n-k+1)$ 是下降阶乘幂（一阶乘幂），即排列数 $P(n,k)$。从组合意义理解：分子为从 $n$ 个元素中取出 $k$ 个元素的有序排列数（相同元素、不同次序也计数），分母 $k!$ 消去同一 $k$ 元组的 $k!$ 种排列次序，即得不计顺序的组合数。