二項係数

数学における二項係数（にこうけいすう、英: binomial coefficients）は二項展開において係数として現れる正の整数の族である。二項係数は2つの非負整数で添字付けられ、添字 n, k を持つ二項係数はふつう (n
k) とか (n¦k) と書かれる（これは二項冪 (1 + x)ⁿ の展開における x^k の項の係数である。適当な仮定の下で、この係数の値は ${\tfrac {n!}{k!\,(n-k)!}}$ で与えられる）。二項係数を、連続する整数 n に対する各行に k を 0 から n まで順に並べて得られる三角形状の数の並びをパスカルの三角形と呼ぶ。

二項係数の全体をパスカルの三角形の形に並べることができる。

4つの数から2つの数を選ぶ方法は ${\tbinom {4}{2}}=6$ 通りある。

四次までの二項展開の視覚的説明

この整数族は代数学のみならず数学の他の多くの分野、特に組合せ論において現れる。n元-集合から k個の元を（その順番を無視して）選ぶ方法が (n
k) 通りである。二項係数の性質を用いて、記号 (n
k) の意味を、もともとの n および k が k ≤ n なる非負整数であった場合を超えて拡張することが可能で、そのような場合もやはり二項係数と称する。

歴史と記法

二項係数に関して詳しく知られた最も初期の議論は10世紀ごろハラユーダが古代サンスクリット語で書いた "Pingala's Chandaḥśāstra" である。1150年ごろには、インドの数学者バースカラ2世が著書 "Lilavati" で二項係数について詳しく述べている。

記号 (n
k) はアンドレアス・フォン・エッチンクハウゼンが1826年に導入したものである。 そのほかの記法として C⁡(n, k), _nC_k, ⁿC_k, Ck
n, Cn
k, C_n,k, (n¦m) などがあり、何れも文字 C は組合せ (combination) や選択 (choice) を表している。

定義と解釈

自然数（0 も含める）n および k に対し、二項係数 (n
k) は二項冪 (1 + X)ⁿ の展開における X^k の項の係数として定義できる。同係数は（k ≤ nのとき）二項公式

$(x+y)^{n}=\textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}x^{n-k}y^{k}$

(∗)

に現れるため「二項係数」の名がある（この式自体は環の互いに可換な任意の元 x, y に対して成り立つ）。

組合せ論においてもまたこの数は、n 個の対象から k 個選ぶ選び方の総数、より形式的には n元-集合の k元-部分集合（k-項組合せ）の総数として現れる。この数が先に述べた係数と一致することは、後で述べるこの数の計算法の何れとも独立に示すことができる。実際、冪 (1 + X)ⁿ における n 個の因子の各々において、一時的に X に対し 1 ≤ i ≤ n なる添字 i をそれぞれ付けて区別しておくと、k 個の添字からなる部分集合をひとつ選ぶ毎に展開後の X^k への寄与が 1 だけあるから、この項の係数はそのような部分集合の選び方の数に一致する。このことは特に (n
k) が任意の自然数 n, k に対して自然数となることも示している。二項係数の組合せ論的解釈（二項係数展開が答えを与える数え上げ問題）は多く存在する。例えば、各位の和が k に一致する n桁のビット（つまり各位の数は 0 か 1）の語（文字列）の総数は (n
k) で与えられる。また、各 a_i が非負整数であるものとして k = a₁ + a₂ + … + a_n と書く方法の総数は (n + k − 1
n − 1) 通りである。これら解釈のほとんどは、k-組合せを数えることに同値であることが容易に示される。

二項係数の値の計算

(n
k) の値を、実際に二項冪を展開したり k-組合せを数え上げたりせずに、計算する方法はいくつかある。

漸化式

一つは、n, k を 1 ≤ k ≤ n − 1 なる自然数として、純加法的な漸化式

${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}$

を初期条件「任意の 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)ⁿ = (1 + X)ⁿ⁻¹(1 + X) の両辺における X^k への寄与を見ることでもこの漸化式は得られる。(1 + X)ⁿ において Xⁿ⁺¹ や X⁻¹ の項は存在しない（あるいは係数が零である）から、二項係数の定義を上記の境界を越えて延長して、(n
k) = 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}}=\textstyle \prod \limits _{i=1}^{k}{\dfrac {n-(k-i)}{i}}=\prod \limits _{i=1}^{k}{\dfrac {n+1-i}{i}}$

で与えられる式を用いる。一つ目の分数の分子に現れる n^k は下降階乗冪である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は n 個の対象からなる集合から選ぶ順番を考慮して相異なる k 個の対象を取り出す方法の総数であり、分母は同じ k-組合せを与える相異なる並びの数を数えるものである。

階乗表示

最後に、計算論的には不利だが、短く書けるのでしばしば証明や導出に用いられるよく知られた階乗函数を用いた式は

${\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}$

で与えられる。ここに n! は n の階乗である。この式は上記の乗法表示式に、分子分母に対して (n − k)! を掛けることで得られる（その結果、この式において分母と分子は多くの共通因数を持つことになる）。（特に階乗は非常に速く増加するから）この式を（k が小さく n が大きい場合に）実際の数値計算に用いることは（先に共通因数を約分しない限り）実用的でない。この式は上記の乗法表示よりは二項係数が対称性

${\binom {n}{k}}={\binom {n}{n-k}}$

(1)

を持つことを見るのに適している（二項係数の定義から対称性をもつことは分かる）。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば

${\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\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 としたもの）も一般化して

$(1+X)^{\alpha }=\textstyle \sum \limits _{k=0}^{\infty }{\dbinom {\alpha }{k}}X^{k}$

(2)

と書くことができる。故にこの場合も (α
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 なる全ての項は零であり、上記の無限級数は有限和となり、したがってもともとの二項定理が再び得られる。しかし α がそれ以外の値ならば、負の整数や有理数の場合も含めて、上記の級数は実際に無限和になる。

パスカルの三角形

パスカルの三角形の第1000 行に並ぶ二項係数を縦に並べたもの。各二項係数を十進表示し、その各桁の数字を0-9に応じたグレイスケールの点で表してある。画像の左の境界は二項係数の対数グラフにほぼ対応しており、これらが対数凹列であることが見て取れる。

→詳細は「パスカルの三角形」を参照

パスカルの法則は重要な漸化式

${\binom {n}{k}}+{\binom {n}{k+1}}={\binom {n+1}{k+1}},$

(3)

で、これを用いて (n
k) が任意の自然数 n, k に対して自然数となること（別な言い方をすれば、連続する k-個の整数の積を k! が割り切ること）を帰納的に示すことができる。これは定義 (∗) や乗法表示からは直ちに明らかなことではない。

パスカルの法則からパスカルの三角形が生じる:

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

番号 n の行には (n
k) の値が k = 0, …, n に対して並べられている。これを書くには、一番外側の 1 から始めて、常に隣り合う２項を加えた数をその真下に書いていけばよい。この方法によって、分数や乗算を使わずに二項係数を手早く計算することができる。

例えば三角形の5行目を見れば

(x + y)⁵ = 1 x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1 y⁵

が直ちに読み取れる。

他の対角線上の数との差は、上記漸化式 (3) の帰結として、一つ前の対角線上の数である。

解釈

二項係数はよくある数え上げ問題の簡明な公式を与えるという意味で組合せ論において重要である。

• n-元集合から k-元を選ぶ方法の総数は (n
  k) である（組合せを参照）。
• n-元集合から重複を許して k元を選ぶ方法の総数は(n + k − 1
  k) 通りある（多重集合を参照）。
• k 個の 1 と n 個の 0 を含む文字列は (n + k
  k) 種類存在する。
• k 個の 1 と n 個の 0 を含み、かつどの2つの 1 も隣り合わない文字列の総数は (n + 1
  k) である。
• カタラン数：1/n + 1(2n
  n).
• 二項分布：(n
  k)p^k(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)\cdots 2\cdot 1}}$

は t に関する有理係数多項式である。この意味において、t には任意の実数あるいは複素数を代入することができ、それによって二項係数の定義を一般化するとき、そのような「一般化された二項係数」はニュートンの一般化二項定理に現れる。

各 k に対し、多項式 (t
k) は p⁡(0) = p⁡(1) = … = p⁡(k − 1) = 0 かつ p⁡(k) = 1 を満たす唯一の k次多項式 p(t) として特徴づけることができる。

この多項式の係数は第一種スターリング数を用いて

${\binom {t}{k}}=\textstyle \sum \limits _{i=0}^{k}\displaystyle \left[{k \atop i}\right]{\frac {t^{i}}{k!}}$

と表すことができる。この導函数は対数微分法により

${\frac {d}{\mathit {dt}}}{\binom {t}{k}}={\binom {t}{k}}\textstyle \sum \limits _{i=0}^{k-1}{\dfrac {1}{t-i}}$

と計算できる。

多項式の空間の基底

標数 0 の任意の体（すなわち、有理数体 Q を含む体）上で、次数が高々 d の任意の多項式 p⁡(t) は二項係数の線型結合

$p(t)=\textstyle \sum \limits _{k=0}^{d}a_{k}{\dbinom {t}{k}}$

として一意に書ける。このときの係数 a_k は数列 p⁡(0), p⁡(1), …, p⁡(k) の第 k-階差で与えられ、明示的に書けば

$a_{k}=\textstyle \sum \limits _{i=0}^{k}(-1)^{k-i}{\dbinom {k}{i}}p(i)$

