二項係数

Number of subsets of a given size

二項係数はパスカルの三角形を形成するように配置することができ、その三角形の各要素はすぐ上の 2 つの要素の合計になります。

4乗までの二項式展開の可視化

数学において、二項係数は二項定理の係数として現れる正の整数である。一般的に、二項係数は整数のペアn ≥ k ≥ 0で添え字が付けられ、次のように表記される。これは二項式べき乗(1 + x ) ⁿの多項式展開におけるx ^k項の係数である。この係数は乗法公式によって計算できる。 ${\displaystyle {\tbinom {n}{k}}.}$

$${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}},}$$

これは階乗表記法を使うと次のように簡潔に表現できる。

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

たとえば、1 + xの 4 乗は、二項係数はx ²項の係数です。 $${\displaystyle {\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}}$$ ${\displaystyle {\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6}$

n = 0, 1, 2, ...の数字を連続する行に並べると、パスカルの三角形と呼ばれる三角形の配列が得られ、これは再帰関係を満たす。 ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}$ $${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}.}$$

二項係数は数学の多くの分野で用いられますが、特に組合せ論において顕著です。組合せ論において、この記号は通常「 n choose k 」と読みます。これは、 n個の要素からなる固定された集合から、 k個の要素からなる（順序付けされていない）部分集合を選択する方法が存在するためです。例えば、{1, 2, 3, 4}から2個の要素を選択する方法、すなわち{1, 2 }、{1, 3}、 {1, 4} 、{2, 3}、{2, 4}、{3, 4}があります。 ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {4}{2}}=6}$

二項係数の最初の形式は、任意の複素数zと整数k ≥ 0に対してに一般化することができ、その特性の多くは、このより一般的な形式でも維持されます。 ${\displaystyle {\tbinom {z}{k}}}$

歴史と表記

アンドレアス・フォン・エッティングスハウゼンは1826年にこの記法を導入したが^[1] 、この数は数世紀前から知られていた（パスカルの三角形を参照）。1150年頃、インドの数学者バースカラチャルヤは著書『リーラーヴァティー』^{の中で二項係数の解説を行った[2]}。 ${\displaystyle {\tbinom {n}{k}}}$

代替表記法としては、 C ( n , k )、_n C _k、ⁿ C _k、Cなどがある。^k
_n, ^[3] Cⁿ
_k、C _{n , k}などがあり、いずれの場合もCは組み合わせまたは選択肢を表します。C表記は、 n個の対象からk 個を選ぶ方法の数を表します。多くの計算機は、 C表記の変形を使用しています。これは、 C表記を 1 行で表示できるためです。この形式では、二項係数は、P ( n , k )などと表記されるnのk個の順列の数と簡単に比較できます。

定義と解釈

け n	0	1	2	3	4	⋯
0	1	0	0	0	0	⋯
1	1	1	0	0	0	⋯
2	1	2	1	0	0	⋯
3	1	3	3	1	0	⋯
4	1	4	6	4	1	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋱
左揃えのパスカルの三角形の最初のいくつかの二項係数

自然数（0を含む）nとkに対して、二項係数は単項式X ^kの（1 + X）ⁿの展開における係数として定義できます。同じ係数は、（k ≤ nの場合）二項式にも現れます。 ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n-k}}$

∗

(可換環の任意の元x、yに有効)、これが「二項係数」という名前の由来です。

この数は組合せ論でも用いられ、順序を無視して、 n個のオブジェクトからk個のオブジェクトを選ぶ方法の数を表します。より正式には、 n要素の集合のk要素サブセット（またはk個の組み合わせ）の数です。この数は、以下の計算式に関わらず、最初の定義の数と等しいと見なすことができます。(1 + X ) ⁿ乗のn因数のそれぞれにおいて、項Xに一時的にインデックスi（1からnまで）のラベルを付けると、 k個のインデックスの各サブセットは展開後に寄与X ^kを与え、結果の単項式の係数はそのようなサブセットの数になります。これは特に、任意の自然数nおよびkに対して が自然数であることを示しています。二項係数（答えが二項係数式で与えられる問題を数える問題）には、他にも多くの組み合わせの解釈があります。例えば、nビット（数字0または1）で構成される語の合計がkである語の数は で与えられ、すべてのa _iが非負の整数である場合の書き方の数は⁠ ⁠で与えられます。これらの解釈のほとんどは、 kの組み合わせを数えることと同等であることが示されます。 ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}}$ ${\displaystyle {\tbinom {n+k-1}{n-1}}}$

二項係数の値を計算する

実際に二項式の累乗を展開したり、k の組み合わせ を数えたりせずにの値を計算する方法はいくつかあります。 ${\displaystyle {\tbinom {n}{k}}}$

再帰式

1 つの方法では、すべての整数に対して再帰的で純粋な加法的な式を使用し、すべての整数n ≥ 0の境界値を 使用します。 $${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$$ ${\displaystyle n,k}$ ${\displaystyle 1\leq k<n,}$ $${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$$

この式は、集合{1, 2, 3, ..., n }を考察し、(a)各グループに特定の集合要素、たとえば「 i 」を含むk要素のグループ(「 i」は各グループの 1 つの場所を埋めるために既に選択されているため、残りのn − 1からk − 1 を選択するだけでよい) と (b) 「 i 」を含まないすべてのkグループを別々に数えることで得られます。これにより、 n個の要素の可能なk の組み合わせがすべて列挙されます。また、 (1 + X ) ^{n −1} (1 + X )におけるX ^kへの寄与をトレースすることでも得られます。 (1 + X ) ⁿには0 のX ^{n +1}またはX ⁻¹があるため、上記の境界を超えて定義を拡張し、k > nまたはk < 0の場合を含めることができます。この再帰式により、0 または自明な係数があるはずの白いスペースで囲まれたパスカルの三角形を構築できます。 ${\displaystyle {\tbinom {n}{k}}=0}$

乗法式

個々の二項係数をより効率的に計算する方法は、式 で与えられます。ここで、最初の分数の分子は階乗です。この式は、二項係数の組み合わせ論的解釈において最も理解しやすいものです。分子は、n個のオブジェクトの集合から、選択順序を維持しながらk 個の異なるオブジェクトのシーケンスを選択する方法の数を示します。分母は、順序を無視した場合に同じk 個の組み合わせを定義する異なるシーケンスの数を数えます。この式は再帰形式でも表すことができます。上記の「C」表記法を用いると、となります。ここで です。これは、 を評価することで容易に導き出され、パスカルの三角形の - 行目の左端の係数（値は常に）から始めて、 - 番目に達するまでその右隣の係数を再帰的に計算するものとして直感的に理解できます。 $${\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}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},}$$ ${\displaystyle n^{\underline {k}}}$ ${\displaystyle C_{n,k}=C_{n,k-1}\cdot (n-k+1)/k}$ ${\displaystyle C_{n,0}=1}$ ${\displaystyle C_{n,k}/C_{n,k-1}}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle k}$

