二項係数

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

数学における二項係数（にこうけいすう、テンプレート:Lang-en-short）は二項展開において係数として現れる正の整数の族である。二項係数は2つの非負整数で添字付けられ、添字テンプレート:Math2 を持つ二項係数はふつうテンプレート:Math とかテンプレート:Math と書かれる（これは二項冪テンプレート:Math の展開におけるテンプレート:Mvar の項の係数である。適当な仮定の下で、この係数の値は $\frac{n!}{k! (n - k)!}$ で与えられる）。二項係数を、連続する整数テンプレート:Mvar に対する各行にテンプレート:Mvar をテンプレート:Math からテンプレート:Mvar まで順に並べて得られる三角形状の数の並びをパスカルの三角形と呼ぶ。

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

歴史と記法

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

記号テンプレート:Math はテンプレート:仮リンクが1826年に導入したものである^[2]。そのほかの記法としてテンプレート:Math, テンプレート:Mvar, テンプレート:Mvar, テンプレート:Mvar, テンプレート:Mvar^[3], テンプレート:Math, テンプレート:Math などがあり、何れも文字 テンプレート:Mvar は組合せ (combination) や選択 (choice) を表している。

定義と解釈

自然数（テンプレート:Math も含める）テンプレート:Mvar およびテンプレート:Mvar に対し、二項係数テンプレート:Math は二項冪テンプレート:Math の展開におけるテンプレート:Mvar の項の係数として定義できる。同係数は（テンプレート:Math2のとき）二項公式テンプレート:NumBlk に現れるため「二項係数」の名がある（この式自体は環の互いに可換な任意の元テンプレート:Math に対して成り立つ）。

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

二項係数の値の計算

テンプレート:Math の値を、実際に二項冪を展開したりテンプレート:Mvar-組合せを数え上げたりせずに、計算する方法はいくつかある。

漸化式

一つは、テンプレート:Math2 をテンプレート:Math2 なる自然数として、純加法的な漸化式

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

を初期条件「任意のテンプレート:Math2 に対しテンプレート:Math2」の下で用いることである。

この漸化式自体は、集合テンプレート:Math2において以下のように場合を分けてテンプレート:Mvar元-集合を数えることで得られる。特定の元に注目し、ここではそれを “テンプレート:Mvar” とする。

(a) 特定の元テンプレート:Mvar を含むテンプレート:Mvar 個の元を集める。この場合、各集まりは既にテンプレート:Mvar があることは仮定しているから、残りのテンプレート:Math2 個の元をテンプレート:Mvar を除くテンプレート:Math2 元の中から特定すればよい。
(b) 特定の元テンプレート:Mvar を全く含まないテンプレート:Mvar 個の元を集める。この場合、テンプレート:Mvar を除くテンプレート:Math2 個の元からテンプレート:Mvar 個を選ぶことに他ならない。

この二者で与えられたテンプレート:Mvar 個の元から得られるすべてのテンプレート:Mvar-組合せが数え上げられているので所期の結果を得る。

あるいはまた、テンプレート:Math2 の両辺におけるテンプレート:Mvar への寄与を見ることでもこの漸化式は得られる。テンプレート:Math においてテンプレート:Math やテンプレート:Math の項は存在しない（あるいは係数が零である）から、二項係数の定義を上記の境界を越えて延長して、テンプレート:Math2 とすることもできる。

この漸化式はパスカルの三角形を描くのにも利用できる。

乗法表示

個々の二項係数をより効果的に計算するには

(\binom{n}{k}) = \frac{n^{\underline{k}}}{k!} = \frac{n (n - 1) (n - 2) \dots (n - (k - 1))}{k (k - 1) (k - 2) \dots 1} = \prod_{i = 1}^{k} \frac{n - (k - i)}{i} = \prod_{i = 1}^{k} \frac{n + 1 - i}{i}

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

階乗表示

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

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

で与えられる。ここにテンプレート:Math はテンプレート:Mvar の階乗である。この式は上記の乗法表示式に、分子分母に対してテンプレート:Math2 を掛けることで得られる（その結果、この式において分母と分子は多くの共通因数を持つことになる）。（特に階乗は非常に速く増加するから）この式を（テンプレート:Mvar が小さくテンプレート:Mvar が大きい場合に）実際の数値計算に用いることは（先に共通因数を約分しない限り）実用的でない。この式は上記の乗法表示よりは二項係数が対称性テンプレート:NumBlk を持つことを見るのに適している（二項係数の定義から対称性をもつことは分かる）。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば

