主題
Search

二項式係數

下載 Mathematica Notebook下載 Wolfram Notebook

二項式係數 (n; k) 是從 n 個可能性中選取 k 個無序結果的方式數，也稱為組合或組合數。符號 _nC_k 和 (n; k) 用於表示二項式係數，有時讀作“n 選擇 k”。

(n; k) 因此給出了從一組 n 個不同專案中可能存在的 k-子集 的數量。例如，{1,2,3,4} 的 2-子集是六對 {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, 和 {3,4}，因此 (4; 2)=6。此外，從原點 (0,0) 到點 (a,b) 的 格路路徑 的數量是二項式係數 (a+b; a) (Hilton and Pedersen 1991)。

對於 非負整數 n 和 k，且滿足 0<=k<=n，二項式係數值由下式給出

(n; k)=(n!)/(k!(n-k)!)
(1)

(Graham et al. 1989, p.157)，其中 z! 表示階乘。對於遞增的 n，按行填充 k=0, 1, ..., n 的值，得到帕斯卡三角形。

將階乘寫為伽瑪函式 z!=Gamma(z+1) 允許將二項式係數推廣到非整數引數（包括複數 x 和 y），形式為

(x; y)=(Gamma(x+1))/(Gamma(y+1)Gamma(x-y+1)).
(2)

羅馬係數 (Roman 1992, Loeb 1995) 是二項式係數的推廣。每當定義二項式係數時，羅馬係數都與之一致。然而，羅馬係數是為二項式係數未定義的值定義的。

對於 非負整數 y 的二項式係數給出了一個關於 x 的多項式

(x; y)=((x)_y)/(y!)
(3)
=(x(x-1)(x-2)...(x-y+1))/(y(y-1)...2·1),
(4)

其中 (x)_y 是一個 泊松-丘哈默符號。這些有理係數有時被稱為“廣義二項式係數”。

使用伽瑪函式對稱公式

(Gamma(s-a+1))/(Gamma(s-b+1))=(-1)^(b-a)(Gamma(b-s))/(Gamma(a-s))
(5)

對於整數 a, b 和複數 s，此定義可以擴充套件到負整數引數，使其在所有整數引數處連續，以及在所有複數引數處連續，除了負整數 x 和非整數 y 的情況，在這種情況下它是無限的 (Kronenburg 2011)。這個定義，由下式給出

(n; k)={(-1)^k(-n+k-1; k) for k>=0; (-1)^(n-k)(-k-1; n-k) for k<=n; 0 otherwise
(6)

對於負整數 n 和整數 k，與二項式定理以及組合恆等式一致，但有一些特殊例外 (Kronenburg 2011)。

二項式係數在 Wolfram 語言 中實現為Binomial[n, k]，它遵循版本 8 中開始的上述約定。變體 [n,m] 保留了帕斯卡恆等式

[n,k]=[n-1,k]+[n-1,k-1],
(7)

因此對於負整數 n 值不同，在 Wolfram 語言 中實現為PascalBinomial[n, k]。

BinomialCoefficient

在 xy 平面上繪製二項式係數（Fowler 1996）給出了上面所示的漂亮圖表，對於 負數 x 和 y，它有一個非常複雜的圖形，因此很難使用標準繪圖程式渲染。

對於正整數 n，二項式定理給出

(x+a)^n=sum_(k=0)^n(n; k)x^ka^(n-k).
(8)

這個恆等式的有限差分模擬被稱為 朱-範德蒙恆等式。類似的公式對於負整數也成立，

(x+a)^(-n)=sum_(k=0)^infty(-n; k)x^ka^(-n-k).
(9)

有許多優雅的二項式和。

二項式係數滿足以下恆等式

(n; 0)=(n; n)=1
(10)
(n; k)=(n; n-k)
(11)
(n; k+1)=(n; k)(n-k)/(k+1)
(12)
(n+1; k)=(n; k)+(n; k-1).
(13)

二項式係數的乘積由下式給出

product_(k=0)^n(n; k)=(H^2(n))/((n!)^(n+1)),
(14)

其中 H(n) 是一個 超階乘，n! 是一個 階乘。

正如庫默在 1852 年表明的那樣，如果 p^k 是素數 p 的最大冪，它能整除 (m+n; m)，其中 m 和 n 是非負整數，那麼 k 是在以 p 為基數將 m 加到 n 時發生的進位數 (Graham et al. 1989, Exercise 5.36, p. 245; Ribenboim 1989; Vardi 1991, p. 68)。庫默的結果也可以用另一種形式表示：素數 p 除以 (n; m) 的指數由整數 j>=0 的數量給出，對於這些整數

frac(m/p^j)>frac(n/p^j),
(15)

其中 frac(x) 表示 x 的小數部分。這個不等式可以簡化為對指數和 sum_(n)Lambda(n)e(x/n) 的研究，其中 Lambda(n) 是 芒戈爾特函式。Jutila (1973, 1974) 給出了這些和的估計，但 Granville 和 Ramare (1996) 進行了最新的改進。

R. W. Gosper 表明

f(n)=(n-1; 1/2(n-1))=(-1)^((n-1)/2) (mod n)
(16)

對於所有素數都成立，並推測它僅對素數成立。當 Skiena (1990) 發現它也適用於合數 n=3×11×179 時，這個推測被推翻。Vardi (1991, p. 63) 隨後表明，當 p 是維費裡希素數 時，n=p^2 是一個解，並且如果 n=p^k 且 k>3 是一個解，那麼 n=p^(k-1) 也是一個解。這使他能夠證明，對於合數 n<1.3×10^7，唯一的解是 5907、1093^2 和 3511^2，其中 1093 和 3511 是 維費裡希素數。

考慮二項式係數 f(n)=(2n-1; n)，前幾個係數為 1, 3, 10, 35, 126, ... (OEIS A001700)。生成函式為

1/2[1/(sqrt(1-4x))-1]=x+3x^2+10x^3+35x^4+....
(17)

這些數字僅對於 n=2, 3, 4, 6, 9, 10, 12, 36, ... (OEIS A046097) 是無平方因子的，目前尚不清楚是否有其他值。事實證明，除非 n 屬於 2-自動集 S_2，否則 f(n) 可被 4 整除，而 2-自動集 S_2 恰好是 二進位制 表示最多包含兩個 1 的數字集合：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, ... (OEIS A048645)。類似地，除非 n 屬於 3-自動集 S_3，否則 f(n) 可被 9 整除，3-自動集 S_3 由數字 n 組成，對於這些數字，三進位制 中 2n 的表示完全由 0 和 2 組成（除非可能有一對相鄰的 1）。S_3 的初始元素是 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 13, 18, 19, 21, 22, 27, ... (OEIS A051382)。如果 f(n) 是無平方因子的，那麼 n 必須屬於 S=S_2 intersection S_3。很可能 S 是有窮的，但尚無證明。現在，大於 4 和 9 的平方數也可能整除 f(n)，但僅透過排除這兩個，對於 n 來說，n<=2^(64) 的唯一可能值是 1, 2, 3, 4, 6, 9, 10, 12, 18, 33, 34, 36, 40, 64, 66, 192, 256, 264, 272, 513, 514, 516, 576 768, 1026, 1056, 2304, 16392, 65664, 81920, 532480 和 545259520。除了最後一個，所有這些都已檢查過，證實對於 n<=545259520，沒有其他 n 使 f(n) 是無平方因子的。

Erdős 表明，對於 3<=k<=n/2，二項式係數 (n; k) 是一個 整數 的冪，僅在 (50; 3)=140^2 一種情況下成立 (Le Lionnais 1983, p. 48)。當 a^2 是三角形數時，二項式係數 T_(n-1)=(n; 2) 是平方數 a^2，這發生在 a=1, 6, 35, 204, 1189, 6930, ... (OEIS A001109) 時。這些 a 值對應的 n=2, 9, 50, 289, 1682, 9801, ... (OEIS A052436) 值。

二項式係數 (n; |_n/2_|) 被稱為中心二項式係數，其中 |_x_| 是向下取整函式，儘管係數子集 (2n; n) 有時也使用這個名稱。Erdős 和 Graham (1980, p. 71) 推測，對於 n>4，中心二項式係數 (2n; n) 永遠不是無平方因子的，這有時被稱為埃爾德什無平方因子猜想。薩克孜定理 (Sárkőzy 1985) 提供了一個部分解，指出對於所有足夠大的 n>=n_0，二項式係數 (2n; n) 永遠不是無平方因子的 (Vardi 1991)。Granville 和 Ramare (1996) 證明了唯一的無平方因子值是 n=2 和 4。Sander (1992) 隨後表明，只要 d 不是“太大”，對於足夠大的 n，(2n+/-d; n) 也永遠不是無平方因子的。

對於 p、q 和 r 個不同的素數，函式 (◇) 滿足

f(pqr)f(p)f(q)f(r)=f(pq)f(pr)f(qr) (mod pqr)
(18)

(Vardi 1991, p. 66)。

大多數 n>=2k 的二項式係數 (n; k) 都有一個素因子 p<=n/k，Lacampagne et al. (1993) 推測這個不等式對於所有 n>17.125k 都成立，或者更強地說，任何這樣的二項式係數的最小素因子為 p<=n/k 或 p<=17，但有例外 (62; 6), (959; 56), (474; 66), (284; 28)，對於這些例外，p=19, 19, 23, 29 (Guy 1994, p. 84)。

二項式係數 (m; n) (mod 2) 可以使用異或運算 n XOR m 計算，使得 mod 2 的帕斯卡三角形非常容易構造。

Sondow (2005) 和 Sondow 與 Zudilin (2006) 注意到不等式

1/(4rm)[((r+1)^(r+1))/(r^r)]^m<((r+1)m; m)<[((r+1)^(r+1))/(r^r)]^m
(19)

對於 m 為正整數，r>=1 為實數。

另請參閱

Apéry 數, 平衡二項式係數, 投票問題, 伯努利三角形, 二項式, 二項分佈, 二項式恆等式, 二項式和, 二項式定理, 中心二項式係數, 選擇, 聖誕襪定理, 朱-範德蒙恆等式, 組合, 虧量, 埃爾德什無平方因子猜想, 例外二項式係數, 階乘, Fibonomial 係數, 伽瑪函式, 良好二項式係數, k-子集, 國王問題, Klee 恆等式, Lah 數, 多重選擇, 多項式係數, 帕斯卡公式, 排列, q-二項式係數, 羅馬係數, 薩克孜定理, Stanley 恆等式, 大衛之星定理, Stolarsky-Harborth 常數, Strehl 恆等式, Székely 恆等式, Wolstenholme 定理 在 課堂中探索此主題

相關 Wolfram 網站

http://functions.wolfram.com/GammaBetaErf/Binomial/

使用 探索

參考文獻

Abramowitz, M. 和 Stegun, I. A. (Eds.). "二項式係數." §24.1.1 in 數學函式手冊，包含公式、圖形和數學表格，第 9 次印刷。 New York: Dover, pp. 10, 256, 和 822-823, 1972.Comtet, L. 高階組合數學：有限與無限展開的藝術，修訂和擴充版。 Dordrecht, Netherlands: Reidel, 1974.Conway, J. H. 和 Guy, R. K. In 數字之書。 New York: Springer-Verlag, pp. 66-74, 1996.Erdős, P.; Graham, R. L.; Nathanson, M. B.; 和 Jia, X. 組合數論中的新舊問題和結果。 New York: Springer-Verlag, 1998.Erdős, P.; Lacampagne, C. B.; 和 Selfridge, J. L. "二項式係數的最小素因子估計." Math. Comput. 61, 215-224, 1993.Feller, W. "二項式係數" 和 "涉及二項式係數的問題和恆等式." §2.8 和 2.12 in 機率論及其應用導論，第 1 卷，第 3 版。 New York: Wiley, pp. 48-50 和 61-64, 1968.Fowler, D. "二項式係數函式." Amer. Math. Monthly 103, 1-17, 1996.Graham, R. L.; Knuth, D. E.; 和 Patashnik, O. "二項式係數." Ch. 5 in 具體數學：計算機科學基礎。 Reading, MA: Addison-Wesley, pp. 153-242, 1989.Granville, A. "二項式係數的算術性質。I. 模素數冪的二項式係數." In 有機數學。1995 年 12 月 12-14 日在 BC 省伯納比舉行的研討會論文集 (Ed. J. Borwein, P. Borwein, L. Jörgenson 和 R. Corless). Providence, RI: Amer. Math. Soc., pp. 253-276, 1997.Granville, A. "二項式係數的算術性質." http://www.dms.umontreal.ca/~andrew/Binomial/.Granville, A. 和 Ramaré, O. "指數和的顯式界限和無平方因子二項式係數的稀缺性." Mathematika 43, 73-107, 1996.Guy, R. K. "二項式係數", "二項式係數的最大除數", 和 "與 zeta-函式相關的級數." §B31, B33, 和 F17 in 數論中未解決的問題，第 2 版。 New York: Springer-Verlag, pp. 84-85, 87-89, 和 257-258, 1994.Harborth, H. "奇數二項式係數的數量." Not. Amer. Math. Soc. 23, 4, 1976.Hilton, P. 和 Pedersen, J. "卡特蘭數、它們的推廣及其應用." Math. Intel. 13, 64-75, 1991.Jutila, M. "具有大素因子的數." J. Indian Math. Soc. 37, 43-53, 1973.Jutila, M. "具有大素因子的數. II." J. Indian Math. Soc. 38, 125-130, 1974.Kronenburg, M. "負引數的二項式係數." 2011 年 5 月 18 日. http://arxiv.org/abs/1105.3689/.Le Lionnais, F. 卓越的數字。 Paris: Hermann, 1983.Loeb, D. E. "二項式係數的推廣." 1995 年 2 月 9 日. http://arxiv.org/abs/math/9502218.Ogilvy, C. S. "二項式係數." Amer. Math. Monthly 57, 551-552, 1950.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; 和 Vetterling, W. T. "伽瑪函式、貝塔函式、階乘、二項式係數." §6.1 in FORTRAN 數值食譜：科學計算的藝術，第 2 版。 Cambridge, England: Cambridge University Press, pp. 206-209, 1992.Prudnikov, A. P.; Marichev, O. I.; 和 Brychkow, Yu. A. 公式 41 in 積分與級數，第 1 卷：初等函式。 Newark, NJ: Gordon & Breach, p. 611, 1986.Ribenboim, P. 素數記錄新書。 New York: Springer-Verlag, pp. 23-24, 1989.Riordan, J. "逆關係和組合恆等式." Amer. Math. Monthly 71, 485-498, 1964.Roman, S. "對數二項式公式." Amer. Math. Monthly 99, 641-648, 1992.Sander, J. W. "二項式係數的素因子." Bull. London Math. Soc. 24, 140-142, 1992.Sárkőzy, A. "關於二項式係數的除數，I." J. Number Th. 20, 70-80, 1985.Skiena, S. 實現離散數學：Mathematica 中的組合數學和圖論。 Reading, MA: Addison-Wesley, p. 262, 1990.Sloane, N. J. A. 序列 A001109/M4217, A001700/M2848, A046097, A048645, A051382, 和 A052436, in "整數序列線上百科全書."Sondow, J. "問題 11132." Amer. Math. Monthly 112, 180, 2005.Sondow, J. 和 Zudilin, W. "尤拉常數、q-對數以及 Ramanujan 和 Gosper 的公式." Ramanujan J. 12, 225-244, 2006.Spanier, J. 和 Oldham, K. B. "二項式係數 (nu; m)." Ch. 6 in 函式圖集。 Washington, DC: Hemisphere, pp. 43-52, 1987.Sved, M. "計數和重新計數." Math. Intel. 5, 21-26, 1983.Vardi, I. "二項式係數的應用", "二項式係數", "一類解", "計算二項式係數", 和 "模整數的二項式." §2.2, 4.1, 4.2, 4.3, 和 4.4 in Mathematica 計算娛樂。 Redwood City, CA: Addison-Wesley, pp. 25-28 和 63-71, 1991.Wolfram, S. "二項式係數的幾何." Amer. Math. Monthly 91, 566-571, 1984.

參考內容

二項式係數

請引用為

Weisstein, Eric W. "二項式係數." 來自 Web 資源。 https://mathworld.tw/BinomialCoefficient.html

主題分類