kとn − kに関する二項係数の対称性により、上記の積の計算および再帰関係は、その上限をkとn − kの小さい方に設定することによって最適化できます。

階乗の式

最後に、計算上は不向きだが、証明や導出でよく使われる簡略形がある。これは階乗関数を繰り返し用いるもので、ここでn !はnの階乗を表す。この式は、上記の乗法式から分子と分母に( n − k )!を乗じることで得られる。結果として、分子と分母に共通する因数が多数含まれる。kが小さくnが大きい場合、共通因数を最初に消去しない限り、明示的な計算には適さない（特に階乗値が急速に増加するため）。この式は、乗法式からは明らかではない対称性を示す（定義からは明らかであるが）。 $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}$$

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}\quad {\text{for }}\ 0\leq k\leq n,}$

1

これにより、より効率的な乗法計算ルーチンが実現されます。階乗降記法を用いると、 $${\displaystyle {\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を任意の数α（負、実、複素）またはすべての正の整数が逆である任意の可換環の元に置き換えることによって、^二項係数の定義を拡張することを可能にする[4]。 $${\displaystyle {\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}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .}$$

この定義により、二項式の一般化（変数の1つを1に設定）が得られ、依然として二項係数を呼び出すことが正当化されます。 ${\displaystyle {\tbinom {\alpha }{k}}}$

${\displaystyle (1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.}$

2

この式は、| X | < 1を満たすすべての複素数αとXに対して有効です。また、Xの形式的な冪級数の恒等式として解釈することもできます。これは、定数係数が1である任意の冪級数の定義として機能します。重要な点は、この定義により、特に指数に対して期待されるすべての恒等式が成り立つことです。 $${\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.}$$

αが非負整数nの場合、k > nとなる項はすべてゼロとなり、^[5]無限級数は有限和となり、二項式が復元されます。しかし、負の整数や有理数など、 αの他の値の場合、級数は実際には無限です。

パスカルの三角形

パスカルの三角形の1000行目を垂直に並べ、係数の小数点以下の数字をグレースケールで右揃えで表示しています。画像の左端は、二項係数の対数グラフにほぼ対応しており、それらが対数凹列を形成していることを示しています。

パスカルの法則は重要な再帰関係である

${\displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1},}$

3

これを用いて数学的帰納法によって、 n ≥ 0 およびk ≥ 0 の任意の整数に対して が自然数であることを証明することができるが、この事実は式(1)からはすぐには明らかではない。パスカルの三角形の左右の要素（空白で示されている）はすべてゼロである。 ${\displaystyle {\tbinom {n}{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行目には、 k = 0, …, nの数が入ります。これは、まず外側の位置に1を置き、内側の各位置にその上の2つの数の和を置くことで構成されます。この方法により、分数や掛け算を必要とせずに二項係数を素早く計算できます。例えば、三角形の5行目を見れば、次の式がすぐに読み取れます。 ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle (x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.}$

組合せ論と統計

二項係数は、特定の頻繁に発生する計数問題に対してすぐに使える公式を提供するため、組み合わせ論において重要です。

• n個の要素の集合からk個の要素を選択する方法はいくつかあります。組み合わせを参照してください。 ${\displaystyle {\tbinom {n}{k}}}$
• 繰り返しが許されている場合、 n個の要素の集合からk個の要素を選択する方法はいくつかあります。Multisetを参照してください。 ${\displaystyle {\tbinom {n+k-1}{k}}}$
• k個の 1 とn個の 0 を含む文字列があります。 ${\displaystyle {\tbinom {n+k}{k}}}$
• k個の1とn個の0からなる文字列があり、2つの1が隣接していない。^[6] ${\displaystyle {\tbinom {n+1}{k}}}$
• カタルーニャ数字は ${\displaystyle {\tfrac {1}{n+1}}{\tbinom {2n}{n}}.}$
• 統計学における二項分布は ${\displaystyle {\tbinom {n}{k}}p^{k}(1-p)^{n-k}.}$

二項係数を多項式として

任意の非負整数kに対して、式は分母がkである多項式として表すことができます。これは、有理係数を持つtの多項式を表します。 ${\textstyle {\binom {t}{k}}}$ $${\displaystyle {\binom {t}{k}}={\frac {t^{\underline {k}}}{k!}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};}$$

したがって、任意の実数または複素数tにおいて評価することで、このような第一引数を持つ二項係数を定義できます。これらの「一般化二項係数」は、ニュートンの一般化二項定理に現れます。

各kに対して、多項式はp (0) = p (1) = ⋯ = p ( k −1) = 0かつp ( k) = 1を満たす唯一のk次多項式p ( t )として特徴付けることができます。 ${\displaystyle {\tbinom {t}{k}}}$

その係数は、第一種スターリング数で表すことができます。の導関数は、対数微分で計算できます。からの整数で評価すると問題が発生する可能性がありますが、以下の恒等式を使用すると、次のように導関数を計算できます。 $${\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.}$$ ${\displaystyle {\tbinom {t}{k}}}$ $${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.}$$ ${\displaystyle 0}$ ${\displaystyle t-1}$ $${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}=\sum _{i=0}^{k-1}{\frac {(-1)^{k-i-1}}{k-i}}{\binom {t}{i}}.}$$

多項式空間の基底としての二項係数

任意の標数0の体（つまり、有理数体を含む任意の体）において、高々d次の各多項式p ( t )は、二項係数が各次数の多項式から構成されるため、二項係数の線型結合として一意に表現できる。係数ak_は、数列p (0), p (1), ..., p ( k )のk次の差である。明示的には、^[7] ${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$

${\displaystyle a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).}$

4

整数値多項式

各多項式は整数値です。つまり、すべての整数入力で整数値を持ちます。（これを証明する1つの方法は、パスカルの恒等式を使用してkについて帰納法を行うことです。）したがって、二項係数多項式の任意の整数線形結合も整数値です。逆に、（4）は、任意の整数値多項式がこれらの二項係数多項式の整数線形結合であることを示しています。より一般的には、特性0体Kの任意の部分環Rについて、 K [ t ]の多項式がすべての整数でRに値を持つのは、それが二項係数多項式のR線形結合である場合に限ります。 ${\displaystyle {\tbinom {t}{k}}}$ ${\displaystyle t}$

例

整数多項式3 t (3 t + 1) / 2は次のように書き直すことができる。

${\displaystyle 9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.}$

二項係数を含む恒等式

階乗の公式は、近くの二項係数を関連付けるのに役立ちます。例えば、kが正の整数でnが任意の値である場合、

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

5

そして、もう少し努力すれば、 $${\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.}$$

また、 $${\displaystyle {\binom {n-1}{k}}={\frac {n-k}{n}}{\binom {n}{k}}.}$$

さらに、次のことも役立つかもしれません。

${\displaystyle {\binom {n}{k}}{\binom {k}{j}}={\binom {n}{j}}{\binom {n-j}{k-j}}={\binom {n}{k-j}}{\binom {n-k+j}{j}}.}$

nが定数の場合、次の再帰式が成り立ちます。 $${\displaystyle {\binom {n}{k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}.}$$

まとめると、 $${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}={\frac {n}{n-k}}{\binom {n-1}{k}}}$$ $${\displaystyle ={\frac {n}{k}}{\binom {n-1}{k-1}}={\frac {n}{n-2k}}{\Bigg (}{\binom {n-1}{k}}-{\binom {n-1}{k-1}}{\Bigg )}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}$$

二項係数の和

式

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}}$

∗∗

は、パスカルの三角形のn行目の要素は常に 2 の n 乗になると言っています。これは、二項定理 ( ∗ )においてx = 1、y = 1と設定することで得られます。この式には自然な組み合わせの解釈もあります。つまり、左辺はサイズk = 0, 1, ..., nの {1, ..., n }のサブセットの数を合計し、サブセットの総数を求めます (つまり、左辺は{1, ..., n } のべき集合を数えます)。ただし、これらのサブセットは、 1, ..., nの各要素を順に選択または除外することによっても生成できます。つまり、n個の独立したバイナリ選択 (ビット文字列) により、合計 個の選択肢が得られます。左辺と右辺は、同じサブセットのコレクションを数える 2 つの方法なので、等しいです。 ${\displaystyle 2^{n}}$

数式

${\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}}$

6

そして、 xについて微分し（後者については2回）、x = y = 1を代入すると、 二項定理から導かれます。 $${\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}$$

任意の複素数値mとn、および任意の非負整数kに対して成立するチュー・ヴァンダーモンド恒等式は、

${\displaystyle \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}}$

