热门问题
时间线
聊天
视角
二項式係數
来自维基百科,自由的百科全书
Remove ads
在數學上,二項式係數是二項式定理中各項的係數。一般而言,二項式係數由兩個非負整數和為參數決定,寫作 ,定義為 的多項式展開式中,項的係數,因此一定是非負整數。如果將二項式係數 寫成一行,再依照 順序由上往下排列,則構成帕斯卡三角形。

二項式係數常見於各數學領域中,尤其是組合數學。事實上,可以被理解為從個相異元素中取出個元素的方法數,所以 大多讀作「取」。二項式係數 的定義可以推廣至是複數的情況,而且仍然被稱為二項式係數。
Remove ads
歷史及記號
雖然二項式係數在西元10世紀就已經被發現(見帕斯卡三角形),但表達式 卻是到1826年才由安德烈亞斯·馮·厄廷格豪森首次始用[注 1]。最早探討二項式係數的論述是十世紀的 Halayudha寫的印度教典籍《賓伽羅的計量聖典》(chandaḥśāstra)。約1150年,印度數學家婆什迦羅第二於其著作《Lilavati》[注 2] 中給出一個簡單的描述。
二項式係數亦有不同的符號表達方式,包括:、、、、[注 3],其中的 C 代表組合(combinations)或選擇(choices)。很多計算機使用含有 C 的變種記號,使得算式只佔一行的空間,相同理由也發生在置換數 ,例如寫作 P(n, k)。
Remove ads
定義及概念
對於非負整數和,二項式係數定義為的多項式展開式(又稱為二項式係數的生成函數)中,項的係數,即
事實上,若、為交換環上的元素,則
此數的另一出處在組合數學,表達了從物中,不計較次序取物有多少方式,亦即從一元素集合中所能組成元素子集的數量。此定義與上述定義相同,理由如下:若將冪的個因數逐一標記為(從1至),則任一元素子集則建構成展式中的一個項,故此該單項的係數等如此種子集的數量。亦因此,就任何自然數和而言,亦為自然數。此外,二項式係數亦見於很多組合問題的解答中,如由個位元(如數字0或1)組成的所有序列中,其和為的數目為,又如算式,其中每一均為非負整數,則有種寫法。這些例子中,大部分可視作等同於點算個元素的組合的數量。
Remove ads
計算二項式係數
除展開二項式或點算組合數量之外,尚有多種方式計算的值。
以下遞歸公式可計算二項式係數:
其中特別指定:
此公式可由計算中的項,或點算集合的個元素組合中包含與不包含的數量得出。
顯然,如果,則。而且對所有,,故此上述遞歸公式可於此等情況下中斷。遞歸公式可用作建構帕斯卡三角形。
Remove ads
個別二項式係數可用以下公式計算:
上式中第一個分數的分子是一階乘冪。此公式可以二項式係數在計算組合數量的意義理解:分子為從個元素中取出個元素的序列之數量,當中包含同樣的元素但不同排列次序的序列。分母則計算同樣的個元素可有多少種排序方式。
Remove ads
二項式係數最簡潔的表達式是階乘:
其中「」是的階乘,此公式從上述乘數公式中分子分母各乘以取得,所以此公式中的分子分母有眾同共同因子。除非先行抵銷兩邊中的共同因子,否則以此公式進行計算時較率欠佳,尤因階乘的數值增長特快。惟此公式展示了二項式係數的對稱特性:
Remove ads
若將換成任意數值(負數、實數或複數),甚至是在任何能為正整數給出逆元素的交換環中的一元素,則二項式係數可籍乘數公式擴展[注 4]:
此定義能使二項式公式一般化(其中一單項為1),故仍能相稱地稱作二項式係數:
此公式對任何複數及,時成立,故此亦可視作的冪級數的恆等式,即係數為常數1,任意冪之級數定義,且在此定義下,對於冪的恆等式成立,例如
若是一非負整數,則所有的項為零,此無窮級數變成有限項的和,還原為二項式公式,但對於的其他值,包括負數和有理數,此級數為無窮級數。
Remove ads
帕斯卡三角形 (楊輝三角)

此式可以用於數學歸納法,以証明對於所有和均為自然數(等同於証明為所有個連續整數之積的因數),此特性並不易從公式(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
第橫行列出的項,其建構方法為在外邊填上1,然後將上一行中每兩個相鄰數相加的和填在其下,此方法可快速地計算二項式係數而不涉及乘法或分數,例如從第5橫行可馬上得出
在斜線上相鄰項的差就是上一斜線上的數值,此乃上述遞歸等式(3)的延伸意義。
Remove ads
組合數學和統計學
二項式係數是組合數學中的重要課題,因其可用於眾多常見的點算問題中,例如
Remove ads
以多項式表達二項式係數
就任就非負整數,可表達為一多項式除以:
此為帶有理數係數,變量是的多項式,可對任意實數或複數運算以得出二項式係數,此「廣義二項式係數」見於牛頓廣義二項式定理。
就任意,多項式可看成是惟一的次多項式滿足及.
其係數可以第一類斯特靈數表示,即:
Remove ads
在任何包含Q的域中,最多階的多項式有惟一的線性組合。係數是數列的第k差分,亦即: [注 5]
Remove ads
每一多項式在整數參數時均是整數值(可在上,用帕斯卡法則以歸納法証明)。故此,二項式係數多項式的整數線性組合亦為整數值。反之,(3.5)表達了任何整數值的多項式均是二項式係數多項式的整數線性組合。一般而言,對於一個特徵0域的任何子環,在內的多項式在整數參數時之值均在內當且僅當該多項式是一二項式係數多項式的-線性組合。
整數值多項式可表達作:
有關二項式係數的恆等式
階乘公式能聯繫相鄰的二項式係數,例如在是正整數時,對任意有:
兩個組合數相乘可作變換:
備註
- Lilavati 第6節,第4章(見Knuth (1997))。
- 見(Graham, Knuth & Patashnik 1994),其中就定義了,其他一般化形式包括考慮兩參數為實數或複數時以伽瑪函數為時定義,但此舉會令大部分二項式係數的恆等式失效,故未有被廣泛採用。然而,此方法替不等於零的參數下定義則可得出如Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997中那種好看的「帕斯卡風車」,但是卻會令帕斯卡法則在原點失效。
參考文獻
- Muir, Thomas. Note on Selected Combinations. Proceedings of the Royal Society of Edinburgh. 1902.
- 两个排列组合求和公式. [2014-01-05]. (原始內容存檔於2019-05-02).
- 趙麗棉 黃基廷. n次单位根在代数问题中的应用. 高等數學研究. 2010, (4) [2014-01-24]. (原始內容存檔於2019-05-02).
- 徐更生 何廷模. 斐波那契数列与组合数的一个关系及推广. 中學教研. 1991, (10) [2014-01-04]. (原始內容存檔於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.
參見
外部連結
- Calculation of Binomial Coefficient
- 本條目含有來自PlanetMath《Binomial Coefficient》的內容,版權遵守創用CC協議:署名-相同方式共享協議。
- 本條目含有來自PlanetMath《Bounds for binomial coefficients》的內容,版權遵守創用CC協議:署名-相同方式共享協議。
- 本條目含有來自PlanetMath《C(n,k) is an integer》的內容,版權遵守創用CC協議:署名-相同方式共享協議。
- 本條目含有來自PlanetMath《Generalized binomial coefficients》的內容,版權遵守創用CC協議:署名-相同方式共享協議。
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads