二项式系数

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

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

对于非负整数${\displaystyle n}$ 和${\displaystyle k}$ ，二项式系数${\displaystyle {\tbinom {n}{k}}}$ 定义为${\displaystyle (1+x)^{n}}$ 的多项式展开式中，${\displaystyle x^{k}}$ 项的系数，即

${\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0}}+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}}$ 

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

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

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

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

递归公式

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

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

其中特别指定：

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

${\displaystyle {\binom {0}{k}}=0\quad \forall k\in \mathbb {N} .}$ 

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

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

乘数公式

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

${\displaystyle {\binom {n}{k}}={\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}},}$ 

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

阶乘公式

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

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

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

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

(1)

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

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

${\displaystyle {\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}}\quad {\mbox{for }}k\in \mathbb {N} {\mbox{ and arbitrary }}\alpha .}$ 

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

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

(2)

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

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

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

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

${\displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1},}$

(3)

此式可以用于数学归纳法，以证明${\displaystyle {\tbinom {n}{k}}}$ 对于所有${\displaystyle n}$ 和${\displaystyle k}$ 均为自然数（等同于证明${\displaystyle k!}$ 为所有${\displaystyle 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

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

${\displaystyle (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)的延伸意义。

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

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

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

${\displaystyle {\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)}};\,\!}$ 

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

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

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

${\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}{\frac {s_{k,i}}{k!}}t^{i}}$ 

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

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

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

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

${\displaystyle a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).}$

(3.5)

整数值多项式

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

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

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

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

${\displaystyle {\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}}}$ 

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

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

关系式

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

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

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

${\displaystyle {\binom {n}{i}}{\binom {i}{m}}={\binom {n}{m}}{\binom {n-m}{i-m}}}$ ^{[参 2]}

一阶求和公式

• ${\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}=2^{n}}$ 
• ${\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}}$ 
• ${\displaystyle \sum _{r=0}^{n-k}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {n-k}{r}}={\binom {n}{k}}^{-1}}$ 
• ${\displaystyle \sum _{r=0}^{n}{\binom {dn}{dr}}={\frac {1}{d}}\sum _{r=1}^{d}(1+e^{\frac {2\pi ri}{d}})^{dn}}$ ^{[参 3]}

• ${\displaystyle \sum _{i=m}^{n}{\binom {a+i}{i}}={\binom {a+n+1}{n}}-{\binom {a+m}{m-1}}}$ 

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

• ${\displaystyle F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}}$ ^{[参 4]}

${\displaystyle 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}}$ 

• ${\displaystyle \sum _{i=m}^{n}{\binom {i}{a}}={\binom {n+1}{a+1}}-{\binom {m}{a+1}}}$ 

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

二阶求和公式

• ${\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}}$ 

• ${\displaystyle \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}}}$ ^{[参 5]}

${\displaystyle (1-x)^{-r_{1}}(1-x)^{-r_{2}}=(1-x)^{-r_{1}-r_{2}}}$ 

${\displaystyle (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}}$ 

${\displaystyle (1-x)^{-r_{1}-r_{2}}=\sum _{n=0}^{\infty }{\binom {r_{1}+r_{2}+n-1}{r_{1}+r_{2}-1}}x^{n}}$ 

• ${\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}={\binom {n+m}{k}}}$ 

三阶求和公式

• ${\displaystyle {\binom {n+k}{k}}^{2}=\sum _{j=0}^{k}{\binom {k}{j}}^{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.
• Bryant, Victor. Aspects of combinatorics. Cambridge University Press. 1993. ISBN 0521419743. 
• Flum, Jörg; Grohe, Martin. Parameterized Complexity Theory. Springer. 2006 [2011-07-28]. ISBN 978-3-540-29952-3. （原始内容存档于2007-11-18）. 
• Fowler, David. The Binomial Coefficient Function. The American Mathematical Monthly (Mathematical Association of America). January 1996, 103 (1): 1–17. JSTOR 2975209. doi:10.2307/2975209. 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics Second. Addison-Wesley. 1994: 153–256. ISBN 0-201-55802-5. 
• Higham, Nicholas J. Handbook of writing for the mathematical sciences. SIAM. 1998: 25. ISBN 0898714206. 
• Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms Third. Addison-Wesley. 1997: 52–74. ISBN 0-201-89683-4. 
• Singmaster, David. Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients. J. London Math. Soc. (2). 1974, 8 (3): 555–560. doi:10.1112/jlms/s2-8.3.555. 
• Shilov, G. E. Linear algebra. Dover Publications. 1977. ISBN 9780486635187. 

• 组合

• Calculation of Binomial Coefficient
• 本条目含有来自PlanetMath《Binomial Coefficient》的内容，版权遵守知识共享协议：署名-相同方式共享协议。
• 本条目含有来自PlanetMath《Bounds for binomial coefficients》的内容，版权遵守知识共享协议：署名-相同方式共享协议。
• 本条目含有来自PlanetMath《C(n,k) is an integer》的内容，版权遵守知识共享协议：署名-相同方式共享协议。
• 本条目含有来自PlanetMath《Generalized binomial coefficients》的内容，版权遵守知识共享协议：署名-相同方式共享协议。