二项式系数

数学上,二项式系数二项式定理中各项的系数。一般而言,二项式系数由两个非负整数为参数决定,写作 ,定义为 的多项式展开式中,项的系数,因此一定是非负整数。如果将二项式系数 写成一行,再依照 顺序由上往下排列,则构成帕斯卡三角形

二项式系数可排列成帕斯卡三角形

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

历史及记号

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

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

定义及概念

对于非负整数  ,二项式系数 定义为 的多项式展开式中, 项的系数,即

 

事实上,若  交换环上的元素,则

 

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

计算二项式系数

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

递归公式

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

 

其中特别指定:

 
 

此公式可由计算 中的 项,或点算集合  个元素组合中包含 与不包含 的数量得出。

显然,如果 ,则 。而且对所有  ,故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形

乘数公式

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

 

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

阶乘公式

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

 

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

 

 

 

 

 

(1)

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

若将 换成任意数值(负数、实数或复数) ,甚至是在任何能为正整数给出逆元素交换环中的一元素,则二项式系数可籍乘数公式扩展[注 4]

 

此定义能使二项式公式一般化(其中一单项为1),故 仍能相称地称作二项式系数:

 

 

 

 

 

(2)

此公式对任何复数   时成立,故此亦可视作 幂级数的恒等式,即系数为常数1,任意幂之级数定义,且在此定义下,对于幂的恒等式成立,例如

 

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

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

 
帕斯卡三角形的第1000行,垂直排列,且以灰阶表示系数的十进制数位,向右对齐,故左边边界约是二项式系数的对数,图中可见数族形成一对数凹数列

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

 

 

 

 

 

(3)

此式可以用于数学归纳法,以证明 对于所有  均为自然数(等同于证明 为所有 个连续整数之积的因数),此特性并不易从公式(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: 21 35 35 21
8: 28 56 70 56 28

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

 

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

组合数学和统计学

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

  • 共有 种方式从 元素中选取 项。见组合
  • 共有 种方式从一个 元素集合中选取(容许重复选取) 元素建立多重集
  • 共有 字符串包含 个1和 个零。
  • 共有 个字符串包含 个1和 个零,且没有两个1相邻。[参 1]
  • 卡塔兰数 
  • 统计学中的二项式分布 
  • 贝兹曲线的公式。

以多项式表达二项式系数

就任就非负整数  可表达为一多项式除以 

 

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

就任意 ,多项式 可看成是惟一的 次多项式 满足  .

其系数可以第一类斯特灵数表示,即:

 

 导数可以对数微分计算:

 

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

在任何包含Q中,最多 阶的多项式有惟一的线性组合 。系数 是数列 k差分,亦即: [注 5]

 

 

 

 

 

(3.5)

整数值多项式

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

整数值多项式 可表达作:

 

  帕斯卡矩阵可算出:

 
 

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

有关二项式系数的恒等式

关系式

阶乘公式能联系相邻的二项式系数,例如在 是正整数时,对任意 有:

  •  
  •  
  •  

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

 [参 2]

一阶求和公式

  •  
  •  
  •  
  •  [参 3]
  •  
 
  •  [参 4]
 
  •  
 

二阶求和公式

  •  
  •  [参 5]
 
 
 
  •  

三阶求和公式

  •  

备注

  1. ^ Higham (1998)
  2. ^ Lilavati 第6节,第4章(见Knuth (1997))。
  3. ^ Shilov (1977)
  4. ^ 见(Graham,Knuth & Patashnik 1994),其中就 定义了 ,其他一般化形式包括考虑两参数为实数或复数时以伽玛函数 时定义 ,但此举会令大部分二项式系数的恒等式失效,故未有被广泛采用。然而,此方法替不等于零的参数下定义则可得出如Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997中那种好看的“帕斯卡风车”,但是却会令帕斯卡法则在原点失效。
  5. ^ 此可视作泰勒定理的离散形式,亦与牛顿多项式有关,此式的交错项之和可以Nörlund–Rice积分表示。

参考文献

  1. ^ Muir, Thomas. Note on Selected Combinations. Proceedings of the Royal Society of Edinburgh. 1902. 
  2. ^ 两个排列组合求和公式. [2014-01-05]. (原始内容存档于2019-05-02). 
  3. ^ 赵丽棉 黄基廷. n次单位根在代数问题中的应用. 高等数学研究. 2010, (4) [2014-01-24]. (原始内容存档于2019-05-02). 
  4. ^ 徐更生 何廷模. 斐波那契数列与组合数的一个关系及推广. 中学教研. 1991, (10) [2014-01-04]. (原始内容存档于2019-05-02). 
  5. ^ 伍启期. 组合数列求和. 佛山科学技术学院学报(自然科学版). 1996, (4) [2014-05-24]. (原始内容存档于2019-05-02). 
  • 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. 

参见

外部链接