7

は、式( 2 )を用いて(1 + x ) ^m (1 + x ) ^{n − m} = (1 + x ) ⁿの展開における係数を調べることで見つけることができる。m = 1のとき、式( 7 )は式( 3 )に簡約される。n = 2 m 、 k = mの特別な場合、式( 1 )を用いると、展開式( 7 )は（右のパスカルの三角形に見られるように） ${\displaystyle x^{k}}$

${\displaystyle {\begin{array}{c}1\\1\qquad 1\\1\qquad 2\qquad 1\\{\color {blue}1\qquad 3\qquad 3\qquad 1}\\1\qquad 4\qquad 6\qquad 4\qquad 1\\1\qquad 5\qquad 10\qquad 10\qquad 5\qquad 1\\1\qquad 6\qquad 15\qquad {\color {red}20}\qquad 15\qquad 6\qquad 1\\1\qquad 7\qquad 21\qquad 35\qquad 35\qquad 21\qquad 7\qquad 1\end{array}}}$

パスカルの三角形、0行目から7行目。式8のm = 3は3行目と6行目に次のように示されています。 ${\displaystyle 1^{2}+3^{2}+3^{2}+1^{2}=20.}$

${\displaystyle \sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},}$

8

ここで、右側の項は中心二項係数です。

チュー・ヴァンダーモンド恒等式の別の形式は、0 ≤ j ≤ k ≤ nを満たす任意の整数j、k、nに適用され、

${\displaystyle \sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.}$

9

証明は同様であるが、負の整数指数を持つ二項級数展開（2）を用いる。j = kのとき、式（9）はホッケースティック恒等式とその相対 $${\displaystyle \sum _{m=k}^{n}{\binom {m}{k}}={\binom {n+1}{k+1}}}$$ $${\displaystyle \sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}.}$$

F ( n ) をn番目のフィボナッチ数とします。 これは( 3 )を用いた帰納法、またはゼッケンドルフの表現によって 証明できます。組合せ論的な証明は以下に示す。 $${\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).}$$

和の多重セクション

整数sとtに対して、級数多重区分は二項係数の和に対して次の恒等式を与えます。 ${\displaystyle 0\leq t<s,}$ $${\displaystyle {\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\ldots ={\frac {1}{s}}\sum _{j=0}^{s-1}\left(2\cos {\frac {\pi j}{s}}\right)^{n}\cos {\frac {\pi (n-2t)j}{s}}.}$$

小さなsの場合、これらの級数は特に良い形を持ちます。例えば、^[8] $${\displaystyle {\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {n\pi }{3}}\right)}$$ $${\displaystyle {\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-2)\pi }{3}}\right)}$$ $${\displaystyle {\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-4)\pi }{3}}\right)}$$ $${\displaystyle {\binom {n}{0}}+{\binom {n}{4}}+{\binom {n}{8}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)}$$ $${\displaystyle {\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)}$$ $${\displaystyle {\binom {n}{2}}+{\binom {n}{6}}+{\binom {n}{10}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)}$$ $${\displaystyle {\binom {n}{3}}+{\binom {n}{7}}+{\binom {n}{11}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)}$$

部分和

二項係数の部分和に対する閉じた公式は存在しないが^{[9] 、(} 3 )と帰納法を用いてk = 0, …, n − 1に対して特別な場合^[10]で $${\displaystyle \sum _{j=0}^{k}{\binom {n}{j}}}$$ $${\displaystyle \sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},}$$

