二项式系数

二项式系数 (又称为组合数) 是计数组合中的一些计数结果. 给定自然数 $k\le n$, 二项式系数 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 定义为$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n(n-1)\cdots (n-k+1)}{k!},$$这是从 $n$ 个不同物品中选出 $k$ 个物品的方法总数. 换言之, 它是一个 $n$ 元集合的所有 $k$ 元子集的个数.

所有二项式系数可以排成一个三角形:$$\begin{array}{c}\text{1}\\ \text{1}\text{1}\\ \text{1}\text{2}\text{1}\\ \text{1}\text{3}\text{3}\text{1}\\ \text{1}\text{4}\text{6}\text{4}\text{1}\\ \text{1}\text{5}\text{10}\text{10}\text{5}\text{1}\\ \text{1}\text{6}\text{15}\text{20}\text{15}\text{6}\text{1}\\ \text{…}\text{…}\text{…}\text{…}\text{…}\text{…}\text{…}\text{…}\end{array}$$其中, 第 $n$ 行的数字是 $\left(\genfrac{}{}{0ex}{}{n-1}{0}\right),$ $\dots ,$ $\left(\genfrac{}{}{0ex}{}{n-1}{n-1}\right)$. 表中每个不在最边上的数都是其上方两个数之和. 这个三角形也称为杨辉三角或 Pascal 三角.

二项式系数得名于二项式定理, 该定理给出了展开式$$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}.$$从而, 二项式系数就是 $(x+y{)}^n$ 中各项的系数.

二项式系数也可以推广到 $n$ 不是自然数的情况. 此时的二项式系数不再有明显的组合意义, 但在合适的表述下, 二项式定理仍然成立.

1定义

定义 1.1. 设 $n$ 是复数, $k$ 是自然数. 则二项式系数 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 定义为$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n(n-1)\cdots (n-k+1)}{k!}.$$特别地, 若 $n$ 是自然数, 且 $k\le n$, 则$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}.$$

二项式系数 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 有时也记为 ${\mathrm{C}}_n^k$ 或 $\mathrm{C}(n,k)$.

2性质

基本性质

•	若 $n,k$ 都是自然数, 则 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 也是自然数.

•	若 $n,k$ 是自然数, 且 $n<k$, 则 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

•	二项式系数与降阶乘满足关系$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n^{\underline{k}}}{k!}.$$

•	对复数 $n$ 和自然数 $k$, 有恒等式$$\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right).$$

•	在二项式定理中取 $x=y=1$, 得到恒等式$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n.$$取 $x=-1$, $y=1$, 得到恒等式$$\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0.$$

初等数论性质

•	(Kummer 定理) 设 $p$ 是素数, $S_p(n)$ 表示自然数 $n$ 的 $p$ 进制表示中所有数码的和. 则对自然数 $k\le n$, 二项式系数的 $p$ 进赋值可以表示为$$v_p\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{S_p(k)+S_p(n-k)-S_p(n)}{p-1}.$$等式右边也等于 $p$ 进制下计算加法 $k+(n-k)$ 需要进位的次数.

•

(Lucas 定理) 设 $p$ 是素数, 自然数 $m\le n$ 的 $p$ 进制表示分别为 $n={\sum }_{l=0}^{\infty }{n}_l{p}^l,m={\sum }_{l=0}^{\infty }{m}_l{p}^l$, 其中 $n_l,m_l\in \{0,1,\dots ,p-1\}$, 则$$\left(\genfrac{}{}{0ex}{}{n}{m}\right)\equiv \prod _{l=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n_l}{m_l}\right)(\mathrm{mod}p),$$乘积中只有有限项不为 $1$.

渐进性质

•	对自然数 $k$ 和实数 $n\ge k$, 有估计$${\left(\frac{n}{k}\right)}^k\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)\le {\left(\frac{\mathrm{e}n}{k}\right)}^k.$$

•	当实数 $n\to +\infty$ 时, 若 $k=o(n^{3/4})$, 则有渐进性质$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\sim \frac{n^k}{k!}\exp (-\frac{k^2}{2n}-\frac{k^3}{6n^2}).$$

术语翻译

二项式系数 • 英文 binomial coefficient • 德文 Binomialkoeffizient (m) • 法文 coefficient binomial (m) • 日文 二項係数 (にこうけいすう) • 韩文 이항 계수 (二項係數)