(4)

で決まる。

整数値多項式

→詳細は「整数値多項式」を参照

各二項係数多項式 (t
k) は整数値（整数を代入したとき必ず整数を返す）である（これは例えばパスカルの等式を用いて k に関する帰納法で示せる）。従って、二項係数多項式の任意の整係数線型結合もまた整数値多項式になる。逆に等式 (4) により任意の整数値多項式がこれら二項係数多項式の正係数線型結合となることが示せる。より一般に標数 0 の体の任意の部分環 R に対し、K[t] に属する多項式が任意の整数において R に値をとるための必要十分条件はそれが二項係数多項式の R-係数線型結合となっていることである。

二項係数に関する等式

階乗表示を用いれば近くにある二項係数の関係を容易に知ることができる。例えば k を正整数、n は任意として

${\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}$

(5)

が成り立ち、また少しの計算で

${\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}}$

を得ることができる。

二項係数を含む級数

等式

$\textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}=2^{n}$

(∗∗)

は等式 (∗) において x = 1 かつ y = 1 とすれば得られる。これはパスカルの三角形の各行において現れる全ての数を足し合わせれば 2 の整数冪になると言っても同じである。この事実の組合せ論的解釈は二通りに数える論法 (double counting) で n元-集合 S の位数 i (i = 1, 2, …, n) の部分集合を数えることである。任意の位数 i に対する部分集合を数えているのだから、その和は S の部分集合の総数に等しく、それが 2ⁿ であることはよく知られている。すなわち、等式 (∗∗) は n元-集合の冪集合の位数が 2ⁿ であることを述べるものである。より明確に、n-桁のビット列を考えれば、このビット列は 2ⁿ 個の数を表すことに利用できる。その中で一つも 1 を含まないビット列を考えれば、これは (n
0) = 1 通りである。ちょうど一つ 1 を含むビット列は (n
1) = n 通りである。このように数えて行けば上記の式を得る。

等式

$\textstyle \sum \limits _{k=0}^{n}k{\dbinom {n}{k}}=n2^{n-1}$

(6)

および

$\textstyle \sum \limits _{k=0}^{n}k^{2}{\dbinom {n}{k}}=(n+n^{2})2^{n-2}$

は等式 (2) を x に関して（後者は2回）微分して x = 1 と置けば得られる。

朱ファンデルモンドの等式

$\textstyle \sum \limits _{j=0}^{k}{\dbinom {m}{j}}{\dbinom {n-m}{k-j}}={\dbinom {n}{k}}$

(7)

は任意の複素数 m, n と任意の非負整数 k に対して成立する。これは (1 + x)^m (1 + x)^n−m = (1 + x)ⁿ の展開における x^k の係数として、等式 (2) を用いて求めることができる。m = 1 のとき等式 (7) は等式 (3) に簡約される。

任意の整数 j, k, n (0 ≤ j ≤ k ≤ n) に対して適用できる同様の等式

$\textstyle \sum \limits _{m=0}^{n}{\dbinom {m}{j}}{\dbinom {n-m}{k-j}}={\dbinom {n+1}{k+1}}$

(8)

は、${\frac {x^{l}}{(1-x)^{l+1}}}=\textstyle \sum \limits _{p=0}^{\infty }{\dbinom {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}}}$

の展開における xⁿ⁺¹ の係数として求められる。j = k のとき等式 (8) は

$\textstyle \sum \limits _{m=0}^{n}{\dbinom {m}{k}}={\dbinom {n+1}{k+1}}$

となる。展開 (7) を n = 2m, k = m に対して用い、(1) を使えば

$\textstyle \sum \limits _{j=0}^{m}{\dbinom {m}{j}}^{2}={\dbinom {2m}{m}}$

(9)

を得る。

F⁡(n) で n 番目のフィボナッチ数を表せば、パスカルの三角形の対角和に関する等式

$\textstyle \sum \limits _{k=0}^{\lfloor n/2\rfloor }{\dbinom {n-k}{k}}=F(n+1)$

(10)

を得る。これは等式 (3) を用いた帰納法、あるいはゼッケンドルフの表現によって示すことができる（左辺は {F⁡(2), …, F⁡(n)} の連続した元を含まない部分集合の総数を与えるものであり、そのようなものはまた F⁡(n + 1) 以下の数の全体を成すということに他ならないことに注意）。組合せ論的証明は後述。

等式 (8) から従う別の等式として、j = k − 1 とおいて ∑
n (n + 1 − j)(j − 1
k − 1) = (n + 1
k + 1) を得る。

