数学における二項係数(にこうけいすう、英: binomial coefficients)は二項展開において係数として現れる正の整数の族である。二項係数は2つの非負整数で添字付けられ、添字 n, k を持つ二項係数はふつう (n
k) とか (n|k) と書かれる(これは二項冪 (1 + x)n の展開における xk の項の係数である。適当な仮定の下で、この係数の値は n ! k ! ( n − k ) ! {\displaystyle {\tfrac {n!}{k!\,(n-k)!}}} で与えられる)。二項係数を、連続する整数 n に対する各行に k を 0 から n まで順に並べて得られる三角形状の数の並びをパスカルの三角形と呼ぶ。
この整数族は代数学のみならず数学の他の多くの分野、特に組合せ論において現れる。n元-集合から k個の元を(その順番を無視して)選ぶ方法が (n 二項係数に関して詳しく知られた最も初期の議論は10世紀ごろハラユーダ
k) 通りである。二項係数の性質を用いて、記号 (n
k) の意味を、もともとの n および k が k ? n なる非負整数であった場合を超えて拡張することが可能で、そのような場合もやはり二項係数と称する。
歴史と記法
記号 (n 自然数(0 も含める)n および k に対し、二項係数 (n に現れるため「二項係数」の名がある(この式自体は環の互いに可換な任意の元 x, y に対して成り立つ)。 組合せ論においてもまたこの数は、n 個の対象から k 個選ぶ選び方の総数、より形式的には n元-集合の k元-部分集合(k-項組合せ)の総数として現れる。この数が先に述べた係数と一致することは、後で述べるこの数の計算法の何れとも独立に示すことができる。実際、冪 (1 + X)n における n 個の因子の各々において、一時的に X に対し 1 ? i ? n なる添字 i をそれぞれ付けて区別しておくと、k 個の添字からなる部分集合をひとつ選ぶ毎に展開後の Xk への寄与が 1 だけあるから、この項の係数はそのような部分集合の選び方の数に一致する。このことは特に (n (n 一つは、n, k を 1 ? k ? n − 1 なる自然数として、純加法的な漸化式 ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}} を初期条件「任意の n ? 0 に対し (n この漸化式自体は、集合 {1, 2, 3, …, n} において以下のように場合を分けて k元-集合を数えることで得られる。特定の元に注目し、ここではそれを “i” とする。 この二者で与えられた n 個の元から得られるすべての k-組合せが数え上げられているので所期の結果を得る。 あるいはまた、(1 + X)n = (1 + X)n−1(1 + X) の両辺における Xk への寄与を見ることでもこの漸化式は得られる。(1 + X)n において Xn+1 や X−1 の項は存在しない(あるいは係数が零である)から、二項係数の定義を上記の境界を越えて延長して、(n この漸化式はパスカルの三角形を描くのにも利用できる。 個々の二項係数をより効果的に計算するには ( n k ) = n k _ k ! = n ( n − 1 ) ( n − 2 ) ⋯ ( n − ( k − 1 ) ) k ( k − 1 ) ( k − 2 ) ⋯ 1 = ∏ i = 1 k n − ( k − i ) i = ∏ i = 1 k n + 1 − i i {\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\textstyle \prod \limits _{i=1}^{k}{\dfrac {n-(k-i)}{i}}=\prod \limits _{i=1}^{k}{\dfrac {n+1-i}{i}}}
k) はアンドレアス・フォン・エッチンクハウゼン(英語版)が1826年に導入したものである[2]。そのほかの記法として C(n, k), nCk, nCk, Ck
n, Cn
k[3], Cn,k, (n|m) などがあり、何れも文字 C は組合せ (combination) や選択 (choice) を表している。
定義と解釈
k) は二項冪 (1 + X)n の展開における Xk の項の係数として定義できる。同係数は(k ? nのとき)二項公式 ( x + y ) n = ∑ k = 0 n ( n k ) x n − k y k {\displaystyle (x+y)^{n}=\textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}x^{n-k}y^{k}} (?)
k) が任意の自然数 n, k に対して自然数となることも示している。二項係数の組合せ論的解釈(二項係数展開が答えを与える数え上げ問題)は多く存在する。例えば、各位の和が k に一致する n桁のビット(つまり各位の数は 0 か 1)の語(文字列)の総数は (n
k) で与えられる。また、各 ai が非負整数であるものとして k = a1 + a2 + … + an と書く方法の総数は (n + k − 1
n − 1) 通りである。これら解釈のほとんどは、k-組合せを数えることに同値であることが容易に示される。
二項係数の値の計算
k) の値を、実際に二項冪を展開したり k-組合せを数え上げたりせずに、計算する方法はいくつかある。
漸化式
0) = (n
n) = 1」の下で用いることである。
(a) 特定の元 i を含む k 個の元を集める。この場合、各集まりは既に i があることは仮定しているから、残りの k − 1 個の元を i を除く n − 1 元の中から特定すればよい。
(b) 特定の元 i を全く含まない k 個の元を集める。この場合、i を除く n − 1 個の元から k 個を選ぶことに他ならない。
k) = 0 (k > n ∨ k < 0) とすることもできる。
乗法表示
Size:157 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef