二項係数
二項係数は与えられた集合から決められた位数の部分集合を数え上げるものであった。関連する組合せ論的問題として、与えられた集合から元をとって作られる決められた位数の多重集合を数え上げる問題、すなわち与えられた集合から重複を許して決められた数の元を選び出す重複組合せの問題がある。その総数は多重集合係数と呼ばれ、n 個の元から k 個選ぶ重複組合せの総数は ( ( n k ) ) {\displaystyle \left(\!{\tbinom {n}{k}}\!\right)} と書かれる。
以下議論の便宜のため n を使わずに、その代わり f = r + (k − 1) および r = f − (k − 1) なる非負整数 f, r を用いる。
多重集合係数は以下に示す関係
( f k ) = ( ( r k ) ) = ( r + k − 1 k ) {\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}}
により二項係数として書ける。この等式を以下のようにも特徴づけることができる。
( f ) k = f k _ = ( f − k + 1 ) ⋯ ( f − 3 ) ⋅ ( f − 2 ) ⋅ ( f − 1 ) ⋅ f , r ( k ) = r k ̄ = r ⋅ ( r + 1 ) ⋅ ( r + 2 ) ⋅ ( r + 3 ) ⋯ ( r + k − 1 ) {\displaystyle {\begin{aligned}(f)_{k}&=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,\\r^{(k)}&=r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1)\end{aligned}}}
二項係数の逆数の部分分数分解は
1 ( z n ) = ∑ i = 0 n − 1 ( − 1 ) n − 1 − i ( n i ) n − i z − i {\displaystyle {\frac {1}{\binom {z}{n}}}=\textstyle \sum \limits _{i=0}^{n-1}(-1)^{n-1-i}{\dbinom {n}{i}}{\dfrac {n-i}{z-i}}}
および
1 ( z + n n ) = ∑ i = 1 n ( − 1 ) i − 1 ( n i ) i z + i {\displaystyle {\frac {1}{\binom {z+n}{n}}}=\textstyle \sum \limits _{i=1}^{n}(-1)^{i-1}{\dbinom {n}{i}}{\dfrac {i}{z+i}}}
で与えられる。
多項係数は二項係数の性質とよく似たたくさんの性質を満たす。例えば漸化式
( n k 1 , k 2 , ... , k r ) = ( n − 1 k 1 − 1 , k 2 , ... , k r ) + ( n − 1 k 1 , k 2 − 1 , ... , k r ) + ⋯ + ( n − 1 k 1 , k 2 , ... , k r − 1 ) {\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{r}}}={\binom {n-1}{k_{1}-1,k_{2},\ldots ,k_{r}}}+{\binom {n-1}{k_{1},k_{2}-1,\ldots ,k_{r}}}+\dotsb +{\binom {n-1}{k_{1},k_{2},\ldots ,k_{r}-1}}}
および任意の置換 σ に関する対称性
( n k 1 , k 2 , ... , k r ) = ( n k σ 1 , k σ 2 , ... , k σ r ) {\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{r}}}={\binom {n}{k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}}}
が挙げられる。ただし、(σi) は (1,2, ...,r) を並べ替えたものである。
一つは、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 に対し (n0) = (nn) = 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) = (1 + X)(1 + X) の両辺における X への寄与を見ることでもこの漸化式は得られる。(1 + X) において X や X の項は存在しない(あるいは係数が零である)から、二項係数の定義を上記の境界を越えて延長して、(nk) = 0 (k > n ∨ k < 0) とすることもできる。
この漸化式はパスカルの三角形を描くのにも利用できる。
これはまた X を不定元とする形式冪級数の等式としても解釈でき、それは実際に定数係数 1 を持つ級数の任意の冪の定義として機能する。この定義を用いるポイントは、冪乗として満足することが期待される全ての恒等式(指数法則)、特に
( 1 + X ) α ( 1 + X ) β = ( 1 + X ) α + β , {\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta },}
( ( 1 + X ) α ) β = ( 1 + X ) α β {\displaystyle ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }}
が満足されることである。α が非負整数 n のとき、k > 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}}}
で与えられる式を用いる。一つ目の分数の分子に現れる n は下降階乗冪である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は n 個の対象からなる集合から選ぶ順番を考慮して相異なる k 個の対象を取り出す方法の総数であり、分母は同じ k-組合せを与える相異なる並びの数を数えるものである。
も従う。ここに H(ε) = −εlog2(ε) − (1 − ε)log2(1 − ε) は ε の二値エントロピー関数である。より精確に、任意の整数 n ≥ k ≥ 1 と ε ≐ k/n ≤ 1/2 に対して、最初の k + 1 個の二項係数の和を
1 8 n ε ( 1 − ε ) ⋅ 2 H ( ε ) ⋅ n ≤ ∑ i = 0 k ( n i ) ≤ 2 H ( ε ) ⋅ n {\displaystyle {\frac {1}{\sqrt {8n\epsilon (1-\epsilon )}}}\cdot 2^{H(\epsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon )\cdot n}}
と評価することができる。
n が大きく、k が n に対して十分小さいとき ( n k ) = n ( n − 1 ) ... ( n − k + 1 ) k ! ≈ ( n − k / 2 ) k k k e − k 2 π k = ( n / k − 0.5 ) k e k 2 π k {\displaystyle \textstyle {\binom {n}{k}}={\frac {n(n-1)\dots (n-k+1)}{k!}}\approx {\frac {(n-k/2)^{k}}{k^{k}e^{-k}{\sqrt {2\pi k}}}}={\frac {(n/k-0.