$${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0}$$後者の結果は、 n未満の次数の任意の多項式P ( x )に対して、有限差分理論から得られる結果の特別な場合でもある。[ ^11]

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(j)=0.}$

( 2 )をk回微分しx = −1とおくと、0 ≤ k < nのとき、に対してこれが得られ、一般にはこれらの線形結合をとることでこれに従う。 ${\displaystyle P(x)=x(x-1)\cdots (x-k+1)}$

P ( x ) がn以下の次数である場合、

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(n-j)=n!a_{n}}$

10

ここで、 P ( x )におけるn次の係数です。 ${\displaystyle a_{n}}$

より一般的には、( 10 ) について、 mとdは複素数です。これは、( 10 ) を⁠ ⁠の代わりに多項式⁠ ⁠に適用するとすぐにわかります。そして、 ⁠ ⁠ は依然として次数n以下であり、そのn次係数はd ⁿ a _nであることがわかります。 $${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}}$$ ${\displaystyle Q(x):=P(m+dx)}$ ${\displaystyle P(x)}$ ${\displaystyle Q(x)}$

この級数は k ≥ 2で収束する。この式はドイツ戦車問題の解析に用いられる。これはMに基づく帰納法によって証明される。 ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}$ ${\textstyle {\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}}}}$

組み合わせ論的証明による恒等式

二項係数を含む多くの恒等式は、組み合わせ論的な手段によって証明できます。たとえば、非負整数の場合、恒等式 （ q = 1のときは（ 6 ） に簡約される）には、次のように二重数えの証明を与えることができます。左側は、[ n ] = {1, 2, ..., n }から少なくともq個の要素を持つサブセットを選択し、選択した要素の中からq個の要素をマークする方法の数を数えます。右側でも同じことを数えます。マークするq個の要素の集合を選択する方法と、 [ n ]の残りの要素のうちどれがそのサブセットに属するかを選択する方法が複数あるためです。 ${\displaystyle {n}\geq {q}}$ $${\displaystyle \sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}}$$ ${\displaystyle {\tbinom {n}{q}}}$ ${\displaystyle 2^{n-q}}$

パスカルの恒等式では、 両辺とも [ n ] のk要素サブセットの数を数えます。つまり、右辺の 2 つの項は、サブセットを要素nを含むものと含まないものにグループ化します。 $${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k},}$$

（ 8 ）の恒等式も組み合わせ論的証明を持つ。恒等式は $${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.}$$

一列に並んだ空のマス目があり、そのうちのn個をマーク（選択）したいとします。これを行う方法はいくつかあります。一方、最初のn個の中からk個、残りのn個の中からk個を選択することで、n個のマス目を選択することもできます。kは0からnまでの任意の値を指定できます。つまり、 ${\displaystyle 2n}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle n-k}$

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.}$

ここで( 1 )を適用して結果を取得します。

F ( i )でフィボナッチ数列を表し、 F (0) = F (1) = 1となるように添え字を付けると、この恒等式は次の組み合わせ論的証明を持つ。^[12]帰納法によって、 F ( n )はn × 1の正方形の帯を2 × 1と1 × 1 のタイルで覆う方法の数を数えることが示される。一方、このようなタイリングで2 × 1のタイルがちょうどk 個使用される場合、1 × 1のタイルはn − 2 k 個使用されるので、合計でn − k個のタイルが使用される。これらのタイルを並べる順序は複数あるため、この係数をすべての可能なkの値にわたって合計すると恒等式が得られる。 $${\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)}$$ ${\displaystyle {\tbinom {n-k}{k}}}$

係数行の合計

すべてのk , ,に対するk通りの組み合わせの数は、二項係数のn行目（0 から数えて）の合計です。これらの組み合わせは、 0 から まで数える2 進数の 1 桁目によって列挙されます。ここで、各桁の位置はn 個の集合から 1 個の項目を表します。 ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ${\displaystyle 2^{n}-1}$

ディクソンの正体

ディクソンの恒等式は、またはより一般的には、 a、b、およびcが負でない整数である場合に、次の式になります。 $${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}}$$ $${\displaystyle \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!}}\,,}$$

継続的なアイデンティティ

特定の三角関数の積分は二項係数で表現できる値を持つ。 ${\displaystyle m,n\in \mathbb {N} ,}$ $${\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}(x)\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}}$$ $${\displaystyle \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}}}$$ $${\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n/2)}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ even}}\\0,&{\text{otherwise}}\end{cases}}}$$

これらは、オイラーの公式を使用して三角関数を複素指数関数に変換し、二項定理を使用して展開し、項ごとに積分することで証明できます。

合同性

nが素数の場合、任意のkに対して、より一般的には、 nが任意の数で、kが 1 とkの間のすべての数がnと互いに素である場合にも、これは真です。 $${\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n}$$ ${\displaystyle 0\leq k\leq n-1.}$

確かに、私たちは $${\displaystyle {\binom {n-1}{k}}={(n-1)(n-2)\cdots (n-k) \over 1\cdot 2\cdots k}=\prod _{i=1}^{k}{n-i \over i}\equiv \prod _{i=1}^{k}{-i \over i}=(-1)^{k}\mod n.}$$

生成関数

通常の生成関数

固定されたnに対して、数列の通常の生成関数は ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots }$ $${\displaystyle \sum _{k=0}^{\infty }{n \choose k}x^{k}=(1+x)^{n}.}$$

kが固定されている場合、数列の通常の生成関数は ${\displaystyle {\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots ,}$ $${\displaystyle \sum _{n=0}^{\infty }{n \choose k}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.}$$

二項係数の二変量生成関数は $${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{n \choose k}x^{k}y^{n}={\frac {1}{1-y-xy}}.}$$

二項係数の対称二変量生成関数は であり、これは置換後の前の生成関数と同じになります。 $${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}x^{k}y^{n}={\frac {1}{1-x-y}}.}$$ ${\displaystyle x\to xy}$

指数生成関数

二項係数の対称指数二変量生成関数は次のとおりです。 $${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}$$

割り切れる性質