(\binom{n}{k}) = {\begin{matrix} n^{\underline{k}} / k! & if k \leq \frac{n}{2} \\ n^{\underline{n - k}} / (n - k)! & if k > \frac{n}{2} \end{matrix}

と書ける。

一般化および二項級数

乗法表示を用いれば、テンプレート:Mvar を任意の数テンプレート:Mvar（負の整数、実数、複素数、……）あるいは任意の整数が可逆となるような可換環の元に取り換えて、

(\binom{α}{k}) = \frac{α^{\underline{k}}}{k!} = \frac{α (α - 1) (α - 2) \dots (α - k + 1)}{k (k - 1) (k - 2) \dots 1}

により二項係数の定義を拡張することができるテンプレート:Refnest。この定義により、二項定理（の一方の変数をテンプレート:Math としたもの）も一般化してテンプレート:NumBlk と書くことができる。故にこの場合もテンプレート:Math を二項係数と呼ぶことは正当化される。この等式は任意の複素数テンプレート:Mvar とテンプレート:Math2 なるテンプレート:Mvar に対して有効である。これはまたテンプレート:Mvar を不定元とする形式冪級数の等式としても解釈でき、それは実際に定数係数テンプレート:Math を持つ級数の任意の冪の定義として機能する。この定義を用いるポイントは、冪乗として満足することが期待される全ての恒等式（指数法則）、特に

$(1 + X)^{α} (1 + X)^{β} = (1 + X)^{α + β},$
$((1 + X)^{α})^{β} = (1 + X)^{α β}$

が満足されることである。テンプレート:Mvar が非負整数テンプレート:Mvar のとき、テンプレート:Math2 なる全ての項は零であり、上記の無限級数は有限和となり、したがってもともとの二項定理が再び得られる。しかしテンプレート:Mvar がそれ以外の値ならば、負の整数や有理数の場合も含めて、上記の級数は実際に無限和になる。

パスカルの三角形

テンプレート:Main テンプレート:仮リンクは重要な漸化式テンプレート:NumBlk で、これを用いてテンプレート:Math が任意の自然数テンプレート:Mvar に対して自然数となること（別な言い方をすれば、連続するテンプレート:Mvar-個の整数の積をテンプレート:Math が割り切ること）を帰納的に示すことができる。これは定義 (テンプレート:EquationNote) や乗法表示からは直ちに明らかなことではない。

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

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

番号テンプレート:Mvar の行にはテンプレート:Math の値がテンプレート:Math2 に対して並べられている。これを書くには、一番外側のテンプレート:Math から始めて、常に隣り合う２項を加えた数をその真下に書いていけばよい。この方法によって、分数や乗算を使わずに二項係数を手早く計算することができる。

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

テンプレート:Math2

が直ちに読み取れる。

他の対角線上の数との差は、上記漸化式 (テンプレート:EquationNote) の帰結として、一つ前の対角線上の数である。

解釈

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

テンプレート:Mvar-元集合からテンプレート:Mvar-元を選ぶ方法の総数はテンプレート:Math である（組合せを参照）。
テンプレート:Mvar-元集合から重複を許してテンプレート:Mvar元を選ぶ方法の総数はテンプレート:Math 通りある（多重集合を参照）。
テンプレート:Mvar 個のテンプレート:Math とテンプレート:Mvar 個のテンプレート:Math を含む文字列はテンプレート:Math 種類存在する。
テンプレート:Mvar 個のテンプレート:Math とテンプレート:Mvar 個のテンプレート:Math を含み、かつどの2つのテンプレート:Math も隣り合わない文字列の総数はテンプレート:Math である^[4]。
カタラン数：テンプレート:Math.
二項分布：テンプレート:Math.

多項式としての性質

テンプレート:Mvar を不定元として、任意の非負整数テンプレート:Mvar に対して式

(\binom{t}{k}) = \frac{(t)_{k}}{k!} = \frac{(t)_{k}}{(k)_{k}} = \frac{t (t - 1) (t - 2) \dots (t - k + 1)}{k (k - 1) (k - 2) \dots 2 \cdot 1}

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

各テンプレート:Mvar に対し、多項式テンプレート:Math はテンプレート:Math2 かつテンプレート:Math2 を満たす唯一のテンプレート:Mvar次多項式テンプレート:Math として特徴づけることができる。

この多項式の係数はテンプレート:仮リンクを用いて

(\binom{t}{k}) = \sum_{i = 0}^{k} [\binom{k}{i}] \frac{t^{i}}{k!}

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

\frac{d}{𝑑 𝑡} (\binom{t}{k}) = (\binom{t}{k}) \sum_{i = 0}^{k - 1} \frac{1}{t - i}

と計算できる。

多項式の空間の基底

標数テンプレート:Math の任意の体（すなわち、有理数体テンプレート:Math を含む体）上で、次数が高々テンプレート:Mvar の任意の多項式テンプレート:Math は二項係数の線型結合

p (t) = \sum_{k = 0}^{d} a_{k} (\binom{t}{k})

として一意に書ける。このときの係数テンプレート:Mvar は数列テンプレート:Math の[[有限差分|第テンプレート:Mvar-階差]]で与えられ、明示的に書けばテンプレート:NumBlk で決まる^{[注 1]}。

整数値多項式

テンプレート:Main 各二項係数多項式テンプレート:Math は整数値（整数を代入したとき必ず整数を返す）である（これは例えばテンプレート:仮リンクを用いてテンプレート:Mvar に関する帰納法で示せる）。従って、二項係数多項式の任意の整係数線型結合もまた整数値多項式になる。逆に等式 (テンプレート:EquationNote) により任意の整数値多項式がこれら二項係数多項式の正係数線型結合となることが示せる。より一般に標数テンプレート:Math の体の任意の部分環テンプレート:Mvar に対し、テンプレート:Math に属する多項式が任意の整数においてテンプレート:Mvar に値をとるための必要十分条件はそれが二項係数多項式のテンプレート:Mvar-係数線型結合となっていることである。

二項係数に関する等式

階乗表示を用いれば近くにある二項係数の関係を容易に知ることができる。例えばテンプレート:Mvar を正整数、テンプレート:Mvar は任意としてテンプレート:NumBlk が成り立ち、また少しの計算で

(\binom{n - 1}{k}) - (\binom{n - 1}{k - 1}) = \frac{n - 2 k}{n} (\binom{n}{k})

が得られる。さらに言えば以下の結果

(\binom{n}{h}) (\binom{n - h}{k}) = (\binom{n}{k}) (\binom{n - k}{h})

は有用である。例えば定数テンプレート:Mvar に対して以下の漸化式

(\binom{n}{k}) = \frac{n + 1 - k}{k} (\binom{n}{k - 1})

を得ることができる。

二項係数を含む級数

等式テンプレート:NumBlk は等式 (テンプレート:EquationNote) においてテンプレート:Math2 かつテンプレート:Math2 とすれば得られる。これはパスカルの三角形の各行において現れる全ての数を足し合わせれば[[2の冪| テンプレート:Math の整数冪]]になると言っても同じである。この事実の組合せ論的解釈はテンプレート:仮リンク (double counting) でテンプレート:Mvar元-集合テンプレート:Mvar の位数テンプレート:Mvar テンプレート:Math2 の部分集合を数えることである。任意の位数テンプレート:Mvar に対する部分集合を数えているのだから、その和はテンプレート:Mvar の部分集合の総数に等しく、それがテンプレート:Math であることはよく知られている。すなわち、等式 (テンプレート:EquationNote) は [[有限集合|テンプレート:Mvar元-集合]]の冪集合の位数がテンプレート:Math であることを述べるものである。より明確に、テンプレート:Mvar-桁のビット列を考えれば、このビット列はテンプレート:Math 個の数を表すことに利用できる。その中で一つもテンプレート:Math を含まないビット列を考えれば、これはテンプレート:Math2 通りである。ちょうど一つテンプレート:Math を含むビット列はテンプレート:Math2 通りである。このように数えて行けば上記の式を得る。

等式テンプレート:NumBlk および

\sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = (n + n^{2}) 2^{n - 2}

は等式 (テンプレート:EquationNote) をテンプレート:Mvar に関して（後者は2回）微分してテンプレート:Math2 と置けば得られる。

テンプレート:仮リンクテンプレート:NumBlk は任意の複素数テンプレート:Math2 と任意の非負整数テンプレート:Mvar に対して成立する。これはテンプレート:Math2 の展開におけるテンプレート:Mvar の係数として、等式 (テンプレート:EquationNote) を用いて求めることができる。テンプレート:Math のとき等式 (テンプレート:EquationNote) は等式 (テンプレート:EquationNote) に簡約される。

任意の整数テンプレート:Math2 に対して適用できる同様の等式テンプレート:NumBlk は、 $\frac{x^{l}}{(1 - x)^{l + 1}} = \sum_{p = 0}^{\infty} (\binom{p}{l}) x^{p}$ を用いれば

x (\frac{x^{j}}{(1 - x)^{j + 1}}) (\frac{x^{k - j}}{(1 - x)^{k - j + 1}}) = \frac{x^{k + 1}}{(1 - x)^{k + 2}}

の展開におけるテンプレート:Math の係数として求められる。テンプレート:Math2 のとき等式 (テンプレート:EquationNote) は

\sum_{m = 0}^{n} (\binom{m}{k}) = (\binom{n + 1}{k + 1})

となる。展開 (テンプレート:EquationNote) をテンプレート:Math2 に対して用い、(テンプレート:EquationNote) を使えばテンプレート:NumBlk を得る。

テンプレート:Math でテンプレート:Mvar 番目のフィボナッチ数を表せば、パスカルの三角形の対角和に関する等式テンプレート:NumBlk を得る。これは等式 (テンプレート:EquationNote) を用いた帰納法、あるいはゼッケンドルフの表現によって示すことができる（左辺はテンプレート:Math2の連続した元を含まない部分集合の総数を与えるものであり、そのようなものはまたテンプレート:Math 以下の数の全体を成すということに他ならないことに注意）。組合せ論的証明は後述。

等式 (テンプレート:EquationNote) から従う別の等式として、テンプレート:Math とおいてテンプレート:Math2 を得る。

テンプレート:Math2 に対する閉じた式は（超幾何函数を用いなければ）ない^[5]が、再び等式 (テンプレート:EquationNote) および帰納法によりテンプレート:Math2 に対してテンプレート:Math2 を得る。同様にテンプレート:Math2 を得る^[6]（テンプレート:Math2 の自明な場合は除く。このときはテンプレート:Math になる）。これ自身は次数高々テンプレート:Mvar の任意の多項式テンプレート:Math2 に対する和分差分学における結果^[7]テンプレート:Math2 の特別の場合である。テンプレート:Math2 に対しては等式 (テンプレート:EquationNote) をテンプレート:Mvar 回微分してテンプレート:Math2 と置けば得られる。一般の場合はこれらの線型結合を作ればよい。

テンプレート:Mvar次以下の多項式テンプレート:Math2 に対してテンプレート:NumBlk が成り立つ。ここでテンプレート:Mvar はテンプレート:Math2 のテンプレート:Mvar次係数である。等式 (テンプレート:EquationNote) はより一般に、複素数テンプレート:Math2 に対して

\sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) P (m + (n - j) d) = d^{n} n! a_{n}