∑k
j=0 (n
j) に対する閉じた式は（超幾何函数を用いなければ）ないが、再び等式 (3) および帰納法により k = 0, …, n − 1 に対して ∑
k (−1) ^j (n
j) = (−1)^k (n − 1
k) を得る。同様に ∑
n (−1) ^j (n
j) = 0 を得る（n = 0 の自明な場合は除く。このときは 1 になる）。これ自身は次数高々 n の任意の多項式 P⁡(x) に対する和分差分学における結果∑
n (−1) ^j (n
j) P(j) = 0 の特別の場合である。P⁡(x) = x(x − 1)…(x − k + 1) (0 ≤ k < n) に対しては等式 (2) を k 回微分して x = −1 と置けば得られる。一般の場合はこれらの線型結合を作ればよい。

n次以下の多項式 P(x) に対して

$\textstyle \sum \limits _{j=0}^{n}(-1)^{j}{\dbinom {n}{j}}P(n-j)=n!a_{n}$

(11)

が成り立つ。ここで a_n は P(x) の n次係数である。等式 (11) はより一般に、複素数 m, d に対して

$\textstyle \sum \limits _{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次係数が dⁿ⋅a_n であることに注意すれば、等式 (11) を適用して直ちに得られる。

級数

${\frac {k-1}{k}}\textstyle \sum \limits _{j=0}^{\infty }{\dfrac {1}{\binom {j+x}{k}}}={\dfrac {1}{\binom {x-1}{k-1}}}$

は k ≥ 2 に対して収束する。この等式はドイツの戦車問題を調べるのに利用できる。これを見るには

${\frac {k-1}{k}}\textstyle \sum \limits _{j=0}^{M}{\dfrac {1}{\binom {j+x}{k}}}={\dfrac {1}{\binom {x-1}{k-1}}}-{\dfrac {1}{\binom {M+x}{k-1}}}$

が成り立つことを M に関する帰納法で示せばよい。

等式 (9) から ∑
n i (n
i)² = n/2 (2n
n) および ∑
n i² (n
i)² = n² (2n − 2
n − 1) が得られる。

Series multisectionにより、0 ≤ t < s として t を境に s 刻みに取った二項係数の総和と s 項の閉じた形の式の和との間の等式

${\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\dotsb ={\frac {1}{s}}\textstyle \sum \limits _{j=0}^{s-1}\left(2\cos {\dfrac {\pi j}{s}}\right)^{n}\cos {\dfrac {\pi (n-2t)j}{s}}$

が示せる。

組合せ論的に証明できる等式

二項係数を含む多くの等式が組合せ論的に証明することができる。例えば n ≥ q なる非負整数に対して

$\textstyle \sum \limits _{k=q}^{n}{\dbinom {n}{k}}{\dbinom {k}{q}}=2^{n-q}{\dbinom {n}{q}}$

（q = 1 のとき (6) に簡約される）は、以下のように二通りの仕方で数えて証明できる。左辺は集合 [n] = {1, 2, …, n} の少なくとも q 個の元を含む部分集合を選び、選ばれた元のうち q 個に印をつける方法を数えている。右辺も同じものを数えるのだけれども、n 個の元のうち q 個に印をつける方法が (n
q) 通りあり、その各々について印をつけた q 個を含む部分集合を得るには印の付いた q 個に残りの n − q 個の元から任意に追加すればよいから、そのような仕方は 2^n−q 通りである。

パスカルの法則

${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}$

の両辺は集合 [n] の k元-部分集合を数えているのだけれども、右辺は特定の元（例えば n）を含むように選ぶ場合と含まないように選ぶ場合に分けて数えている。

等式 (9), 再掲すると

$\textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}^{2}={\dbinom {2n}{n}}$

も組合せ論的に証明できる。2n 個の□を一列に並べ、それらのうちの n 個を選んで印を付けることを考える。そのような方法は (2n
n) 通りである（右辺）。他方、そのような n 個の□を選ぶときに、k 個は前半の n 個から、残り n − k 個は後半の n 個から選ぶとして 1 ≤ k ≤ n に亙って考える。これにより ∑
n (n
k)(n
n − k) = (2n
n) が得られるから、等式 (1) を適用して所期の結果を得る。

2次元格子上の経路の例

等式 (10) も組合せ論的に証明できる。(n − k
k) は、2次元格子上で (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 / 2⌋ なる各 k に亙って考えれば、(0, 0) から (0, 1) 刻みと (0, 2) 刻みを合わせて (0, n) へ到達する方法の総数が数え上げられる。そのような方法の総数が F(n + 1) 通りあることは明らかである。

ディクソンの等式

ディクソンの等式は

$\textstyle \sum \limits _{k=-a}^{a}(-1)^{k}{\dbinom {2a}{k+a}}^{3}={\dfrac {(3a)!}{(a!)^{3}}}$

あるいはより一般に

$\textstyle \sum \limits _{k=-a}^{a}(-1)^{k}{\dbinom {a+b}{a+k}}{\dbinom {b+c}{b+k}}{\dbinom {c+a}{c+k}}={\dfrac {(a+b+c)!}{a!\,b!\,c!}}$

で与えられる。ここに a, b, c は非負整数である。

連続等式

ある種の三角積分は二項係数で表される値を持つ。m, n を非負整数として:

• $\int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}x\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}$
• $\int _{-\pi }^{\pi }\sin((2m-n)x)\sin ^{n}x\ dx={\begin{cases}(-1)^{m+{\frac {n+1}{2}}}{\dfrac {\pi }{2^{n-1}}}{\dbinom {n}{m}}&(n{\text{: odd}})\\0&({\text{otherwise}})\end{cases}}$
• $\int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}x\ dx={\begin{cases}(-1)^{m+{\frac {n+1}{2}}}{\dfrac {\pi }{2^{n-1}}}{\dbinom {n}{m}}&(n{\text{: even}})\\0&({\text{otherwise}})\end{cases}}$