1852 年、クンマーは、 mとn が非負の整数でp が素数である場合、 pを割り切る最大のべき乗はp ^{c に}等しくなることを証明しました。ここでcは、 mとn をpを底として加算したときの繰り上がりの数です。同様に、における素数pの指数は、k / p ^jの小数部がn / p ^jの小数部よりも大きくなる非負の整数jの数に等しくなります。 (たとえば、kの底p表現のすべての数字がnの底p表現の対応する数字以下である場合、 はpで割り切れません。) このことから、 はn / gcd ( n , k )で割り切れると演繹できます。したがって特に、s < p ^rとなるすべての正の整数rおよびsについて、 p が割り切れることがわかります。ただし、これはpの高次のべき乗には当てはまりません。たとえば、 9 は を割り切れません。 ${\displaystyle {\tbinom {m+n}{m}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {p^{r}}{s}}}$ ${\displaystyle {\tbinom {9}{6}}}$

任意の整数は、ほとんどすべての二項係数を割り切れる。^[13]より正確には、整数dを固定し、dがを割り切れる二項係数の個数をf ( N )で表すとする。すると、 n < Nとなる二項係数の個数はN ( N +1)/2なので、 dで割り切れる二項係数の密度は1になる。 ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle n<N}$ ${\displaystyle {\tbinom {n}{k}}}$ $${\displaystyle \lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.}$$ ${\displaystyle {\tbinom {n}{k}}}$

二項係数は連続する整数の最小公倍数に関連した割り切れる性質を持つ。例えば^[14]

${\displaystyle {\binom {n+k}{k}}}$を割ります。 ${\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n}}}$

${\displaystyle {\binom {n+k}{k}}}$は の倍数です。 ${\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n\cdot \operatorname {lcm} ({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}}$

もう一つの事実: 整数n ≥ 2が素数となるのは、中間の二項係数がすべてnで割り切れる場合のみです。 $${\displaystyle {\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}}$$

証明: pが素数のとき、0 < k < pのすべての場合でpが割り切れます。これは、 が自然数で、p が分子を割り切れますが、分母を割り切れないからです。nが合成数の場合、p をnの最小の素因数とし、k = n / pとします。すると0 < p < 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は素数なので、 p は( n − 1)( n − 2)⋯( n − p + 1)を割り切れないことがわかっており、したがって分子はnで割り切れません。 $${\displaystyle {\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}}$$ ${\displaystyle {\tbinom {p}{k}}}$ $${\displaystyle {\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)!}}\not \equiv 0{\pmod {n}}}$$

境界と漸近公式

1 ≤ k ≤ nを満たすすべてのnおよびkの値に対して、の以下の境界が成り立ちます。最初の不等式は、であり、この積の各項が であるという事実から導き出されます。同様の議論で、2番目の不等式も示せます。最後の厳密な不等式は と等価であり、右辺が指数級数の項であるため、これは明らかです。 ${\displaystyle {\tbinom {n}{k}}}$ $${\displaystyle {\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.}$$ $${\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}}$$ ${\displaystyle k}$ ${\textstyle \geq {\frac {n}{k}}}$ ${\textstyle e^{k}>k^{k}/k!}$ ${\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}$

割り切れる性質から、両方の等式が達成できることを推論することができます。^[14] $${\displaystyle {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{(n-k)\cdot \operatorname {lcm} \left({\binom {k}{0}},\ldots ,{\binom {k}{k}}\right)}}\leq {\binom {n}{k}}\leq {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{n-k}},}$$

情報理論では、以下の境界が有用である：^{[15] : 353}ここでは2値エントロピー関数である。これはさらに、すべてのに対して と限定することができる。^{[16] : 309} $${\displaystyle {\frac {1}{n+1}}2^{nH(k/n)}\leq {n \choose k}\leq 2^{nH(k/n)}}$$ ${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$ $${\displaystyle {\sqrt {\frac {n}{8k(n-k)}}}2^{nH(k/n)}\leq {n \choose k}\leq {\sqrt {\frac {n}{2\pi k(n-k)}}}2^{nH(k/n)}}$$ ${\displaystyle 1\leq k\leq n-1}$

両方nそしてけ大きい

スターリングの近似は、両方が無限大に近づく場合に有効な、以下の近似値を与える。スターリングの公式の不等式は階乗にも上限を与えるため、上記の漸近近似に若干の変形を加えることで、正確な上限が得られる。特に、が十分に大きい場合、およびとなる。より一般的には、m ≥ 2およびn ≥ 1の場合（ここでも、スターリングの公式を二項係数の階乗に適用することにより）、 ${\displaystyle n-k,k}$ $${\displaystyle {n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}}$$ ${\displaystyle n}$ $${\displaystyle {2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}$$ ${\displaystyle {\sqrt {n}}{2n \choose n}\geq 2^{2n-1}}$ $${\displaystyle {\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}.}$$

nが大きく、kがnに関して線形である場合、二項係数 に対する様々な正確な漸近推定値が存在する。例えば、の場合 、 となる。ただし、 d = n − 2 kである。^[17] ${\textstyle {\binom {n}{k}}}$ ${\displaystyle |n/2-k|=o(n^{2/3})}$ $${\displaystyle {\binom {n}{k}}\sim {\binom {n}{\frac {n}{2}}}e^{-d^{2}/(2n)}\sim {\frac {2^{n}}{\sqrt {{\frac {1}{2}}n\pi }}}e^{-d^{2}/(2n)}}$$

nよりもはるかに大きいけ

nが大きく、kがo ( n )（つまりk / n →0） の場合には、 oは小文字のo表記である。[ ^18] $${\displaystyle {\binom {n}{k}}\sim \left({\frac {ne}{k}}\right)^{k}\cdot (2\pi k)^{-1/2}\cdot \exp \left(-{\frac {k^{2}}{2n}}(1+o(1))\right)}$$

二項係数の和

二項係数の和の単純かつ大まかな上限は二項定理を使って得ることができる。 より正確な上限は、を満たすすべての整数に対して有効であることによって与えられる。^[19] $${\displaystyle \sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}}$$ $${\displaystyle {\frac {1}{\sqrt {8n\varepsilon (1-\varepsilon )}}}\cdot 2^{H(\varepsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\varepsilon )\cdot n},}$$ ${\displaystyle n>k\geq 1}$ ${\displaystyle \varepsilon \doteq k/n\leq 1/2}$

一般化二項係数

ガンマ関数の無限積の公式は、二項係数の式も与え、漸近公式はとなります。 $${\displaystyle (-1)^{k}{z \choose k}={-z+k-1 \choose k}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {\left(1+{\frac {1}{j}}\right)^{-z-1}}{1-{\frac {z+1}{j}}}}}$$ $${\displaystyle {z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{and}}\qquad {z+k \choose k}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)}$$ ${\displaystyle k\to \infty }$

