二项式系数

<image>

在数学上，二项式系数是二项式定理中各项的系数。一般而言，二项式系数由两个非负整数$n$和$k$为参数决定，写作 $\tbinom nk$，定义为 $(1+x)^n$的多项式展开式中，$x^k$项的系数，因此一定是非负整数。如果将二项式系数 $\binom{n}{0},\binom{n}{1},\dots ,\binom{n}{n}$写成一行，再依照 $n=0,1,2,\dots$顺序由上往下排列，则构成帕斯卡三角形。

二项式系数常见于各数学领域中，尤其是组合数学。事实上，$\tbinom nk$可以被理解为从$n$个相异元素中取出$k$个元素的方法数，所以 $\tbinom nk$大多读作“$n$取$k$”。二项式系数 $\tbinom nk$的定义可以推广至$n$是复数的情况，而且仍然被称为二项式系数。

## 历史及记号

虽然二项式系数在公元10世纪就已经被发现（见帕斯卡三角形），但表达式 $\tbinom nk$却是到1826年才由安德烈亚斯·冯·厄廷格豪森首次始用。最早探讨二项式系数的论述是十世纪的 Halayudha写的印度教典籍《宾伽罗的计量圣典》（chandaḥśāstra）。约1150年，印度数学家婆什迦罗第二于其著作《Lilavati》中给出一个简单的描述。

二项式系数亦有不同的符号表达方式，包括：$C(n,k)$、$_n C_k$、$^n C_k$、$C^{k}_{n}$、$C^{n}_{k}$，其中的 C 代表组合（combinations）或选择（choices）。很多计算机使用含有 C 的变种记号，使得算式只占一行的空间，相同理由也发生在置换数 $P_k^n$，例如写作 P(n, k)。

## 定义及概念

对于非负整数$n$和$k$，二项式系数$\tbinom nk$定义为$(1+x)^n$的多项式展开式(又称为二项式系数的生成函数)中，$x^k$项的系数，即

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

事实上，若$x$、$y$为交换环上的元素，则

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

此数的另一出处在组合数学，表达了从$n$物中，不计较次序取$k$物有多少方式，亦即从一$n$元素集合中所能组成$k$元素子集的数量。此定义与上述定义相同，理由如下：若将幂$(1+X)^n$的$n$个因数逐一标记为$i$（从1至$n$），则任一$k$元素子集则建构成展式中的一个$X^k$项，故此该单项的系数等如此种子集的数量。亦因此，就任何自然数$n$和$k$而言，$\tbinom nk$亦为自然数。此外，二项式系数亦见于很多组合问题的解答中，如由$n$个位元（如数字0或1）组成的所有序列中，其和为$k$的数目为$\tbinom nk$，又如算式$k=a_1+a_2+\cdots+a_n$，其中每一$a_i$均为非负整数，则有$\tbinom{n+k-1}k$种写法。这些例子中，大部分可视作等同于点算$k$个元素的组合的数量。

## 计算二项式系数

除展开二项式或点算组合数量之外，尚有多种方式计算$\tbinom nk$的值。

### 递归公式

以下递归公式可计算二项式系数：

$$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N$$

其中特别指定：

$$\binom n0 = 1 \quad \forall n\in\N\cup\{0\},$$

$$\binom 0k = 0 \quad \forall k\in\N.$$

此公式可由计算$(1+x)^{n-1}(1+x)$中的$x^k$项，或点算集合$\left \{ 1,2,\cdots ,n \right \}$的$k$个元素组合中包含$n$与不包含$n$的数量得出。

显然，如果$k>n$，则$\tbinom nk=0$。而且对所有$n$，$\tbinom nn=1$，故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。

### 乘数公式

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

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

上式中第一个分数的分子是一阶乘幂。此公式可以二项式系数在计算组合数量的意义理解：分子为从$n$个元素中取出$k$个元素的序列之数量，当中包含同样的元素但不同排列次序的序列。分母则计算同样的$k$个元素可有多少种排序方式。

### 阶乘公式

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

$$\binom nk = \frac{n!}{k!\,(n-k)!} \quad \mbox{for }\ 0\leq k\leq n.$$

其中“$n!$”是$n$的阶乘，此公式从上述乘数公式中分子分母各乘以$(n-k)!$取得，所以此公式中的分子分母有众同共同因子。除非先行抵销两边中的共同因子，否则以此公式进行计算时较率欠佳，尤因阶乘的数值增长特快。惟此公式展示了二项式系数的对称特性：

$$\binom nk = \binom n{n-k} \quad \mbox{for }\ 0\leq k\leq n.$$

### 一般化形式及其与二项式级数的关系

