二项式系数

在数学上，二项式系数是二项式定理中各项的系数。一般而言，二项式系数由两个非负整数 n 和 k 为参数决定，写作 ( n k ) {displaystyle {tbinom {n}{k}}} ，定义为 ( 1 + x ) n {displaystyle (1+x)^{n}} 的多项式展开式中， x k {displaystyle x^{k}} 项的系数，因此一定是非负整数。如果将二项式系数 ( n 0 ) , ( n 1 ) , … , ( n n ) {displaystyle {binom {n}{0}},{binom {n}{1}},dots ,{binom {n}{n}}} 写成一行，再依照 n = 0 , 1 , 2 , … {displaystyle n=0,1,2,dots } 顺序由上往下排列，则构成帕斯卡三角形。二项式系数常见于各数学领域中，尤其是组合数学。事实上， ( n k ) {displaystyle {tbinom {n}{k}}} 可以被理解为从 n {displaystyle n} 个相异元素中取出 k {displaystyle k} 个元素的方法数，所以 ( n k ) {displaystyle {tbinom {n}{k}}} 大多读作“ n {displaystyle n} 取 k {displaystyle k} ”。二项式系数 ( n k ) {displaystyle {tbinom {n}{k}}} 的定义可以推广至 n {displaystyle n} 是复数的情况，而且仍然被称为二项式系数。虽然二项式系数在公元10世纪就已经被发现（见帕斯卡三角形），但表达式 ( n k ) {displaystyle {tbinom {n}{k}}} 却是到1826年才由安德烈亚斯·冯·厄廷格豪森首次始用。最早探讨二项式系数的论述是十世纪的 Halayudha（英语：Halayudha）写的印度教典籍《Pingala的计量圣典》（chandaḥśāstra）。约1150年，印度数学家Bhaskaracharya于其著作《Lilavati》 中给出一个简单的描述。二项式系数亦有不同的符号表达方式，包括： C ( n , k ) {displaystyle C(n,k)} 、 n C k {displaystyle _{n}C_{k}} 、 n C k {displaystyle ^{n}C_{k}} 、 C n k {displaystyle C_{n}^{k}} 、 C k n {displaystyle C_{k}^{n}} ，其中的 C 代表组合（combinations）或选择（choices）。很多计算机使用含有 C 的变种记号，使得算式只占一行的空间，相同理由也发生在置换数 P k n {displaystyle P_{k}^{n}} ，例如写作 P(n, k)。对于非负整数 n {displaystyle n} 和 k {displaystyle k} ，二项式系数 ( n k ) {displaystyle {tbinom {n}{k}}} 定义为 ( 1 + x ) n {displaystyle (1+x)^{n}} 的多项式展开式中， x k {displaystyle x^{k}} 项的系数，即事实上，若 x {displaystyle x} 、 y {displaystyle y} 为交换环上的元素，则此数的另一出处在组合数学，表达了从 n {displaystyle n} 物中，不计较次序取 k {displaystyle k} 物有多少方式，亦即从一 n {displaystyle n} 元素集合中所能组成 k {displaystyle k} 元素子集的数量。此定义与上述定义相同，理由如下：若将幂 ( 1 + X ) n {displaystyle (1+X)^{n}} 的 n {displaystyle n} 个因数逐一标记为 i {displaystyle i} （从1至 n {displaystyle n} ），则任一 k {displaystyle k} 元素子集则建构成展式中的一个 X k {displaystyle X^{k}} 项，故此该单项的系数等如此种子集的数量。亦因此，就任何自然数 n {displaystyle n} 和 k {displaystyle k} 而言， ( n k ) {displaystyle {tbinom {n}{k}}} 亦为自然数。此外，二项式系数亦见于很多组合问题的解答中，如由 n {displaystyle n} 个位元（如数字0或1）组成的所有序列中，其和为 k {displaystyle k} 的数目为 ( n k ) {displaystyle {tbinom {n}{k}}} ，又如算式 k = a 1 + a 2 + ⋯ + a n {displaystyle k=a_{1}+a_{2}+cdots +a_{n}} ，其中每一 a i {displaystyle a_{i}} 均为非负整数，则有 ( n + k − 1 k ) {displaystyle {tbinom {n+k-1}{k}}} 种写法。这些例子中，大部分可视作等同于点算 k {displaystyle k} 个元素的组合的数量。除展开二项式或点算组合数量之外，尚有多种方式计算 ( n k ) {displaystyle {tbinom {n}{k}}} 的值。以下递归公式可计算二项式系数：其中特别指定：此公式可由计算 ( 1 + X ) n − 1 ( 1 + X ) {displaystyle (1+X)^{n-1}(1+X)} 中的 X k {displaystyle X^{k}} 项，或点算集合 { 1 , 2 , ⋯ , n } {displaystyle left{1,2,cdots ,nright}} 的 k {displaystyle k} 个元素组合中包含 n {displaystyle n} 与不包含 n {displaystyle n} 的数量得出。显然，如果 k > n {displaystyle k>n} ，则 ( n k ) = 0 {displaystyle {tbinom {n}{k}}=0} 。而且对所有 n {displaystyle n} ， ( n n ) = 1 {displaystyle {tbinom {n}{n}}=1} ，故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。个别二项式系数可用以下公式计算：上式中第一个分数的分子是一阶乘幂。此公式可以二项式系数在计算组合数量的意义理解：分子为从 n {displaystyle n} 个元素中取出 k {displaystyle k} 个元素的序列之数量，当中包含同样的元素但不同排列次序的序列。分母则计算同样的 k {displaystyle k} 个元素可有多少种排序方式。二项式系数最简洁的表达式是阶乘:其中“ n ! {displaystyle n!} ”是 n {displaystyle n} 的阶乘，此公式从上述乘数公式中分子分母各乘以 ( n − k ) ! {displaystyle (n-k)!} 取得，所以此公式中的分子分母有众同共同因子。除非先行抵销两边中的共同因子，否则以此公式进行计算时较率欠佳，尤因阶乘的数值增长特快。惟此公式展示了二项式系数的对称特性：( n k ) = ( n n − k ) for    0 ≤ k ≤ n . {displaystyle {binom {n}{k}}={binom {n}{n-k}}quad {mbox{for }} 0leq kleq n.}(1)若将 n {displaystyle n} 换成任意数值（负数、实数或复数） α {displaystyle alpha } ，甚至是在任何能为正整数给出逆元素的交换环中的一元素，则二项式系数可籍乘数公式扩展：此定义能使二项式公式一般化（其中一单项为1），故 ( α k ) {displaystyle {tbinom {alpha }{k}}} 仍能相称地称作二项式系数：( 1 + X ) α = ∑ k = 0 ∞ ( α k ) X k . {displaystyle (1+X)^{alpha }=sum _{k=0}^{infty }{alpha choose k}X^{k}.}(2)此公式对任何复数 α {displaystyle alpha } 及 X {displaystyle X} ， | X | < 1 {displaystyle leftvert Xrightvert <1} 时成立，故此亦可视作 X {displaystyle X} 的幂级数的恒等式，即系数为常数1，任意幂之级数定义，且在此定义下，对于幂的恒等式成立，例如若 α {displaystyle alpha } 是一非负整数 n {displaystyle n} ，则所有 k > n {displaystyle k>n} 的项为零，此无穷级数变成有限项的和，还原为二项式公式，但对于 α {displaystyle alpha } 的其他值，包括负数和有理数，此级数为无穷级数。帕斯卡法则是一重要的递归等式：( n k ) + ( n k + 1 ) = ( n + 1 k + 1 ) , {displaystyle {n choose k}+{n choose k+1}={n+1 choose k+1},}(3)此式可以用于数学归纳法，以证明 ( n k ) {displaystyle {tbinom {n}{k}}} 对于所有 n {displaystyle n} 和 k {displaystyle k} 均为自然数（等同于证明 k ! {displaystyle k!} 为所有 k {displaystyle k} 个连续整数之积的因数），此特性并不易从公式(1)中得出。帕斯卡法则建构出帕斯卡三角形:第 n {displaystyle n} 横行列出 ( n k ) {displaystyle {tbinom {n}{k}}} 的 k = 0 , … , n {displaystyle k=0,ldots ,n} 项，其建构方法为在外边填上1，然后将上一行中每两个相邻数相加的和填在其下，此方法可快速地计算二项式系数而不涉及乘法或分数，例如从第5横行可马上得出在斜线上相邻项的差就是上一斜线上的数值，此乃上述递归等式(3)的延伸意义。二项式系数是组合数学中的重要课题，因其可用于众多常见的点算问题中，例如就任就非负整数 k {displaystyle k} ， ( t k ) {displaystyle scriptstyle {binom {t}{k}}} 可表达为一多项式除以 k ! {displaystyle k!} ：此为带有理数系数，变量是 t {displaystyle t} 的多项式，可对任意实数或复数 t {displaystyle t} 运算以得出二项式系数，此“广义二项式系数”见于牛顿广义二项式定理。就任意 k {displaystyle k} ，多项式 ( t k ) {displaystyle {tbinom {t}{k}}} 可看成是惟一的 k {displaystyle k} 次多项式 p ( t ) {displaystyle p(t)} 满足 p ( 0 ) = p ( 1 ) = … = p ( k − 1 ) = 0 {displaystyle p(0)=p(1)=ldots =p(k-1)=0} 及 p ( k ) = 1 {displaystyle p(k)=1} .其系数可以第一类斯特灵数表示，即：( t k ) {displaystyle {tbinom {t}{k}}} 之导数可以对数微分计算：在任何包含Q的域中，最多 d {displaystyle d} 阶的多项式有惟一的线性组合 ∑ k = 0 d a k ( t k ) {displaystyle sum _{k=0}^{d}a_{k}{binom {t}{k}}} 。系数 a k {displaystyle a_{k}} 是数列 p ( 0 ) , p ( 1 ) , … , p ( k ) {displaystyle p(0),p(1),ldots ,p(k)} 的第k差分，亦即：a k = ∑ i = 0 k ( − 1 ) k − i ( k i ) p ( i ) . {displaystyle a_{k}=sum _{i=0}^{k}(-1)^{k-i}{binom {k}{i}}p(i).}(3.5)每一多项式 ( t k ) {displaystyle {tbinom {t}{k}}} 在整数参数时均是整数值（可在 k {displaystyle k} 上，用帕斯卡法则以归纳法证明）。故此，二项式系数多项式的整数线性组合亦为整数值。反之，(3.5)表达了任何整数值的多项式均是二项式系数多项式的整数线性组合。一般而言，对于一个特征0域 k {displaystyle k} 的任何子环 R {displaystyle R} ，在 K [ t ] {displaystyle K} 内的多项式在整数参数时之值均在 R {displaystyle R} 内当且仅当该多项式是一二项式系数多项式的 R {displaystyle R} -线性组合。整数值多项式 3 t ( 3 t + 1 ) 2 {displaystyle {frac {3t(3t+1)}{2}}} 可表达作：从 t = 1 , 2 , 3 {displaystyle t=1,2,3} 时 3 t ( 3 t + 1 ) 2 = 6 , 21 , 45 {displaystyle {frac {3t(3t+1)}{2}}=6,21,45} 用帕斯卡矩阵的逆可算出：这种二项式系数多项式结合朱世杰恒等式应用于等幂求和。阶乘公式能联系相邻的二项式系数，例如在 k {displaystyle k} 是正整数时，对任意 n {displaystyle n} 有：两个组合数相乘可作变换：本条目含有来自PlanetMath《Binomial Coefficient》的内容，版权遵守知识共享协议：署名-相同方式共享协议。本条目含有来自PlanetMath《Bounds for binomial coefficients》的内容，版权遵守知识共享协议：署名-相同方式共享协议。本条目含有来自PlanetMath《Proof that C(n,k) is an integer》的内容，版权遵守知识共享协议：署名-相同方式共享协议。本条目含有来自PlanetMath《Generalized binomial coefficients》的内容，版权遵守知识共享协议：署名-相同方式共享协议。