とできる。これはテンプレート:Math2 の代わりに多項式テンプレート:Math2 とするとき、テンプレート:Math2 がやはりテンプレート:Mvar次以下の多項式であることとテンプレート:Mvar次係数がテンプレート:Math2 であることに注意すれば、等式 (テンプレート:EquationNote) を適用して直ちに得られる。

級数

\frac{k - 1}{k} \sum_{j = 0}^{\infty} \frac{1}{(\binom{j + x}{k})} = \frac{1}{(\binom{x - 1}{k - 1})}

はテンプレート:Math2 に対して収束する。この等式はテンプレート:仮リンクを調べるのに利用できる。これを見るには

\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})}

が成り立つことをテンプレート:Mvar に関する帰納法で示せばよい。

等式 (テンプレート:EquationNote) からテンプレート:Math2 およびテンプレート:Math が得られる。

テンプレート:仮リンクにより、テンプレート:Math2 としてテンプレート:Mvar を境にテンプレート:Mvar 刻みに取った二項係数の総和とテンプレート:Mvar 項の閉じた形の式の和との間の等式

(\binom{n}{t}) + (\binom{n}{t + s}) + (\binom{n}{t + 2 s}) + \dots = \frac{1}{s} \sum_{j = 0}^{s - 1} {(2 \cos \frac{π j}{s})}^{n} \cos \frac{π (n - 2 t) j}{s}