若将$n$换成任意数值（负数、实数或复数）$\alpha$，甚至是在任何能为正整数给出逆元素的交换环中的一元素，则二项式系数可籍乘数公式扩展

$k<0$

$\tbinom n k = 0$

$k<0$

$\tbinom n k$

$$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1} <pre> \quad\mbox{for } k\in\N \mbox{ and arbitrary } \alpha. </pre>$$

此定义能使二项式公式一般化（其中一单项为1），故$\tbinom\alpha k$仍能相称地称作二项式系数：

$$(1+X)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} X^k.$$

此公式对任何复数$\alpha$及$X$，$\left \vert X \right \vert <1$时成立，故此亦可视作$X$的幂级数的恒等式，即系数为常数1，任意幂之级数定义，且在此定义下，对于幂的恒等式成立，例如

$$(1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta} \quad\mbox{and}\quad ((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta}.$$

若$\alpha$是一非负整数$n$，则所有$k>n$的项为零，此无穷级数变成有限项的和，还原为二项式公式，但对于$\alpha$的其他值，包括负数和有理数，此级数为无穷级数。

## 帕斯卡三角形 (杨辉三角)

<image>

帕斯卡法则是一重要的递归等式：

$${n \choose k} + {n \choose k+1} = {n+1 \choose k+1},$$ 此式可以用于数学归纳法，以证明$\tbinom n k$对于所有$n$和$k$均为自然数（等同于证明$k!$为所有$k$个连续整数之积的因数），此特性并不易从公式(1)中得出。

帕斯卡法则建构出帕斯卡三角形:

0:｜1

1:｜1｜1

2:｜1｜2｜1

3:｜1｜3｜3｜1

4:｜1｜4｜6｜4｜1

5:｜1｜5｜10｜10｜5｜1

6:｜1｜6｜15｜20｜15｜6｜1

7:｜1 ｜7 ｜21｜35｜35｜21｜7 ｜1

8:｜1 ｜8 ｜28｜56｜70｜56｜28｜8 ｜1

第$n$横行列出$\tbinom n k$的$k=0,\ldots ,n$项，其建构方法为在外边填上1，然后将上一行中每两个相邻数相加的和填在其下，此方法可快速地计算二项式系数而不涉及乘法或分数，例如从第5横行可马上得出

$$(x+y)^5=\boldsymbol{1}x^5+\boldsymbol{5}x^4 y+\boldsymbol{10}x^3 y^2+\boldsymbol{10}x^2 y^3+\boldsymbol{5}xy^4+\boldsymbol{1}y^5$$

在斜线上相邻项的差就是上一斜线上的数值，此乃上述递归等式(3)的延伸意义。

## 组合数学和统计学

二项式系数是组合数学中的重要课题，因其可用于众多常见的点算问题中，例如

- 共有$\tbinom n k$种方式从$n$元素中选取$k$项。见组合。
- 共有$\tbinom {n+k-1}k$种方式从一个$n$元素集合中选取（容许重复选取）$k$元素建立多重集。
- 共有$\tbinom {n+k} k$个字符串包含$k$个1和$n$个零。
- 共有$\tbinom {n+1} k$个字符串包含$k$个1和$n$个零，且没有两个1相邻。
- 卡塔兰数是$\frac {\tbinom{2n}n}{n+1}$
- 统计学中的二项式分布是$\tbinom n k p^k (1-p)^{n-k} \!$
- 贝兹曲线的公式。

## 以多项式表达二项式系数

就任就非负整数$k$，$\scriptstyle{\binom{t}{k}}$可表达为一多项式除以$k!$：

$$\binom{t}{k} =\frac{(t)_k}{k!}=\frac{(t)_k}{(k)_k}= \frac{t(t-1)(t-2)\cdots(t-k+1)}{k(k-1)(k-2)\cdots(2)(1)};\,\!$$

此为带有理数系数，变量是$t$的多项式，可对任意实数或复数$t$运算以得出二项式系数，此“广义二项式系数”见于牛顿广义二项式定理。

就任意$k$，多项式$\tbinom{t}{k}$可看成是惟一的$k$次多项式$p(t)$满足$p(0)=p(1)=\ldots=p(k-1)=0$及$p(k)=1$.

其系数可以第一类斯特灵数表示，即：

$$\binom{t}{k} = \sum_{i=0}^k \frac{s_{k,i}}{k!} t^i$$

$\tbinom{t}{k}$之导数可以对数微分计算：

$$\frac{\mathrm{d}}{\mathrm{d}t} \binom{t}{k} = \binom{t}{k} \sum_{i=0}^{k-1} \frac{1}{t-i}\,.$$

### 以二项式系数为多项式空间之基底

在任何包含Q的域中，最多$d$阶的多项式有惟一的线性组合$\sum_{k=0}^d a_k \binom{t}{k}$。系数$a_k$是数列$p(0), p(1), \ldots , p(k)$的第k差分，亦即：

$$a_k = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} p(i).$$