この漸近的な振る舞いは近似にも含まれています。（ここではk番目の調和数であり、はオイラー・マスケロニ定数です。） $${\displaystyle {z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}$$ ${\displaystyle H_{k}}$ ${\displaystyle \gamma }$

さらに、漸近公式は 、および何らかの複素数 に対して常に成立します。 $${\displaystyle {\frac {z+k \choose j}{k \choose j}}\to \left(1-{\frac {j}{k}}\right)^{-z}\quad {\text{and}}\quad {\frac {j \choose j-k}{j-z \choose j-k}}\to \left({\frac {j}{k}}\right)^{z}}$$ ${\displaystyle k\to \infty }$ ${\displaystyle j/k\to x}$ ${\displaystyle x}$

一般化

多項式への一般化

二項係数は、次の数として定義される多項係数に一般化することができる。ここで $${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}}$$ $${\displaystyle \sum _{i=1}^{r}k_{i}=n.}$$

二項係数は( x + y ) ⁿの係数を表しますが、多項式係数は多項式の係数を表します。r = 2 の場合は二項係数になります。 $${\displaystyle (x_{1}+x_{2}+\cdots +x_{r})^{n}.}$$ $${\displaystyle {n \choose k_{1},k_{2}}={n \choose k_{1},n-k_{1}}={n \choose k_{1}}={n \choose k_{2}}.}$$

多項式係数の組み合わせ的解釈は、n個の識別可能な要素をr 個の（識別可能な）コンテナーに分配することです。各コンテナーには正確にk _i個の要素が含まれます。ここで、iはコンテナーのインデックスです。

多項式係数には、二項式係数に似た多くの特性があります。たとえば、再帰関係、対称性などが あります。ここで、 は(1, 2, ..., r ) の順列です。 $${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n-1 \choose k_{1}-1,k_{2},\ldots ,k_{r}}+{n-1 \choose k_{1},k_{2}-1,\ldots ,k_{r}}+\ldots +{n-1 \choose k_{1},k_{2},\ldots ,k_{r}-1}}$$ $${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}}$$ ${\displaystyle (\sigma _{i})}$

テイラー級数

第一種スターリング数を用いると、任意の点の周りの級数展開は ${\displaystyle z_{0}}$ $${\displaystyle {\begin{aligned}{z \choose 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}{z_{0} \choose 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}{j \choose i}{\frac {s_{k,j}}{k!}}.\end{aligned}}}$$

二項係数n = 1/2

二項係数の定義は、 が実数で が整数の場合にまで拡張できます。 ${\displaystyle n}$ ${\displaystyle k}$

特に、任意の非負整数に対して次の恒等式が成り立ちます。 ${\displaystyle k}$ $${\displaystyle {{1/2} \choose {k}}={{2k} \choose {k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.}$$

これは、ニュートン二項級数を使用してべき級数に展開すると現れます。 ${\displaystyle {\sqrt {1+x}}}$ $${\displaystyle {\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.}$$

二項係数の積

2つの二項係数の積は、二項係数の線形結合として表すことができます。 $${\displaystyle {z \choose m}{z \choose n}=\sum _{k=0}^{\min(m,n)}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},}$$

ここで、接続係数は多項式係数です。ラベル付き組み合わせオブジェクトに関しては、接続係数は、重みがそれぞれmとnであるラベル付き組み合わせオブジェクトのペアに、最初のk個のラベルが識別された、または結合されて重みがm + n − kの新しいラベル付き組み合わせオブジェクトが得られた場合に、m + n − k個のラベルを割り当てる方法の数を表します。 （つまり、ラベルを 3 つの部分に分割して、最初のオブジェクトの結合部分、結合されていない部分、および 2 番目のオブジェクトの結合されていない部分に適用します。）この点で、指数生成級数に対する二項係数は、通常の生成級数に対する下降階乗と同じです。

パスカルの三角形のn行目にあるすべての二項係数の積は、次の式で表されます。 $${\displaystyle \prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=1}^{n}k^{2k-n-1}.}$$

部分分数分解

逆数の部分分数分解は次のように表される。 $${\displaystyle {\frac {1}{z \choose n}}=\sum _{i=0}^{n-1}(-1)^{n-1-i}{n \choose i}{\frac {n-i}{z-i}},\qquad {\frac {1}{z+n \choose n}}=\sum _{i=1}^{n}(-1)^{i-1}{n \choose i}{\frac {i}{z+i}}.}$$

ニュートンの二項級数

ニュートンの二項級数は、アイザック・ニュートン卿にちなんで名付けられ、二項定理を無限級数に一般化したものです。 $${\displaystyle (1+z)^{\alpha }=\sum _{n=0}^{\infty }{\alpha \choose n}z^{n}=1+{\alpha \choose 1}z+{\alpha \choose 2}z^{2}+\cdots .}$$

両辺が微分方程式 (1 + z ) f' ( z ) = α f ( z )を満たすことを示すことによって、恒等式が得られます。

この級数の収束半径は1 です。別の表現は、恒等式が適用される場合です。 $${\displaystyle {\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}}$$ $${\displaystyle {n \choose k}=(-1)^{k}{k-n-1 \choose k}}$$

多重集合（上昇）二項係数

二項係数は、与えられた集合から所定の大きさの部分集合を数えます。関連する組み合わせ問題として、与えられた集合から要素を取り、所定の大きさの多重集合を数える問題があります。つまり、与えられた集合から特定の数の要素を選択し、同じ要素を繰り返し選択する可能性のある方法の数を数える問題です。得られた数値は多重集合係数と呼ばれます。^[20] n要素の集合からk個の要素を「多重選択」（つまり、置換選択）する方法の数はと表されます。 ${\textstyle \left(\!\!{\binom {n}{k}}\!\!\right)}$

この記事ではnの主な意味との曖昧さと混乱を避けるために、 f = n = r + ( k − 1)、r = f − ( k − 1)
とします。

多重集合係数は、二項係数を用いて次の規則で表現することができます。この恒等式の別の特徴付けとしては、下降階乗を次のように 定義し、対応する上昇階乗を次のように 定義することができます。例えば、二項係数は次のように記述できます。対応する多重集合係数は、下降階乗を上昇階乗に置き換えることで定義されます。 $${\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.}$$ $${\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,}$$ $${\displaystyle r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);}$$ $${\displaystyle 17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.}$$ $${\displaystyle {\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}},}$$ $${\displaystyle \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

負および分数nに対して拡張された二項係数C  ( n , k ) を、単純な二項式で示します。パスカルの三角形が回転し、交互の項が反転していることがわかります。 n  = −1 の場合はグランディ級数となります。

任意のnに対して、特に負の整数nで評価される二項係数は符号付き多重集合係数で与えられる。特別な場合 では、これは次のように簡約される。 $${\displaystyle {\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}}}$$ ${\displaystyle n=-1}$ ${\displaystyle (-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right).}$

