二項係数
数学における二項係数(にこうけいすう、binomial coefficients)は二項展開において係数として現れる正の整数の族である。二項係数は二つの非負整数で添字付けられ、添字 n, k を持つ二項係数はふつう \tbinom{n}{k} とか (n¦k) と書かれる(これは二項冪 (1 + x)n の展開における xk の項の係数である。適当な仮定の下で、この係数の値は \tfrac{n!}{k!\,(n-k)!} で与えられる)。二項係数を、連続する整数 n に対する各行に k を 0 から n まで順に並べて得られる三角形状の数の並びをパスカルの三角形と呼ぶ。
この整数族は代数学のみならず数学の他の多くの分野、特に組合せ論において現れる。n-元集合から k-個の元を(その順番を無視して)選ぶ方法が \tbinom nk 通りである。二項係数の性質を用いて、記号 \tbinom nk の意味を、もともとの n および k が k ≤ n なる非負整数であった場合を超えて拡張することが可能で、そのような場合もやはり二項係数と称する。
二項係数に関して詳しく知られた最も初期の議論は10世紀ごろハラユーダが古代サンスクリット語で書いた "Pingala's Chandaḥśāstra" である。1150年ごろには、インドの数学者バースカラ2世が著書 "Lilavati" で二項係数について詳しく述べている。
記号 \tbinom{n}{k} はアンドレアス・フォン・エッチンクハウゼンが1826年に導入したものである。
そのほかの記法として C⁡(n, k), nCk, nCk, Ck, Cn, Cn,k, (n¦m) などがあり、何れも文字 C は組合せ (combination) や選択 (choice) を表している。
に現れるため「二項係数」の名がある(この式自体は環の互いに可換な任意の元 x, y に対して成り立つ)。
組合せ論においてもまたこの数は、n 個の対象から k 個選ぶ選び方の総数、より形式的には n-元集合の k-元部分集合(k-項組合せ)の総数として現れる。この数が先に述べた係数と一致することは、後で述べるこの数の計算法の何れとも独立に示すことができる。実際、冪 (1 + X)n における n 個の因子の各々において、一時的に X に対し 1 ≤ i ≤ n なる添字 i をそれぞれ付けて区別しておくと、k 個の添字からなる部分集合をひとつ選ぶ毎に展開後の Xk への寄与が 1 だけあるから、この項の係数はそのような部分集合の選び方の数に一致する。このことは特に (n) が任意の自然数 n, k に対して自然数となることも示している。二項係数の組合せ論的解釈(二項係数展開が答えを与える数え上げ問題)は多く存在する。例えば、各位の和が k に一致する n-桁のビット(つまり各位の数は 0 か 1)の語(文字列)の総数は (n) で与えられる。また、各 ai が非負整数であるものとして k  a1 + a2 + … + an と書く方法の総数は(n+k−1) 通りである。これら解釈のほとんどは、k-組合せを数えることに同値であることが容易に示される。
(n) の値を、実際に二項冪を展開したり k-組合せを数え上げたりせずに、計算する方法はいくつかある。
ひとつは、n, k を 1 ≤ k ≤ n − 1 なる自然数として、純加法的な漸化式
\binom nk = \binom{n-1}{k-1} + \binom{n-1}k
を初期条件「任意の 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)  0 (k > n ∨ k < 0) とすることもできる。
この漸化式はパスカルの三角形を描くのにも利用できる。
\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}=\prod_{i=1}^k \frac{n-(k-i)}{i}=\prod_{i=1}^k \frac{n+1-i}{i}
で与えられる式を用いる。一つ目の分数の分子に現れる nk は下降階乗冪である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は n 個の対象からなる集合から選ぶ順番を考慮して相異なる k 個の対象を取り出す方法の総数であり、分母は同じ k-組合せを与える相異なる並びの数を数えるものである。
最後に、計算論的には不利だが、短く書けるのでしばしば証明や導出に用いられるよく知られた階乗函数を用いた式は
\binom{n}{k} = \frac{n!}{k!\,(n-k)!}
で与えられる。ここに n! は n の階乗である。この式は上記の乗法表示式に、分子分母に対して (n − k)! を掛けることで得られる(その結果、この式において分母と分子は多くの共通因数を持つことになる)。(特に階乗は非常に速く増加するから)この式を(k が小さく n が大きい場合に)実際の数値計算に用いることは(先に共通因数を約分しない限り)実用的でない。この式は上記の乗法表示よりは二項係数が対称性
を持つことを見るのに適している(二項係数の定義から対称性をもつことはわかる)。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば
\binom nk =
\begin{cases}
n^{\underline{k}/k! & \text{if }\ k \le \frac{n}{2} \\
n^{\underline{n-k}/(n-k)! & \text{if }\ k > \frac{n}{2}
\end{cases}
と書ける。
乗法表示を用いれば、n を任意の数 α(負の整数、実数、複素数、……)あるいは任意の整数が可逆となるような可換環の元に取り換えて、
\binom \alpha k = \frac{\alpha^{\underline k}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}
により二項係数の定義を拡張することができる。この定義により、二項定理(の一方の変数を 1 としたもの)も一般化して
と書くことができる。故にこの場合も \tbinom\alpha k を二項係数と呼ぶことは正当化される。この等式は任意の複素数 α と X < 1 なる X に対して有効である。これはまた X を不定元とする形式冪級数の等式としても解釈でき、それは実際に定数係数 1 を持つ級数の任意の冪の定義として機能する。この定義を用いるポイントは、冪乗として満足することが期待される全ての恒等式(指数法則)、特に
(1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta},
((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta}
が満足されることである。α が非負整数 n のとき、k > n なる全ての項は零であり、上記の無限級数は有限和となり、したがってもともとの二項定理が再び得られる。しかし α がそれ以外の値ならば、負の整数や有理数の場合も含めて、上記の級数は実際に無限和になる。
で、これを用いて (n) が任意の自然数 n, k に対して自然数となること(別な言い方をすれば、連続する k-個の整数の積を k! が割り切ること)を帰納的に示すことができる。これは定義 (∗) や乗法表示からは直ちに明らかなことではない。
パスカルの法則からパスカルの三角形が生じる:
番号 n の行には (n) の値が k  0, …, n に対して並べられている。これを書くには、一番外側の 1 から始めて、常に隣り合う二項を加えた数をその真下に書いていけばよい。この方法によって、分数や乗算を使わずに二項係数を手早く計算することができる。
が直ちに読み取れる。
他の対角線上の数との差は、上記漸化式 (3) の帰結として、一つ前の対角線上の数である。
二項係数はよくある数え上げ問題の簡明な公式を与えるという意味で組合せ論において重要である。
n-元集合から k-元を選ぶ方法の総数は (n) である(組合せを参照)。
n-元集合から重複を許して k-元を選ぶ方法の総数は (n+k-1) 通りある(多重集合を参照)。
k 個の 1 と n 個の 0 を含む文字列は (n+k) 種類存在する。
k 個の 1 と n 個の 0 を含み、かつどの二つの 1 も隣り合わない文字列の総数は (n+1) である。
カタラン数: n+1(2n).
二項分布: (n)pk(1 − p)n−k.
t を不定元として、任意の非負整数 k に対して式
\binom{t}{k} =\frac{(t)_k}{k!}=\frac{(t)_k}{(k)_k}= \frac{t(t-1)(t-2)\cdots(t-k+1)}{k(k-1)(k-2)\cdots2 \cdot 1}
は t に関する有理係数多項式である。この意味において、t には任意の実数あるいは複素数を代入することができ、それによって二項係数の定義を一般化するとき、そのような「一般化された二項係数」はニュートンの一般化二項定理に現れる。
各 k に対し、多項式 () は p⁡(0) = p⁡(1) = … = p⁡(k − 1) = 0 かつ p⁡(k) = 1 を満たす唯一の k-次多項式 p(t) として特徴づけることができる。
\binom{t}{k} = \sum_{i=0}^k \left[{ k \atop i} \right]\frac{t^i}{k!}
と表すことができる。この導函数は対数微分法により
\frac{d}{\mathit{dt} \binom{t}{k} = \binom{t}{k} \sum_{i=0}^{k-1} \frac{1}{t-i}
と計算できる。
標数 0 の任意の体(すなわち、有理数体 Q を含む体)上で、次数が高々 d の任意の多項式 p⁡(t) は二項係数の線型結合
p(t) = \sum_{k=0}^d a_k \binom{t}{k}
として一意に書ける。このときの係数 ak は数列 p⁡(0), p⁡(1), …, p⁡(k) の第 k-階差で与えられ、明示的に書けば
で決まる。
各二項係数多項式 (t) は整数値(整数を代入したとき必ず整数を返す)である(これは例えばパスカルの等式を用いて k に関する帰納法で示せる)。従って、二項係数多項式の任意の整係数線型結合もまた整数値多項式になる。逆に等式 (4) により任意の整数値多項式がこれら二項係数多項式の正係数線型結合となることが示せる。より一般に標数 0 の体の任意の部分環 R に対し、K[t] に属する多項式が任意の整数において R に値をとるための必要十分条件はそれが二項係数多項式の R-係数線型結合となっていることである。
階乗表示を用いれば近くにある二項係数の関係を容易に知ることができる。例えば k を正整数、n は任意として
が成り立ち、また少しの計算で
\binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}
が得られる。さらに言えば以下の結果
\binom{n}{h}\binom{n-h}{k}=\binom{n}{k}\binom{n-k}{h}
は有用である。例えば定数 n に対して以下の漸化式
\binom{n}{k} = \frac{n+1-k}{k} \binom{n}{k-1}
を得ることができる。
は等式 (∗) において x  1 かつ y  1 とすれば得られる。これはパスカルの三角形の各行において現れる全ての数を足し合わせれば 2 の整数冪になると言っても同じである。この事実の組合せ論的解釈は二通りに数える論法 (double counting) で n-元集合 S の位数 i (i  1, 2, …, n) の部分集合を数えることである。任意の位数 i に対する部分集合を数えているのだから、その和は S の部分集合の総数に等しく、それが 2n であることはよく知られている。即ち、等式 (∗∗) は n-元集合の冪集合の位数が 2n であることを述べるものである。より明確に、n-桁のビット列を考えれば、このビット列は 2n 個の数を表すことに利用できる。その中でひとつも 1 を含まないビット列を考えれば、これは (n)  1 通りである。ちょうど一つ 1 を含むビット列は (n)  n 通りである。このように数えて行けば上記の式を得る。
および 0 k2 (n)  (n + n2)2n−2 は等式 (2) を x に関して(後者は二回)微分して x  1 と置けば得られる。
は任意の複素数 m, n と任意の非負整数 k に対して成立する。これは (1 + x)m (1 + x)n−m  (1 + x)n の展開における xk の係数として、等式 (2) を用いて求めることができる。m  1 のとき等式 (7) は等式 (3) に簡約される。
任意の整数 j, k, n (0 ≤ j ≤ k ≤ n) に対して適用できる同様の等式
は、\textstyle\frac{x^l}{(1-x)^{l+1} = \sum_{p=0}^\infty \binom{p}{l}x^p を用いれば
x\left(\tfrac{x^{j}{(1-x)^{j+1}\right) \left(\tfrac{x^{k-j}{(1-x)^{k-j+1}\right) = \tfrac{x^{k+1}{(1-x)^{k+2}
の展開における xn+1 の係数として求められる。j  k のとき等式 (8) は 0 (m)  (n+1) となる。展開 (7) を n  2m, k  m に対して用い、(1) を使えば
を得る。
F⁡(n) で n 番目のフィボナッチ数を表せば、パスカルの三角形の対角和に関する等式 0 (n−k)  F(n + 1) を得る。これは等式 (3) を用いた帰納法、あるいはゼッケンドルフの表現によって示すことができる(左辺は  {F⁡(2), …, F⁡(n)} の連続した元を含まない部分集合の総数を与えるものであり、そのようなものはまた F⁡(n + 1) 以下の数の全体を成すということに他ならないことに注意)。組合せ論的証明は後述。
等式 (8) から従う別の等式として、j  k − 1 とおいて k (n + 1 − j)(j−1)  (n+1) を得る。
0 (n) に対する閉じた式は(超幾何函数を用いなければ)ないが、再び等式 (3) および帰納法により k  0, …, n − 1 に対して 0 (−1)j (n)  (−1)k (n−1) を得る。同様に 0 (−1)j (n)  0 を得る(n  0 の自明な場合は除く。このときは 1 になる)。これ自身は次数高々 n の任意の多項式 P⁡(x) に対する和分差分学における結果 0 (−1)j (n)P(j)  0 の特別の場合である。P⁡(x)  x(x − 1)…(x − k + 1) (0 ≤ k < n) に対しては等式 (2) を k 回微分して x  −1 と置けば得られる。一般の場合はこれらの線型結合を作ればよい。
n-次以下の多項式 P(x) に対して
が成り立つ。ここで an は P(x) の n-次係数である。等式 (10) はより一般に、複素数 m, d に対して
\sum_{j=0}^n (-1)^j\binom{n}{j} P(m+(n-j)d) = d^n n! a_n
とできる。これは P⁡(x) の代わりに多項式 Q⁡(x) : P⁡(m + d⋅x) とするとき、Q⁡(x)がやはり n-次以下の多項式であることと n-次係数が dn⋅an であることとに注意すれば、等式 (10) を適用して直ちに得られる。
\frac{k-1}k\sum_{j=0}^\infty \frac 1 {\binom {j+x} k}=\frac 1{\binom{x-1}{k-1}
は k ≥ 2 に対して収束する。この等式はドイツの戦車問題を調べるのに利用できる。これを見るには
\frac{k-1}k\sum_{j=0}^{M}\frac 1 {\binom{j+x} k}=\frac 1{\binom{x-1}{k-1}-\frac 1{\binom{M+x}{k-1}
が成り立つことを M に関する帰納法で示せばよい。
等式 (9) から 0 i (n)2  n (2n) および 0 i2 (n)2  n2 (2n−2) が得られる。
Series multisectionにより、0 ≤ t < s として t を境に s 刻みに取った二項係数の総和と s 項の閉じた形の式の和との間の等式
\binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\dotsb=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}
が示せる。
二項係数を含む多くの等式が組合せ論的証明証明することができる。例えば n ≥ q なる非負整数に対して
\sum_{k=q}^n \binom{n}{k} \binom k q = 2^{n-q}\binom{n}{q}
(q  1 のとき (6) に簡約される)は、以下のように二通りに数える論法できる。左辺は集合 [n]  {1, 2, …, n} の少なくとも q 個の元を含む部分集合を選び、選ばれた元のうち q 個に印をつける方法を数えている。右辺も同じものを数えるのだけれども、n 個の元のうち q 個に印をつける方法が (n) 通りあり、その各々について印をつけた q 個を含む部分集合を得るには印の付いた q 個に残りの n − q 個の元から任意に追加すればよいから、そのような仕方は 2n−q 通りである。
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}
の両辺は集合 [n] の k-元部分集合を数えているのだけれども、右辺は特定の元(例えば n)を含むように選ぶ場合と含まないように選ぶ場合に分けて数えている。
等式 (9), 再掲すると
\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}
も組合せ論的に証明できる。2n 個の□を一列に並べ、それらのうちの n 個を選んで印をつけることを考える。そのような方法は (2n) 通りである(右辺)。他方、そのような n 個の□を選ぶときに、k 個は前半の n 個から、のこり n − k 個は後半の n 個から選ぶとして 1 ≤ k ≤ n に亙って考える。これにより 0 (n)(n)  (2n) が得られるから、等式 (1) を適用して所期の結果を得る。
等式 0 (n−k)  F(n + 1) も組合せ論的に証明できる。(n−k) は、二次元格子上で (0, 0) から (k, n − k) まで、(0, 1) または (1, 1) 刻みで移動して辿った経路の総数を表す。そのことは全部で n − k 個の点を亙るために必ずちょうど k 回だけ (1, 1) 刻みの移動をしなければならないのだから明らかである。さてここでちょうど k 個ある (1, 1) 刻みを (0, 2) 刻みで置き換えると、(0, 1) 刻みと (0, 2) 刻みを合わせて (0, n) へ到達することになる。これを 0 ≤ k ≤ ⌊n⌋ なる各 k に亙って考えれば、(0, 0) から (0, 1) 刻みと (0, 2) 刻みを合わせて (0, n) へ到達する方法の総数が数え上げられる。そのような方法の総数が F(n + 1) 通りあることは明らかでる。
\sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3}
\sum_{k=-a}^a(-1)^k{a+b\choose a+k} {b+c\choose b+k}{c+a\choose c+k}  = \frac{(a+b+c)!}{a!\,b!\,c!}
で与えられる。ここに a, b, c は非負整数である。
ある種の三角積分は二項係数で表される値を持つ。m, n を非負整数として:
\textstyle\int_{-\pi}^{\pi} \cos((2m-n)x)\cos^n x\ dx = \frac{\pi}{2^{n-1} \binom{n}{m}
\textstyle\int_{-\pi}^{\pi} \sin((2m-n)x)\sin^n x\ dx = \begin{cases}
(-1)^{m+(n+1)/2} \frac{\pi}{2^{n-1} \binom{n}{m} & (n \text{: odd}) \\
0 & (\text{otherwise})
\end{cases}
\textstyle\int_{-\pi}^{\pi} \cos((2m-n)x)\sin^n x\ dx = \begin{cases}
(-1)^{m+(n+1)/2} \frac{\pi}{2^{n-1} \binom{n}{m} & (n \text{: even}) \\
0 & (\text{otherwise})
\end{cases}
これらはオイラーの公式で三角函数を複素指数函数に変換して、二項定理で展開して項別積分すれば示せる。
固定した n に対して作られる数列 (n), (n), (n), … の通常母函数は
\sum_k {n\choose k} x^k = (1+x)^n
で与えられる。固定した k に対して作られる数列 (0), (1), (2), … の通常母函数は
\sum_{n=k}^\infty {n\choose k} y^n = \frac{y^k}{(1-y)^{k+1}
である。一般の非負整数 n, k に対する二項係数の二変数母函数 は
\sum_{n,k} {n\choose k} x^k y^n = \frac{1}{1-y-xy}
を満たす。二項係数に対する別の形の二変数母函数は、対称函数として
\sum_{n,k} {n+k\choose k} x^k y^n = \frac{1}{1-x-y}
で与えられる。
\sum_{n,k} \frac{1}{(n+k)!}{n+k\choose k} x^k y^n = e^{x+y}
となる。
1852年、クンマーは非負整数 m, n および素数 p に対し、(m+n) を整除する最大の p-冪が pc であるとき、c は m と n を加えるときに生じる p-進表示における繰り上がりの数に等しいことを示した。同じことだが、(n) における素因子 p の冪指数は k の小数部 が n の小数部よりも大きくなるような非負整数 j の総数に等しい。これにより、(n) が n((n, k) は n と k との最大公約数)で割り切れることが導かれる。したがって特に、任意の正整数 r および s < pr なる正整数 s に対して p は (pr) を割り切る。しかしより高次の p-冪に対してこれは正しくない(例えば 9 は (9) を割り切らない)。
は「任意の整数がほとんど全ての二項係数を整除する」という幾分驚くべき結果を与えた。より精確に言えば、整数 d を固定して、f⁡(N) は n < N なる二項係数 (n) のうち d で割り切れるものの総数を表すものとすると、
\lim_{N\to\infty} \frac{f(N)}{N(N+1)/2} = 1
が成り立つというものである。n < N なる二項係数 (n) の総数は N(N + 1) であるから、これは d で整除可能なものの占める密度が 1 に収束することを意味する。
別の事実として、整数 n ≥ 2 が素数となる必要十分条件は、中間二項係数
\binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n-1}
の全てが n で整除可能なことである。実際、p が素数ならば、0 < k < p なる任意の k に対して p は
\binom p k = \frac{p \cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1}
を割り切る。これは分子は素因数 p を含むが分母は p を素因数に持たないことによる。n が合成数のとき、p を n を割り切る最小の素因数とし、k  n と置けば、0 < p < n かつ
\binom{n}{p} = \frac{n(n-1)(n-2)\cdots(n-p+1)}{p!}=\frac{k(n-1)(n-2)\cdots(n-p+1)}{(p-1)!}
は n で割り切れない。仮に割り切れるとすると分子 k(n − 1)(n − 2)× … ×(n − p + 1) が n  k × p で割り切れることになり、それは (n − 1)(n − 2)× … ×(n − p + 1) が p で割り切れる場合しかありえないが、n は p で割り切れるのだから、p は n − 1, n − 2, …, n − p + 1 を割り切らず、p は素数だから従って (n − 1)(n − 2)× … ×(n − p + 1) も割り切らず、それゆえ分子が n で割りきられることもない。
\tbinom n k に関して以下の評価
\left(\frac{n}{k}\right)^k \le {n \choose k}  \le \frac{n^k}{k!} \le \left(\frac{n\cdot e}{k}\right)^k
が 1 ≤ k ≤ n に対して成立する。スターリングの近似からは n (2n) ≥ 22n−1, 一般に
\sqrt{n}{mn \choose n} \ge \frac{m^{m(n-1)+1}{(m-1)^{(m-1)(n-1)}
が m ≥ 2 かつ n ≥ 1 に対して成立する。また n → ∞ のとき近似
{2n \choose n} \sim \frac{4^n}{\sqrt{\pi n}
が成り立つ。n, k がともに 1 より十分大きければスターリング近似からは以下の漸近近似
\log_2{n \choose k} \sim n H\left(\frac{k}{n}\right)
も従う。ここに H⁡(ε)  −εlog2⁡(ε) − (1 − ε)log2⁡(1 − ε) は ε の二値エントロピー関数である。より精確に、任意の整数 n ≥ k ≥ 1 と ε ≐ k/n ≤ 1/2 に対して、最初の k + 1 個の二項係数の和を