これらはオイラーの公式で三角函数を複素指数函数に変換して、二項定理で展開して項別積分すれば示せる。

母函数

通常母函数

固定した n に対して作られる数列 (n
0), (n
1), (n
2), … の通常母函数は

$\textstyle \sum \limits _{k=0}^{\infty }{\dbinom {n}{k}}x^{k}=(1+x)^{n}$

で与えられる。固定した k に対して作られる数列 (0
k), (1
k), (2
k), … の通常母函数は

$\textstyle \sum \limits _{n=k}^{\infty }{\dbinom {n}{k}}y^{n}={\dfrac {y^{k}}{(1-y)^{k+1}}}$

である。一般の非負整数 n, k に対する二項係数の二変数母函数 は

$\textstyle \sum \limits _{n,k}{\dbinom {n}{k}}x^{k}y^{n}={\dfrac {1}{1-y-xy}}$

を満たす。二項係数に対する別の形の二変数母函数は、対称函数として

$\textstyle \sum \limits _{n,k}{\dbinom {n+k}{k}}x^{k}y^{n}={\dfrac {1}{1-x-y}}$

で与えられる。

指数型母函数

二項係数に関する指数型二変数母函数は

$\sum _{n,k}{\frac {1}{(n+k)!}}{\binom {n+k}{k}}x^{k}y^{n}=e^{x+y}$

となる。

可除性

→詳細は「クンマーの定理」および「リュカの定理」を参照

1852年、クンマーは非負整数 m, n および素数 p に対し、(m + n
m) を整除する最大の p-冪が p^c であるとき、c は m と n を加えるときに生じる p-進表示における繰り上がりの数に等しいことを示した。同じことだが、(n
k) における素因子 p の冪指数は k⁄p ^j の小数部 が n⁄p ^j の小数部よりも大きくなるような非負整数 j の総数に等しい。これにより、(n
k) が n⁄gcd(n,k) で割り切れることが導かれる。したがって特に、任意の正整数 r および s < p^r なる正整数 s に対して p は (p^r
s) を割り切る。しかしより高次の p-冪に対してこれは正しくない（例えば 9 は (9
6) を割り切らない）。

Singmaster (1974) は「任意の整数がほとんど全ての二項係数を整除する」という幾分驚くべき結果を与えた。より精確に言えば、整数 d を固定して、f⁡(N) は n < N なる二項係数 (n
k) のうち d で割り切れるものの総数を表すものとすると、

$\lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1$

が成り立つというものである。n < N なる二項係数 (n
k) の総数は 1/2N(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/p と置けば、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 で割り切られることもない。

上界・下界と漸近公式

(n
k) に関して以下の評価

$\left({\frac {n}{k}}\right)^{k}\leq {\binom {n}{k}}\leq {\frac {n^{k}}{k!}}\leq \left({\frac {n\cdot e}{k}}\right)^{k}$

が 1 ≤ k ≤ n に対して成立する。スターリングの近似からは √n (2n
n) ≥ 2²ⁿ⁻¹, 一般に

${\sqrt {n}}{\binom {mn}{n}}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}$

が m ≥ 2 かつ n ≥ 1 に対して成立する。また n → ∞ のとき近似

${\binom {2n}{n}}\sim {\frac {4^{n}}{\sqrt {\pi n}}}$

が成り立つ。n, k がともに 1 より十分大きければスターリング近似からは以下の漸近近似

$\log _{2}{\binom {n}{k}}\sim nH\left({\frac {k}{n}}\right)$

も従う。ここに H⁡(ε) = −εlog₂⁡(ε) − (1 − ε)log₂⁡(1 − ε) は ε の二値エントロピー関数である。より精確に、任意の整数 n ≥ k ≥ 1 と ε ≐ k/n ≤ 1/2 に対して、最初の k + 1 個の二項係数の和を