たとえば、n = −4、k = 7の場合、r = 4、f = 10になります。 $${\displaystyle {\begin{aligned}{\binom {-4}{7}}&={\frac {-10\cdot -9\cdot -8\cdot -7\cdot -6\cdot -5\cdot -4}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=(-1)^{7}\;{\frac {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=\left(\!\!{\binom {-7}{7}}\!\!\right)\left(\!\!{\binom {4}{7}}\!\!\right)={\binom {-1}{7}}{\binom {10}{7}}.\end{aligned}}}$$

2つの実数値または複素数値の引数

二項係数は、ガンマ関数またはベータ関数を使用して 、2つの実数値または複素数値の引数に一般化されます。この定義は、次の追加のプロパティを継承します。さらに、 $${\displaystyle {x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (y+1,x-y+1)}}.}$$ ${\displaystyle \Gamma }$ $${\displaystyle {x \choose y}={\frac {\sin(y\pi )}{\sin(x\pi )}}{-y-1 \choose -x-1}={\frac {\sin((x-y)\pi )}{\sin(x\pi )}}{y-x-1 \choose y};}$$ $${\displaystyle {x \choose y}\cdot {y \choose x}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}.}$$

結果として得られる関数はほとんど研究されておらず、どうやら(Fowler 1996)で初めてグラフ化されたようです。注目すべきことに、多くの二項恒等式は成り立ちません。ただし、nが正（つまり負）の場合は成り立ちません。その挙動は非常に複雑で、様々な八分円（つまりx軸とy軸、そして直線に関して）で著しく異なり、負のxに対しては負の整数値で特異点が見られ、正と負の領域が市松模様のように変化します。 ${\textstyle {\binom {n}{m}}={\binom {n}{n-m}}}$ ${\textstyle {\binom {-n}{m}}\neq {\binom {-n}{-n-m}}}$ ${\displaystyle -n}$ ${\displaystyle y=x}$

• 八分儀では、通常の二項式を滑らかに補間した形で、尾根（「パスカルの尾根」）があります。 ${\displaystyle 0\leq y\leq x}$
• 八分円と象限では関数はゼロに近くなります。 ${\displaystyle 0\leq x\leq y}$ ${\displaystyle x\geq 0,y\leq 0}$
• 象限では、関数は頂点を持つ平行四辺形上で交互に非常に大きな正と負の値をとる。 ${\displaystyle x\leq 0,y\geq 0}$ $${\displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$$
• 八分儀では、動作は再び非常に大きな正と負が交互に現れますが、正方形のグリッド上になります。 ${\displaystyle 0>x>y}$
• 八分儀では、特異点の近くを除いてゼロに近くなります。 ${\displaystyle -1>y>x+1}$

一般化q-シリーズ

二項係数には、ガウス二項係数として知られるq類似の一般化があります。これらの係数は不定値（伝統的にqと表記される）における多項式であり、有限体上のベクトル空間の線型部分空間の数を数えることや、特定の対称性を持つ{1, 2, ..., n }の部分集合の数を数えること（巡回ふるい分け現象の一例）など、組合せ論における多くの列挙問題に応用されています。

無限基数への一般化

二項係数の定義は、次のように定義することで無限基数に一般化できます。 ここで、 Aは基数を持つ集合です。一般化された二項係数は、基数を表すためにどのような集合を選択しても は同じままであるという意味で、明確に定義されていることが示せます。有限基数の場合、この定義は二項係数の標準的な定義と一致します。 $${\displaystyle {\alpha \choose \beta }=\left|\left\{B\subseteq A:\left|B\right|=\beta \right\}\right|}$$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\textstyle {\alpha \choose \beta }}$

選択公理を仮定すると、任意の無限基数に対して であることが証明できます。 ${\textstyle {\alpha \choose \alpha }=2^{\alpha }}$ ${\displaystyle \alpha }$

参照

• 二項変換
• デラノワ数
• オイラー数
• 超幾何関数
• 階乗と二項式のトピックのリスト
• 整数のマコーレー表現
• モツキン数
• パスカルの三角形の多重項
• ナラヤナ番号
• ダビデの星の定理
• 太陽の奇妙な正体
• ニュートン級数表
• 三項式展開

注記

1. ハイアム（1998）
2. Lilavatiセクション 6、第 4 章 (Knuth (1997) を参照)。
3. ウスペンスキー 1937年、18ページ
4. （Graham, Knuth & Patashnik 1994）も参照。この定義ではについても定義されている。2つの実数値または複素数値の引数にガンマ関数を用いるなどの別の一般化では に対して非ゼロ値を割り当てるが、これによってほとんどの二項係数恒等式が成立しなくなるため、ほとんどの定義では広く用いられていない。このような非ゼロ値の選択の1つは、ヒルトン、ホルトン、ペダーセン共著『数学的反射：多数の鏡のある部屋で』（Springer、1997年）に登場する美的に美しい「パスカル風車」につながるが、パスカルの恒等式さえも成立しなくなる（原点において）。 ${\displaystyle {\tbinom {n}{k}}=0}$ ${\displaystyle k<0}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k<0}$
5. が非負の整数のとき、 は分子の - 番目の因数が であるためです。したがって、すべての に対して- 番目の項は零積になります。 ${\displaystyle \alpha =n}$ ${\displaystyle \textstyle {\binom {n}{k}}=0}$ ${\displaystyle k>n}$ ${\displaystyle (k=n+1)}$ ${\displaystyle n-(n+1)+1=0}$ ${\displaystyle k}$ ${\displaystyle k\geq n+1}$
6. ミュア、トーマス (1902). 「選択された組み合わせに関する注記」.エディンバラ王立協会紀要.
7. これはテイラーの定理の離散的な類似物と見ることができます。ニュートンの多項式と密接に関連しています。この形式の交代和は、ネルンド・ライス積分として表すことができます。
8. Gradshteyn & Ryzhik (2014、pp. 3–4)。
9. Boardman, Michael (2004)、「The Egg-Drop Numbers」、Mathematics Magazine、77 (5): 368– 372、doi :10.2307/3219201、JSTOR  3219201、MR  1573776、二項係数の部分和には閉じた形式（つまり直接的な公式）が存在しないことはよく知られている。。
10. Aupetit, Michael (2009)「決定論的ジェネレータによるほぼ均質なマルチパーティショニング」Neurocomputing、72 ( 7–9 ): 1379– 1389、doi :10.1016/j.neucom.2008.12.024、ISSN  0925-2312 、式(7)p.1389で展開された帰納法を参照。。
11. ルイス、セバスチャン (1996). 「ウィルソンの定理に至る代数的恒等式」.数学ガゼット. 80 (489): 579– 582. arXiv : math/0406086 . doi :10.2307/3618534. JSTOR  3618534. S2CID  125556648.
12. ベンジャミン＆クイン 2003、4−5ページ
13. デイヴィッド・シンマスター（1974）
14. Farhi, Bakir (2007). 「整数の有限列の最小公倍数に対する非自明な下限値」. Journal of Number Theory . 125 (2): 393– 411. arXiv : 0803.0290 . doi :10.1016/j.jnt.2006.10.017. S2CID  115167580.
15. Thomas M. Cover、Joy A. Thomas (2006年7月18日). 『情報理論の要素』 . ホーボーケン、ニュージャージー州: Wiley. ISBN 0-471-24195-4。
16. FJ MacWilliams; NJA Sloane (1981). 『誤り訂正符号の理論』 第16巻（第3版）. North-Holland. ISBN 0-444-85009-0。
17. スペンサー、ジョエル；フロレスク、ローラ（2014年）「アシンプトピア」学生数学図書館第71巻AMS66頁ISBN 978-1-4704-0904-3. OCLC  865574788。
18. スペンサー, ジョエル; フロレスク, ローラ (2014).アシンプトピア. 学生数学図書館. 第71巻. AMS . p. 59. ISBN 978-1-4704-0904-3. OCLC  865574788。
19. 例えばAsh (1990, p. 121)やFlum & Grohe (2006, p. 427)を参照。
20. Munarini, Emanuele (2011)、「リオルダン行列と調和数の和」(PDF)、適用可能解析と離散数学、5 (2): 176– 200、doi :10.2298/AADM110609014M、MR  2867317。