が示せる。

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

二項係数を含む多くの等式がテンプレート:仮リンク証明することができる。例えばテンプレート:Math2 なる非負整数に対して

\sum_{k = q}^{n} (\binom{n}{k}) (\binom{k}{q}) = 2^{n - q} (\binom{n}{q})

（テンプレート:Math2 のとき (テンプレート:EquationNote) に簡約される）は、以下のようにテンプレート:仮リンクできる。左辺は集合テンプレート:Math2の少なくともテンプレート:Mvar 個の元を含む部分集合を選び、選ばれた元のうちテンプレート:Mvar 個に印をつける方法を数えている。右辺も同じものを数えるのだけれども、テンプレート:Mvar 個の元のうちテンプレート:Mvar 個に印をつける方法がテンプレート:Math 通りあり、その各々について印をつけたテンプレート:Mvar 個を含む部分集合を得るには印の付いたテンプレート:Mvar 個に残りのテンプレート:Math2 個の元から任意に追加すればよいから、そのような仕方はテンプレート:Math 通りである。

パスカルの法則

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

の両辺は集合テンプレート:Math のテンプレート:Mvar元-部分集合を数えているのだけれども、右辺は特定の元（例えばテンプレート:Mvar）を含むように選ぶ場合と含まないように選ぶ場合に分けて数えている。