${\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 に対して十分小さいとき $\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.5)^{k}e^{k}}{\sqrt {2\pi k}}}$ と書くことができるので、

$\log {\binom {n}{k}}\approx k\ln({\frac {n}{k}}-0.5)+k-0.5\ln(2\pi k)$

を得る。より精度を望むならば、ln⁡(n(n − 1)…(n − k + 1)) を積分で近似して

$\log {\binom {n}{k}}\approx (n+0.5)\ln {\frac {n+0.5}{n-k+0.5}}+k\ln {\frac {n-k+0.5}{k}}-0.5\ln(2\pi k)$

となる。n = 20 かつ k = 10 に対して log⁡(n
k) ≈ 12.127 およびこれら近似式からそれぞれ近似値 12.312 および 12.133 を得る。

ガンマ函数の無限積表示に基づく無限積

$(-1)^{k}{\binom {z}{k}}={\binom {-z+k-1}{k}}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {(1+{\frac {1}{j}})^{-z-1}}{1-{\frac {z+1}{j}}}}$

から漸近公式

${\binom {z}{k}}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}},\quad {\binom {z+k}{k}}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)$

が k → ∞ で成り立つ。この漸近挙動は近似

${\binom {z+k}{k}}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}$

にも表れている。ここに、H_k は k番目の調和数で、γ はオイラー–マスケローニ定数である。さらに、k → ∞ かつ適当な複素数 x に対して j/k → x なるとき、漸近公式

${\frac {\binom {z+k}{j}}{\binom {k}{j}}}\to \left(1-{\frac {j}{k}}\right)^{-z},\quad {\frac {\binom {j}{j-k}}{\binom {j-z}{j-k}}}\to \left({\frac {j}{k}}\right)^{z}$

が成り立つ。

二項係数の和について、二項定理を用いると

$\sum _{i=0}^{k}{\binom {n}{i}}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}=(1+n)^{k}$

という単純で粗い上界が得られる。

近似

n が十分大きいとき、

${\binom {n}{k}}={\frac {2^{n}}{\sqrt {{\tfrac {1}{2}}n\pi }}}e^{-{\frac {(k-(n/2))^{2}}{n/2}}}\left[1+O\left({\frac {1}{\sqrt {n}}}\right)\right]$

は二項係数と正規分布との関係に基づく近似を与える。これは、二項分布と等しい期待値と分散 (np, np(1-p)) を持つ正規分布をとり、p = 1 − p = 1/2 として、2ⁿ を掛ければ、中心極限定理に対する評価から従う。

一般化

多項への一般化

→詳細は「多項係数」を参照

二項係数を一般化するものとして

${\binom {n}{k_{1},k_{2},\ldots ,k_{r}}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}\qquad (\textstyle \sum \limits _{i=1}^{r}k_{i}=n)$

で定義される数を多項係数と呼ぶ。二項係数が (x + y)ⁿ の係数であったのに対し、多項係数は (x₁ + x₂ + … + x_r)ⁿ の多項式展開の係数であり、r = 2 のとき二項係数を与える:

${\binom {n}{k_{1},k_{2}}}={\binom {n}{k_{1},n-k_{1}}}={\binom {n}{k_{1}}}={\binom {n}{k_{2}}}.$

多項係数は、区別可能な n 個の元を r 個の箱に分けて入れるとき、箱の番号 i (1 ≤ i ≤ r) に対して各箱がちょうど k_i 個の元を含むような分け方の総数として組合せ論的に解釈できる。

多項係数は二項係数の性質とよく似たたくさんの性質を満たす。例えば漸化式

${\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}}$

および任意の置換 σ に関する対称性

${\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) を並べ替えたものである。

テイラー級数

第一種スターリング数を用いれば、二項係数の任意に選んだ点 z₀ の周りでのテイラー展開は

${\begin{aligned}{\binom {z}{k}}={\frac {1}{k!}}\sum _{i=0}^{k}z^{i}s_{k,i}&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}{\binom {z_{0}}{j-i}}{\frac {s_{k+i-j,i}}{(k+i-j)!}}\\&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}z_{0}^{j-i}{\binom {j}{i}}{\frac {s_{k,j}}{k!}}\end{aligned}}$

と与えられる。

半整数に対する二項係数

二項係数の定義（積による表示）は n が実数、k が整数の場合にも意味を持つ。特に n = 1/2 のとき任意の非負整数 k に対して

