二項係数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/07/13 01:12 UTC 版)
この整数族は代数学のみならず数学の他の多くの分野、特に組合せ論において現れる。n元-集合から k個の元を(その順番を無視して)選ぶ方法が (n
k) 通りである。二項係数の性質を用いて、記号 (n
k) の意味を、もともとの n および k が k ≤ n なる非負整数であった場合を超えて拡張することが可能で、そのような場合もやはり二項係数と称する。
歴史と記法
二項係数に関して詳しく知られた最も初期の議論は10世紀ごろハラユーダが古代サンスクリット語で書いた "Pingala's Chandaḥśāstra" である。1150年ごろには、インドの数学者バースカラ2世が著書 "Lilavati" で二項係数について詳しく述べている[1]。
記号 (n
k) はアンドレアス・フォン・エッチンクハウゼンが1826年に導入したものである[2]。
そのほかの記法として C(n, k), nCk, nCk, Ck
n, Cn
k[3], Cn,k, (n¦m) などがあり、何れも文字 C は組合せ (combination) や選択 (choice) を表している。
定義と解釈
自然数(0 も含める)n および k に対し、二項係数 (n
k) は二項冪 (1 + X)n の展開における Xk の項の係数として定義できる。同係数は(k ≤ nのとき)二項公式
に現れるため「二項係数」の名がある(この式自体は環の互いに可換な任意の元 x, y に対して成り立つ)。
組合せ論においてもまたこの数は、n 個の対象から k 個選ぶ選び方の総数、より形式的には n元-集合の k元-部分集合(k-項組合せ)の総数として現れる。この数が先に述べた係数と一致することは、後で述べるこの数の計算法の何れとも独立に示すことができる。実際、冪 (1 + X)n における n 個の因子の各々において、一時的に X に対し 1 ≤ i ≤ n なる添字 i をそれぞれ付けて区別しておくと、k 個の添字からなる部分集合をひとつ選ぶ毎に展開後の Xk への寄与が 1 だけあるから、この項の係数はそのような部分集合の選び方の数に一致する。このことは特に (n
k) が任意の自然数 n, k に対して自然数となることも示している。二項係数の組合せ論的解釈(二項係数展開が答えを与える数え上げ問題)は多く存在する。例えば、各位の和が k に一致する n桁のビット(つまり各位の数は 0 か 1)の語(文字列)の総数は (n
k) で与えられる。また、各 ai が非負整数であるものとして k = a1 + a2 + … + an と書く方法の総数は (n + k − 1
n − 1) 通りである。これら解釈のほとんどは、k-組合せを数えることに同値であることが容易に示される。
二項係数の値の計算
(n
k) の値を、実際に二項冪を展開したり k-組合せを数え上げたりせずに、計算する方法はいくつかある。
漸化式
一つは、n, k を 1 ≤ k ≤ n − 1 なる自然数として、純加法的な漸化式
を初期条件「任意の n ≥ 0 に対し (n
0) = (n
n) = 1」の下で用いることである。
この漸化式自体は、集合 {1, 2, 3, …, n} において以下のように場合を分けて k元-集合を数えることで得られる。特定の元に注目し、ここではそれを “i” とする。
- (a) 特定の元 i を含む k 個の元を集める。この場合、各集まりは既に i があることは仮定しているから、残りの k − 1 個の元を i を除く n − 1 元の中から特定すればよい。
- (b) 特定の元 i を全く含まない k 個の元を集める。この場合、i を除く n − 1 個の元から k 個を選ぶことに他ならない。
この二者で与えられた n 個の元から得られるすべての k-組合せが数え上げられているので所期の結果を得る。
あるいはまた、(1 + X)n = (1 + X)n−1(1 + X) の両辺における Xk への寄与を見ることでもこの漸化式は得られる。(1 + X)n において Xn+1 や X−1 の項は存在しない(あるいは係数が零である)から、二項係数の定義を上記の境界を越えて延長して、(n
k) = 0 (k > n ∨ k < 0) とすることもできる。
この漸化式はパスカルの三角形を描くのにも利用できる。
乗法表示
個々の二項係数をより効果的に計算するには
で与えられる式を用いる。一つ目の分数の分子に現れる nk は下降階乗冪である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は n 個の対象からなる集合から選ぶ順番を考慮して相異なる k 個の対象を取り出す方法の総数であり、分母は同じ k-組合せを与える相異なる並びの数を数えるものである。
階乗表示
最後に、計算論的には不利だが、短く書けるのでしばしば証明や導出に用いられるよく知られた階乗函数を用いた式は
で与えられる。ここに n! は n の階乗である。この式は上記の乗法表示式に、分子分母に対して (n − k)! を掛けることで得られる(その結果、この式において分母と分子は多くの共通因数を持つことになる)。(特に階乗は非常に速く増加するから)この式を(k が小さく n が大きい場合に)実際の数値計算に用いることは(先に共通因数を約分しない限り)実用的でない。この式は上記の乗法表示よりは二項係数が対称性
を持つことを見るのに適している(二項係数の定義から対称性をもつことは分かる)。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば
と書ける。
一般化および二項級数
乗法表示を用いれば、n を任意の数 α(負の整数、実数、複素数、……)あるいは任意の整数が可逆となるような可換環の元に取り換えて、
により二項係数の定義を拡張することができる[注 1]。この定義により、二項定理(の一方の変数を 1 としたもの)も一般化して
と書くことができる。故にこの場合も (α
k) を二項係数と呼ぶことは正当化される。この等式は任意の複素数 α と |X| < 1 なる X に対して有効である。これはまた X を不定元とする形式冪級数の等式としても解釈でき、それは実際に定数係数 1 を持つ級数の任意の冪の定義として機能する。この定義を用いるポイントは、冪乗として満足することが期待される全ての恒等式(指数法則)、特に
が満足されることである。α が非負整数 n のとき、k > n なる全ての項は零であり、上記の無限級数は有限和となり、したがってもともとの二項定理が再び得られる。しかし α がそれ以外の値ならば、負の整数や有理数の場合も含めて、上記の級数は実際に無限和になる。
注釈
- ^ (Graham, Knuth & Patashnik 1994) を参照、これはまた k < 0 のとき (n
k) = 0 とする。別の一般化としてガンマ函数を用いて k < 0 のとき (n
k) に非零な値を割り当てることもできるが、それは多くの二項係数に関する公式を満足せず、これを定義として広汎に適用することはできない。そのように非零値を選ぶものの一つとして、見た目の美しい Holton (1997)の「パスカルの風車」("Pascal windmill") が導かれる[4]が、これはパスカルの等式も(原点において)成り立たない。 - ^ これはテイラーの定理の離散版として理解でき、ニュートン多項式と近しい。この形の交代和はネールント–ライス積分として表せる。
出典
- ^ Lilavati Section 6, Chapter 4 (see Knuth (1997)).
- ^ Higham (1998)
- ^ Shilov (1977, p. 92)
- ^ Holton, Pedersen (1997), Mathematical Reflections: In a Room With Many Mirrors, Springer, ISBN 978-1-4612-1932-3
- ^ Thomas, Muir (1904). “Note on selected combinations”. Proceedings of the Royal Society of Edinburgh. doi:10.1017/S0370164600007768 .
- ^ Boardman, Michael (2004), “The Egg-drop numbers”, Mathematics Magazine 77 (5): 368-372, JSTOR 3219201, MR1573776 , "it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients".
- ^ see induction developed in eq (7) p.1389 in Aupetit, Michael (2009), “Nearly homogeneous multi-partitioning with a deterministic generator”, Neurocomputing 72 (7-9): 1379-1389, doi:10.1016/j.neucom.2008.12.024, ISSN 0925-2312.
- ^ Ruiz, Sebastian (1996). “An algebraic identity leading to Wilson's theorem”. The Mathematical Gazette 80 (489): 579-582. doi:10.2307/3618534 .
- ^ Knuth 1997, p. 30.
- ^ see e.g. Ash (1990, p. 121) or Flum & Grohe (2006, p. 427).
- ^ Munarini, Emanuele (2011), “Riordan matrices and sums of harmonic numbers”, Applicable Analysis and Discrete Mathematics 5 (2): 176-200, doi:10.2298/AADM110609014M, MR2867317.
- 二項係数のページへのリンク