等式 (テンプレート:EquationNote), 再掲すると

\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})

も組合せ論的に証明できる。テンプレート:Math 個の□を一列に並べ、それらのうちのテンプレート:Mvar 個を選んで印を付けることを考える。そのような方法はテンプレート:Math 通りである（右辺）。他方、そのようなテンプレート:Mvar 個の□を選ぶときに、テンプレート:Mvar 個は前半のテンプレート:Mvar 個から、残りテンプレート:Math2 個は後半のテンプレート:Mvar 個から選ぶとしてテンプレート:Math2 に亙って考える。これによりテンプレート:Math2 が得られるから、等式 (テンプレート:EquationNote) を適用して所期の結果を得る。

2次元格子上の経路の例

等式 (テンプレート:EquationNote) も組合せ論的に証明できる。テンプレート:Math は、2次元格子上でテンプレート:Math2 からテンプレート:Math2 まで、テンプレート:Math またはテンプレート:Math2 刻みで移動して辿った経路の総数を表す。そのことは全部でテンプレート:Math2 個の点を亙るために必ずちょうどテンプレート:Mvar 回だけテンプレート:Math2 刻みの移動をしなければならないのだから明らかである。さてここでちょうどテンプレート:Mvar 個あるテンプレート:Math2 刻みをテンプレート:Math2 刻みで置き換えると、テンプレート:Math2 刻みとテンプレート:Math2 刻みを合わせてテンプレート:Math へ到達することになる。これをテンプレート:Math2 なる各テンプレート:Mvar に亙って考えれば、テンプレート:Math2 からテンプレート:Math2 刻みとテンプレート:Math2 刻みを合わせてテンプレート:Math へ到達する方法の総数が数え上げられる。そのような方法の総数がテンプレート:Math2 通りあることは明らかである。

ディクソンの等式

テンプレート:仮リンクは

\sum_{k = - a}^{a} (- 1)^{k} {(\binom{2 a}{k + a})}^{3} = \frac{(3 a)!}{(a!)^{3}}

あるいはより一般に

\sum_{k = - a}^{a} (- 1)^{k} (\binom{a + b}{a + k}) (\binom{b + c}{b + k}) (\binom{c + a}{c + k}) = \frac{(a + b + c)!}{a! b! c!}

で与えられる。ここにテンプレート:Math2 は非負整数である。

連続等式

ある種の三角積分は二項係数で表される値を持つ。テンプレート:Math2 を非負整数として:

$\int_{- π}^{π} \cos ((2 m - n) x) \cos^{n} x d x = \frac{π}{2^{n - 1}} (\binom{n}{m})$
$\int_{- π}^{π} \sin ((2 m - n) x) \sin^{n} x d x = {\begin{matrix} (- 1)^{m + \frac{n + 1}{2}} \frac{π}{2^{n - 1}} (\binom{n}{m}) & (n : odd) \\ 0 & (otherwise) \end{matrix}$
$\int_{- π}^{π} \cos ((2 m - n) x) \sin^{n} x d x = {\begin{matrix} (- 1)^{m + \frac{n + 1}{2}} \frac{π}{2^{n - 1}} (\binom{n}{m}) & (n : even) \\ 0 & (otherwise) \end{matrix}$

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

母函数

通常母函数

固定したテンプレート:Mvar に対して作られる数列テンプレート:Math2 の通常母函数は

\sum_{k = 0}^{\infty} (\binom{n}{k}) x^{k} = (1 + x)^{n}

で与えられる。固定したテンプレート:Mvar に対して作られる数列テンプレート:Math2 の通常母函数は

\sum_{n = k}^{\infty} (\binom{n}{k}) y^{n} = \frac{y^{k}}{(1 - y)^{k + 1}}

である。一般の非負整数テンプレート:Math2 に対する二項係数のテンプレート:仮リンクは

\sum_{n, k} (\binom{n}{k}) x^{k} y^{n} = \frac{1}{1 - y - x y}

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

\sum_{n, k} (\binom{n + k}{k}) x^{k} y^{n} = \frac{1}{1 - x - y}

で与えられる。

指数型母函数

二項係数に関するテンプレート:仮リンクは

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

となる。

可除性

テンプレート:Main 1852年、クンマーは非負整数テンプレート:Mvar および素数テンプレート:Mvar に対し、テンプレート:Math を整除する最大のテンプレート:Mvar-冪がテンプレート:Mvar であるとき、テンプレート:Mvar はテンプレート:Mvar とテンプレート:Mvar を加えるときに生じるテンプレート:Mvar-進表示における繰り上がりの数に等しいことを示したテンプレート:Sfn。同じことだが、テンプレート:Math における素因子テンプレート:Mvar の冪指数はテンプレート:Math のテンプレート:仮リンクがテンプレート:Math の小数部よりも大きくなるような非負整数テンプレート:Mvar の総数に等しい。これにより、テンプレート:Math がテンプレート:Math で割り切れることが導かれる。したがって特に、任意の正整数テンプレート:Mvar およびテンプレート:Math2 なる正整数テンプレート:Mvar に対してテンプレート:Mvar はテンプレート:Math を割り切る。しかしより高次のテンプレート:Mvar-冪に対してこれは正しくない（例えばテンプレート:Math はテンプレート:Math を割り切らない）。

テンプレート:Harvtxt は「任意の整数がほとんど全ての二項係数を整除する」という幾分驚くべき結果を与えた。より精確に言えば、整数テンプレート:Mvar を固定して、テンプレート:Math2 はテンプレート:Math2 なる二項係数テンプレート:Math のうちテンプレート:Mvar で割り切れるものの総数を表すものとすると、

\lim_{N \to \infty} \frac{f (N)}{N (N + 1) / 2} = 1

が成り立つというものである。テンプレート:Math2 なる二項係数テンプレート:Math の総数はテンプレート:Math であるから、これはテンプレート:Mvar で整除可能なものの占める密度がテンプレート:Math に収束することを意味する。

別の事実として、整数テンプレート:Math2 が素数となる必要十分条件は、中間二項係数

(\binom{n}{1}), (\binom{n}{2}), \dots, (\binom{n}{n - 1})

の全てがテンプレート:Mvar で整除可能なことである。実際、テンプレート:Mvar が素数ならば、テンプレート:Math2 なる任意のテンプレート:Mvar に対してテンプレート:Mvar は

(\binom{p}{k}) = \frac{p \cdot (p - 1) \dots (p - k + 1)}{k \cdot (k - 1) \dots 1}

を割り切る。これは分子は素因数テンプレート:Mvar を含むが分母はテンプレート:Mvar を素因数に持たないことによる。テンプレート:Mvar が合成数のとき、テンプレート:Mvar をテンプレート:Mvar を割り切る最小の素因数とし、テンプレート:Math2 と置けば、テンプレート:Math かつ

(\binom{n}{p}) = \frac{n (n - 1) (n - 2) \dots (n - p + 1)}{p!} = \frac{k (n - 1) (n - 2) \dots (n - p + 1)}{(p - 1)!}

はテンプレート:Mvar で割り切れない。仮に割り切れるとすると分子テンプレート:Math2 がテンプレート:Math で割り切れることになり、それはテンプレート:Math がテンプレート:Mvar で割り切れる場合しかありえないが、テンプレート:Mvar はテンプレート:Mvar で割り切れるのだから、テンプレート:Mvar はテンプレート:Math2 を割り切らず、テンプレート:Mvar は素数だから従ってテンプレート:Math2 も割り切らず、それゆえ分子がテンプレート:Mvar で割り切られることもない。

上界・下界と漸近公式

テンプレート:Math に関して以下の評価

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

がテンプレート:Math2 に対して成立する。スターリングの近似からはテンプレート:Math, 一般に

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

がテンプレート:Math2 かつテンプレート:Math2 に対して成立する。またテンプレート:Math2 のとき近似

(\binom{2 n}{n}) \sim \frac{4^{n}}{\sqrt{π n}}

が成り立つ。テンプレート:Math2 がともに 1 より十分大きければスターリング近似からは以下の漸近近似

\log_{2} (\binom{n}{k}) \sim n H (\frac{k}{n})

も従う。ここにテンプレート:Math2 はテンプレート:Math の二値エントロピー関数である。より精確に、任意の整数テンプレート:Math2 とテンプレート:Math2 に対して、最初のテンプレート:Math2 個の二項係数の和を

\frac{1}{\sqrt{8 n ϵ (1 - ϵ)}} \cdot 2^{H (ϵ) \cdot n} \leq \sum_{i = 0}^{k} (\binom{n}{i}) \leq 2^{H (ϵ) \cdot n}

と評価することができる^[8]。

テンプレート:Mvar が大きく、テンプレート:Mvar がテンプレート:Mvar に対して十分小さいとき $(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k!} \approx \frac{(n - k / 2)^{k}}{k^{k} e^{- k} \sqrt{2 π k}} = \frac{(n / k - 0.5)^{k} e^{k}}{\sqrt{2 π k}}$ と書くことができるので、

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

を得る。より精度を望むならば、テンプレート:Math2 を積分で近似して

\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 π k)

となる。テンプレート:Math2 かつテンプレート:Math2 に対してテンプレート:Math2 およびこれら近似式からそれぞれ近似値テンプレート:Math2 およびテンプレート:Math2 を得る。

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

(- 1)^{k} (\binom{z}{k}) = (\binom{- z + k - 1}{k}) = \frac{1}{Γ (- 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}}{Γ (- z) k^{z + 1}}, (\binom{z + k}{k}) = \frac{k^{z}}{Γ (z + 1)} (1 + \frac{z (z + 1)}{2 k} + 𝒪 (k^{- 2}))

がテンプレート:Math2 で成り立つ。この漸近挙動は近似

(\binom{z + k}{k}) \approx \frac{e^{z (H_{k} - γ)}}{Γ (z + 1)}

にも表れている。ここに、テンプレート:Mvar はテンプレート:Mvar番目の調和数で、テンプレート:Math はオイラー–マスケローニ定数である。さらに、テンプレート:Math2 かつ適当な複素数テンプレート:Mvar に対してテンプレート:Math2 なるとき、漸近公式

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

が成り立つ。

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

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

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

近似

テンプレート:Mvar が十分大きいとき、

(\binom{n}{k}) = \frac{2^{n}}{\sqrt{\frac{1}{2} n π}} e^{- \frac{(k - (n / 2))^{2}}{n / 2}} [1 + O (\frac{1}{\sqrt{n}})]

は二項係数と正規分布との関係に基づく近似を与える。これは、二項分布と等しい期待値と分散テンプレート:Math2 を持つ正規分布をとり、テンプレート:Math2 として、テンプレート:Math を掛ければ、中心極限定理に対する評価から従う。

一般化

多項への一般化

テンプレート:Main 二項係数を一般化するものとして

(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{r}!} (\sum_{i = 1}^{r} k_{i} = n)

で定義される数を多項係数と呼ぶ。二項係数がテンプレート:Math の係数であったのに対し、多項係数はテンプレート:Math2 の多項式展開の係数であり、テンプレート:Math2 のとき二項係数を与える:

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

多項係数は、区別可能なテンプレート:Mvar 個の元をテンプレート:Mvar 個の箱に分けて入れるとき、箱の番号テンプレート:Math2 に対して各箱がちょうどテンプレート:Mvar 個の元を含むような分け方の総数として組合せ論的に解釈できる。

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

(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = (\binom{n - 1}{k_{1} - 1, k_{2}, \dots, k_{r}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, \dots, k_{r}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, \dots, k_{r} - 1})

および任意の置換テンプレート:Mvar に関する対称性

(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = (\binom{n}{k_{σ_{1}}, k_{σ_{2}}, \dots, k_{σ_{r}}})

が挙げられる。ただし、テンプレート:Math はテンプレート:Math2 を並べ替えたものである。

テイラー級数

テンプレート:仮リンクを用いれば、二項係数の任意に選んだ点テンプレート:Math の周りでのテイラー展開は

\begin{matrix} (\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{matrix}

と与えられる。

半整数に対する二項係数

二項係数の定義（積による表示）はテンプレート:Mvar が実数、テンプレート:Mvar が整数の場合にも意味を持つ。特にテンプレート:Math2 のとき任意の非負整数テンプレート:Mvar に対して

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

が成り立つ。これは二項級数展開テンプレート:Math2 に現れる。

二項係数の積

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

(\binom{z}{m}) (\binom{z}{n}) = \sum_{k = 0}^{m} (\binom{m + n - k}{k, m - k, n - k}) (\binom{z}{m + n - k})

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

部分分数分解

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

\frac{1}{(\binom{z}{n})} = \sum_{i = 0}^{n - 1} (- 1)^{n - 1 - i} (\binom{n}{i}) \frac{n - i}{z - i}

および

\frac{1}{(\binom{z + n}{n})} = \sum_{i = 1}^{n} (- 1)^{i - 1} (\binom{n}{i}) \frac{i}{z + i}

で与えられる。

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

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

(1 + z)^{α} = \sum_{n = 0}^{\infty} (\binom{α}{n}) z^{n} = 1 + (\binom{α}{1}) z + (\binom{α}{2}) z^{2} + \dots

である。これが成り立つことは両辺が微分方程式テンプレート:Math2 を満たすことを見ればよい。

この級数の収束半径はテンプレート:Math である。

\frac{1}{(1 - z)^{α + 1}} = \sum_{n = 0}^{\infty} (\binom{n + α}{n}) z^{n}

とも書ける。

上昇版二項係数

テンプレート:Main 二項係数は与えられた集合から決められた位数の部分集合を数え上げるものであった。関連する組合せ論的問題として、与えられた集合から元をとって作られる決められた位数の多重集合を数え上げる問題、すなわち与えられた集合から重複を許して決められた数の元を選び出す重複組合せの問題がある。その総数は多重集合係数と呼ばれ^[9]、テンプレート:Mvar 個の元からテンプレート:Mvar 個選ぶ重複組合せの総数は $((\binom{n}{k}))$ と書かれる。

以下議論の便宜のためテンプレート:Mvar を使わずに、その代わりテンプレート:Math2 およびテンプレート:Math2 なる非負整数テンプレート:Math2 を用いる。

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

(\binom{f}{k}) = ((\binom{r}{k})) = (\binom{r + k - 1}{k})

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

\begin{matrix} (f)_{k} & = f^{\underline{k}} = (f - k + 1) \dots (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) \dots (r + k - 1) \end{matrix}

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

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

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

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

として与えられる。

負の二項係数

任意のテンプレート:Mvar に対して

\begin{matrix} (\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) \dots (n + k - 1)}{k!} \\ = (- 1)^{k} (\binom{n + k - 1}{k}) \\ = (- 1)^{k} ((\binom{n}{k})) \end{matrix}

が成り立つ。特に、負の整数における二項係数は符号付多重集合係数である。テンプレート:Math なる特別の場合には、これは $(- 1)^{k} = (\binom{- 1}{k}) = ((\binom{- k}{k}))$ と簡単になる。

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

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

(\binom{x}{y}) = \frac{Γ (x + 1)}{Γ (y + 1) Γ (x - y + 1)} = \frac{1}{(x + 1) B (x - y + 1, y + 1)}

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

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

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

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

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

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

テンプレート:Mvar-二項係数

二項係数の[[q-類似| テンプレート:Mvar-類似]]はテンプレート:仮リンクと呼ばれる。

無限基数の二項係数

部分集合の数を数える二項係数の組合せ論的定義を、基数テンプレート:Mvar に対して濃度テンプレート:Mvar を持つ適当な集合テンプレート:Mvar をとって

(\binom{α}{β}) = | {B \subseteq A : | B | = β} |

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

選択公理を仮定すれば、任意の無限基数テンプレート:Mvar に対してテンプレート:Math2 が示せる。

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist2

出典

テンプレート:Reflist

参考文献

テンプレート:Refbegin

テンプレート:Refend

外部リンク

テンプレート:PlanetMath attribution

↑ Lilavati Section 6, Chapter 4 (see テンプレート:Harvtxt).
↑ テンプレート:Harvtxt
↑ テンプレート:Harvtxt
↑ テンプレート:Cite journal
↑ テンプレート:Citation.
↑ see induction developed in eq (7) p.1389 in テンプレート:Citation.
↑ テンプレート:Cite journal
↑ see e.g. テンプレート:Harvtxt or テンプレート:Harvtxt.
↑ テンプレート:Citation.

引用エラー: 「注」という名前のグループの <ref> タグがありますが、対応する <references group="注"/> タグが見つかりません

[1] Lilavati Section 6, Chapter 4 (see テンプレート:Harvtxt).

[2] テンプレート:Harvtxt

[3] テンプレート:Harvtxt

[4] テンプレート:Cite journal

[6] テンプレート:Citation.

[7] see induction developed in eq (7) p.1389 in テンプレート:Citation.

[8] テンプレート:Cite journal

[9] see e.g. テンプレート:Harvtxt or テンプレート:Harvtxt.

[10] テンプレート:Citation.

[1]

[2]

[3]

[4]

[注 1]

[5]

[6]

[7]

[8]

[9]

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

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