${\binom {1/2}{k}}={\binom {2k}{k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}$

が成り立つ。これは二項級数展開 √1 + x = ∑
k≥0 (1/2
k)x^k に現れる。

二項係数の積

二項係数の積は二項係数の線型結合として

${\binom {z}{m}}{\binom {z}{n}}=\textstyle \sum \limits _{k=0}^{m}{\dbinom {m+n-k}{k,m-k,n-k}}{\dbinom {z}{m+n-k}}$

と表すことができる。この展開の結合係数は多項係数で与えられる。ラベル付けられた組合せ論的対象を用いて言えば、この結合係数はそれぞれ重み m および n のラベル付けられた対象の対で最初の k 個のラベルが一致するようなものに m + n − k をラベル付ける方法の総数、あるいはそれらを貼り合せて新たに重み m + n − k でラベル付けられた対象を付け加える方法（つまり、このラベルを一方の対象の貼り合せない部分、他方の対象の貼り合せない部分、両者の貼り合せ部分の3つの部分に分ける方法）の総数である。このように見ると、二項係数の母函数は下降階乗冪に対する通常母函数に対応する指数型母函数である。

部分分数分解

二項係数の逆数の部分分数分解は

${\frac {1}{\binom {z}{n}}}=\textstyle \sum \limits _{i=0}^{n-1}(-1)^{n-1-i}{\dbinom {n}{i}}{\dfrac {n-i}{z-i}}$

および

${\frac {1}{\binom {z+n}{n}}}=\textstyle \sum \limits _{i=1}^{n}(-1)^{i-1}{\dbinom {n}{i}}{\dfrac {i}{z+i}}$

で与えられる。

ニュートンの一般二項級数

→詳細は「二項級数」を参照

アイザック・ニュートンに名を因むニュートンの二項級数は、二項定理の級数版

$(1+z)^{\alpha }=\textstyle \sum \limits _{n=0}^{\infty }{\dbinom {\alpha }{n}}z^{n}=1+{\dbinom {\alpha }{1}}z+{\dbinom {\alpha }{2}}z^{2}+\dotsb$

である。これが成り立つことは両辺が微分方程式 (1 + z)f'(z) = αf(z) を満たすことを見ればよい。

この級数の収束半径は 1 である。

${\frac {1}{(1-z)^{\alpha +1}}}=\textstyle \sum \limits _{n=0}^{\infty }{\dbinom {n+\alpha }{n}}z^{n}$

とも書ける。

上昇版二項係数

→詳細は「多重集合係数」を参照

二項係数は与えられた集合から決められた位数の部分集合を数え上げるものであった。関連する組合せ論的問題として、与えられた集合から元をとって作られる決められた位数の多重集合を数え上げる問題、すなわち与えられた集合から重複を許して決められた数の元を選び出す重複組合せの問題がある。その総数は多重集合係数と呼ばれ、n 個の元から k 個選ぶ重複組合せの総数は $\left(\!{\tbinom {n}{k}}\!\right)$ と書かれる。

以下議論の便宜のため n を使わずに、その代わり f = r + (k − 1) および r = f − (k − 1) なる非負整数 f, r を用いる。

多重集合係数は以下に示す関係

${\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}$

により二項係数として書ける。この等式を以下のようにも特徴づけることができる。

${\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}}$

が等しいことに注意すれば、二項係数を下降階乗冪を用いて

${\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}$

と書くとき、対応する多重集合係数は下降階乗冪を対応する上昇階乗冪で置き換えた

$\left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}$

として与えられる。

負の二項係数

任意の n に対して

${\begin{aligned}{\binom {-n}{k}}&={\frac {-n\cdot -(n+1)\dots -(n+k-2)\cdot -(n+k-1)}{k!}}\\&=(-1)^{k}\;{\frac {n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)}{k!}}\\&=(-1)^{k}{\binom {n+k-1}{k}}\\&=(-1)^{k}\left(\!\!{\binom {n}{k}}\!\!\right)\end{aligned}}$

が成り立つ。特に、負の整数における二項係数は符号付多重集合係数である。n = −1 なる特別の場合には、これは $(-1)^{k}={\tbinom {-1}{k}}={\big (}\!{\tbinom {-k}{k}}\!{\big )}$ と簡単になる。

両引数が実数または複素数の場合

ガンマ函数やベータ函数を用いて

${\binom {x}{y}}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (x-y+1,y+1)}}$

と書けば、二項係数の2つの引数を任意の実数または複素数まで一般化することができる。この定義においてガンマ函数の性質を用いれば、

${\binom {x}{y}}={\frac {\sin(y\pi )}{\sin(x\pi )}}{\binom {-y-1}{-x-1}}={\frac {\sin((x-y)\pi )}{\sin(x\pi )}}{\binom {y-x-1}{y}}$

が満たされることも分かる。特に

${\binom {x}{y}}\cdot {\binom {y}{x}}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}$