参考文献

• アッシュ、ロバート・B. (1990) [1965].情報理論. ドーバー出版. ISBN 0-486-66521-6。
• ベンジャミン、アーサー・T.、クイン、ジェニファー・J. (2003). 「本当に大切な証明：組み合わせ証明の技法」 . ドルチアーニ数学解説集. 第27巻.アメリカ数学協会. ISBN 978-0-88385-333-7。
• ブライアント、ビクター（1993年）『組合せ論の諸相』ケンブリッジ大学出版局、ISBN 0-521-41974-3。
• フルム、ヨルグ。グローエ、マーティン(2006)。パラメータ化された複雑性理論。スプリンガー。ISBN 978-3-540-29952-3. 2007年11月18日時点のオリジナルよりアーカイブ。2017年8月28日閲覧。
• ファウラー、デイビッド（1996年1月）「二項係数関数」アメリカ数学月刊誌103 ( 1)。アメリカ数学会誌: 1-17 . doi :10.2307/2975209. JSTOR  2975209.
• Goetgheluck, P. (1987). 「二項係数の計算」. American Mathematical Monthly . 94 (4): 360– 365. doi :10.2307/2323099. JSTOR  2323099.
• グラハム, ロナルド L. ;クヌース, ドナルド E. ;パタシュニク, オレン(1994年2月). 『具体的な数学 ― コンピュータサイエンスの基礎』（第2版）. マサチューセッツ州レディング, 米国: Addison-Wesley Professional . pp.  154– 155. ISBN 0-201-55802-5. MR  1397498。
• Gradshteyn, IS; Ryzhik, IM (2014).積分・級数・積表（第8版）. Academic Press. ISBN 978-0-12-384933-5。
• Grinshpan, AZ (2010)、「重み付き不等式と負の二項式」、応用数学の進歩、45 (4): 564– 606、doi : 10.1016/j.aam.2010.04.004
• ハイアム、ニコラス・J. (1998).数学科学ライティングハンドブック. SIAM . p. 25. ISBN 0-89871-420-6。
• ドナルド・E.・クヌース（1997年）『コンピュータプログラミングの技法』第1巻：基礎アルゴリズム（第3版）。アディソン・ウェスレー。52  ～ 74ページ。ISBN 0-201-89683-4。
• シングマスター、デイヴィッド(1974). 「二項係数に関する注釈 III. 任意の整数はほぼすべての二項係数を割り切る」ロンドン数学会誌. 8 (3): 555– 560. doi :10.1112/jlms/s2-8.3.555.
• シロフ, GE (1977).線形代数. ドーバー出版. ISBN 978-0-486-63518-7。
• ウスペンスキー、ジェームズ（1937年）、数学的確率入門、マグロウヒル

外部リンク

• 「二項係数」数学百科事典、EMSプレス、2001 [1994]
• Andrew Granville (1997). 「二項係数の算術的性質 I. 素数べきを法とする二項係数」. CMS Conf. Proc . 20 : 151–162 . 2015年9月23日時点のオリジナルよりアーカイブ。 2013年9月3日閲覧。

この記事には、クリエイティブ コモンズの表示/共有ライセンスの下でライセンスされている次のPlanetMath の記事の資料が組み込まれています: 二項係数、二項係数の上限と下限、二項係数は整数、一般化二項係数。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Binomial_coefficient&oldid=1320779528"