### 整数值多项式

每一多项式$\tbinom{t}{k}$在整数参数时均是整数值（可在$k$上，用帕斯卡法则以归纳法证明）。故此，二项式系数多项式的整数线性组合亦为整数值。反之，(3.5)表达了任何整数值的多项式均是二项式系数多项式的整数线性组合。一般而言，对于一个特征0域$k$的任何子环$R$，在$K[t]$内的多项式在整数参数时之值均在$R$内当且仅当该多项式是一二项式系数多项式的$R$-线性组合。

整数值多项式$\frac{3t(3t+1)}{2}$可表达作：

$$9\tbinom{t}{2} + 6 \tbinom{t}{1} + 0\tbinom{t}{0}$$

从$t=1,2,3$时$\frac{3t(3t+1)}{2}=6,21,45$用帕斯卡矩阵的逆可算出：

$$\begin{pmatrix} \tbinom{t-1}{0} & \tbinom{t-1}{1} & \tbinom{t-1}{2} \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\-1 & 1 & 0\\1 & -2 & 1 \end{pmatrix} \begin{pmatrix} 6 \\ 21 \\ 45 \end{pmatrix}=\begin{pmatrix} \tbinom{t-1}{0} & \tbinom{t-1}{1} & \tbinom{t-1}{2} \end{pmatrix} \begin{pmatrix} 6 \\ 15 \\ 9 \end{pmatrix}$$

$$=6\tbinom{t-1}{0} + 15\tbinom{t-1}{1} + 9\tbinom{t-1}{2}=6\tbinom{t}{1} + 9\tbinom{t}{2}$$

这种二项式系数多项式结合朱世杰恒等式应用于等幂求和。

## 有关二项式系数的恒等式

### 关系式

阶乘公式能联系相邻的二项式系数，例如在$k$是正整数时，对任意$n$有：

- $$\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$$
- $$\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$$
- $$\binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}.$$

两个组合数相乘可作变换：

$\binom ni \binom im=\binom nm \binom {n-m}{i-m}$

### 一阶求和公式

- $$\sum_{r=0}^n \binom nr = 2^{n}$$
- $$\sum_{r=0}^k \binom {n+r-1}r = \binom {n+k}k$$
- $$\sum_{r=0}^{n-k} \frac {(-1)^r (n+1)}{k+r+1} \binom {n-k}r = \binom nk^{-1}$$
- $\sum_{r=0}^n \binom {dn}{dr}=\frac{1}{d}\sum_{r=1}^d (1+e^{\frac{2 \pi r i}{d}})^{dn}$
- $$\sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} - \binom {a+m}{m-1}$$

$$\binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + ... + \binom {a+n}{n} = \binom {a+n+1}{n}$$

- $F_n=\sum_{i=0}^{\infty} \binom {n-i}{i}$

$$F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n-i}{i-1}+\sum_{i=1}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{i}=F_{n+1}$$

- $$\sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1}$$

$$\binom {m}{a+1} + \binom ma + \binom {m+1}a ... + \binom na = \binom {n+1}{a+1}$$

### 二阶求和公式

- $$\sum_{r=0}^n {\binom nr}^2 = \binom {2n}n$$
- $\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}=\binom {r_1+r_2+n-1}{r_1+r_2-1}$

$$(1-x)^{-r_1} (1-x)^{-r_2}=(1-x)^{-r_1-r_2}$$

$$(1-x)^{-r_1} (1-x)^{-r_2}=(\sum_{n=0}^{\infty} \binom {r_1+n-1}{r_1-1} x^n)(\sum_{n=0}^{\infty} \binom {r_2+n-1}{r_2-1} x^n)=\sum_{n=0}^{\infty} (\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}) x^n$$

$$(1-x)^{-r_1-r_2}=\sum_{n=0}^{\infty} \binom {r_1+r_2+n-1}{r_1+r_2-1} x^n$$

- $$\sum_{i=0}^k \binom ni \binom m{k-i}=\binom {n+m}k$$

### 三阶求和公式

- $${\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k}$$

## 参考文献

- Benjamin, Arthur T.; Quinn, Jennifer (2003). Proofs that Really Count: The Art of Combinatorial Proof , Mathematical Association of America.

## 外部链接

- Calculation of Binomial Coefficient