である。この一般化に関する研究は少ないが、(Fowler 1996) などにはすでに現れている。通常の二項係数に関する多くの等式がもはや成り立たなくなっていることに注意すべきである（例えば正の n に対して (n
m) = (n
n − m) や (− n
m) = (− n
− n − m) は一般には正しくない）。その挙動は極めて複雑で、x軸、y軸と直線 y = x で分けられる八分象限 (octant) のどの位置にあるかで著しく異なる。負の x に対しては負の整数の位置に特異点を持ち、正と負の領域が市松模様を成す:

• 0 ≤ y ≤ x なる八分象限では、通常の二項係数を滑らかに補間し、稜線を成す（「パスカルの稜線」("Pascal's ridge")）。
• 0 ≤ x ≤ y なる八分象限または x ≥ 0, y ≥ 0 なる四分象限では、函数は零に近い。
• x ≤ 0, y ≥ 0 なる四分象限では、四点 (−n, m + 1), (−n, m), (−n − 1, m − 1), (−n − 1, m) を頂点とする平行四辺形ごとに非常に大きな正の値と負の値を交互に取る。
• 0 > x > y なる八分象限では、やはり非常に大きな正の値と負の値を交互に取るが、今度は正方形の格子で起こる。
• −1 > y > x + 1 なる八分象限では、特異点の近くを除けば零に近い。

q-二項係数

二項係数の q-類似はガウスの二項係数と呼ばれる。

無限基数の二項係数

部分集合の数を数える二項係数の組合せ論的定義を、基数 α, β に対して濃度 α を持つ適当な集合 A をとって

${\binom {\alpha }{\beta }}=|\{B\subseteq A:|B|=\beta \}|$

の形に表せば、無限基数に対しても一般化できる。基数 α を表す集合 A の取り方に依らず (α
β ) が等しいという意味でこの一般化はうまく定義されている。有限基数に対してこれが通常の二項係数の定義に一致するのは明らかであろう。

選択公理を仮定すれば、任意の無限基数 α に対して (α
α) = 2^α が示せる。

関連項目

• 二項変換
• 中心二項係数
• クンマーの定理：二項係数の素冪因子に関する—
• リュカの定理
• パスカルの三角形における各数の重複度
• ダビデの星の定理
• 孫の奇妙な等式
• ニュートン級数の一覧
• 三項係数
• ポッホハマー記号

脚注

参考文献

• Ash, Robert B. (1990) [1965]. Information Theory. Dover Publications, Inc.. ISBN 0-486-66521-6. http://www.amazon.com/Information-Theory-Dover-Books-Mathematics/dp/0486665216 
• Benjamin, Arthur T.; Jennifer, Quinn (2003). Proofs that Really Count: The Art of Combinatorial Proof. Mathematical Association of America. ISBN 978-0-88385-333-7. https://www.maa.org/press/books/proofs-that-really-count-the-art-of-combinatorial-proof 
• Bryant, Victor (1993). Aspects of Combinatorics. Cambridge University Press. ISBN 0-521-41974-3 
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0 
• Fowler, David (1996-01). “The binomial coefficient function”. The American Mathematical Monthly (Mathematical Association of America) 103 (1): 1-17. doi:10.2307/2975209. JSTOR 2975209 
• Goetgheluck, P. (1987). “Computing binomial coefficients”. American Math. Monthly 94: 360-365. doi:10.2307/2323099. 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (Second ed.). Addison-Wesley. pp. 153-256. ISBN 0-201-55802-5 
• Higham, Nicholas J. (1998). Handbook of Writing for the Mathematical Sciences. SIAM. p. 25. ISBN 0-89871-420-6 
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Third ed.). Addison-Wesley. pp. 52-74. ISBN 0-201-89683-4 
• Singmaster, David (1974). “Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients”. Journal of the London Mathematical Society 8 (3): 555-560. doi:10.1112/jlms/s2-8.3.555. 
• Shilov, G. E. (1977). Linear Algebra. Dover Publications. ISBN 978-0-486-63518-7 

外部リンク

• 『二項係数の有名公式一覧と2つの証明方針』 - 高校数学の美しい物語
• 『二項係数の和，二乗和，三乗和』 - 高校数学の美しい物語

• Hazewinkel, Michiel, ed. (2001), “Binomial coefficients”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Binomial_coefficients 
• Andrew Granville (1997). “Arithmetic properties of binomial coefficients I. Binomial coefficients modulo prime powers”. CMS Conf. Proc 20: 151-162. http://www.cecm.sfu.ca/organics/papers/granville/Binomial/toppage.html. 

この記事は、クリエイティブ・コモンズ・ライセンス 表示-継承 3.0 非移植のもと提供されているオンライン数学辞典『PlanetMath』の以下の項目の本文を含む: Binomial Coefficient, Bounds for binomial coefficients, Proof that C(n,k) is an integer, Generalized binomial coefficients.