数 学 に お け る 二 項 係 数 ︵ に こ う け い す う 、 英 : b i n o m i a l c o e f f i c i e n t s ︶ は 二 項 展 開 に お い て 係 数 と し て 現 れ る 正 の 整 数 の 族 で あ る 。 二 項 係 数 は 2 つ の 非 負 整 数 で 添 字 付 け ら れ 、 添 字 n , k を 持 つ 二 項 係 数 は ふ つ う ( n
k ) と か ( n ¦ k ) と 書 か れ る ︵ こ れ は 二 項 冪 ( 1 + x ) n の 展 開 に お け る x k の 項 の 係 数 で あ る 。 適 当 な 仮 定 の 下 で 、 こ の 係 数 の 値 は
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\tfrac {n!}{k!\,(n-k)!}}}
で 与 え ら れ る ︶ 。 二 項 係 数 を 、 連 続 す る 整 数 n に 対 す る 各 行 に k を 0 か ら n ま で 順 に 並 べ て 得 ら れ る 三 角 形 状 の 数 の 並 び を パ ス カ ル の 三 角 形 と 呼 ぶ 。
二 項 係 数 の 全 体 を パ ス カ ル の 三 角 形 の 形 に 並 べ る こ と が で き る 。
4 つ の 数 か ら 2 つ の 数 を 選 ぶ 方 法 は
(
4
2
)
=
6
{\displaystyle {\tbinom {4}{2}}=6}
通 り あ る 。
四 次 ま で の 二 項 展 開 の 視 覚 的 説 明
こ の 整 数 族 は 代 数 学 の み な ら ず 数 学 の 他 の 多 く の 分 野 、 特 に 組 合 せ 論 に お い て 現 れ る 。 n 元 - 集 合 か ら k 個 の 元 を ︵ そ の 順 番 を 無 視 し て ︶ 選 ぶ 方 法 が ( n
k ) 通 り で あ る 。 二 項 係 数 の 性 質 を 用 い て 、 記 号 ( n
k ) の 意 味 を 、 も と も と の n お よ び k が k ≤ n な る 非 負 整 数 で あ っ た 場 合 を 超 え て 拡 張 す る こ と が 可 能 で 、 そ の よ う な 場 合 も や は り 二 項 係 数 と 称 す る 。
自然数 (0 も含める)n および k に対し、二項係数 ( n k ) は二項冪 (1 + X )n の展開における Xk の項 の係数 として定義できる。同係数は(k ≤ n のとき)二項公式
(
x
+
y
)
n
=
∑
k
=
0
n
(
n
k
)
x
n
−
k
y
k
{\displaystyle (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 に お け る n 個 の 因 子 の 各 々 に お い て 、 一 時 的 に X に 対 し 1 ≤ i ≤ n な る 添 字 i を そ れ ぞ れ 付 け て 区 別 し て お く と 、 k 個 の 添 字 か ら な る 部 分 集 合 を ひ と つ 選 ぶ 毎 に 展 開 後 の X k へ の 寄 与 が 1 だ け あ る か ら 、 こ の 項 の 係 数 は そ の よ う な 部 分 集 合 の 選 び 方 の 数 に 一 致 す る 。 こ の こ と は 特 に ( n
k ) が 任 意 の 自 然 数 n , k に 対 し て 自 然 数 と な る こ と も 示 し て い る 。 二 項 係 数 の 組 合 せ 論 的 解 釈 ︵ 二 項 係 数 展 開 が 答 え を 与 え る 数 え 上 げ 問 題 ︶ は 多 く 存 在 す る 。 例 え ば 、 各 位 の 和 が k に 一 致 す る n 桁 の ビ ッ ト ︵ つ ま り 各 位 の 数 は 0 か 1 ︶ の 語 ︵ 文 字 列 ︶ の 総 数 は ( n
k ) で 与 え ら れ る 。 ま た 、 各 a i が 非 負 整 数 で あ る も の と し て k = a 1 + a 2 + … + a n と 書 く 方 法 の 総 数 は ( n + k − 1
n − 1 ) 通 り で あ る 。 こ れ ら 解 釈 の ほ と ん ど は 、 k - 組 合 せ を 数 え る こ と に 同 値 で あ る こ と が 容 易 に 示 さ れ る 。
( n k ) の値を、実際に二項冪を展開したり k -組合せを数え上げたりせずに、計算する方法はいくつかある。
一 つ は 、 n , k を 1 ≤ k ≤ n − 1 な る 自 然 数 と し て 、 純 加 法 的 な 漸 化 式
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}
を 初 期 条 件 ﹁ 任 意 の n ≥ 0 に 対 し ( 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 ) の 両 辺 に お け る X k へ の 寄 与 を 見 る こ と で も こ の 漸 化 式 は 得 ら れ る 。 ( 1 + X ) n に お い て X n + 1 や X − 1 の 項 は 存 在 し な い ︵ あ る い は 係 数 が 零 で あ る ︶ か ら 、 二 項 係 数 の 定 義 を 上 記 の 境 界 を 越 え て 延 長 し て 、 ( n
k ) = 0 ( k > n ∨ k < 0 ) と す る こ と も で き る 。
こ の 漸 化 式 は パ ス カ ル の 三 角 形 を 描 く の に も 利 用 で き る 。
個々の二項係数をより効果的に計算するには
(
n
k
)
=
n
k
_
k
!
=
n
(
n
−
1
)
(
n
−
2
)
⋯
(
n
−
(
k
−
1
)
)
k
(
k
−
1
)
(
k
−
2
)
⋯
1
=
∏
i
=
1
k
n
−
(
k
−
i
)
i
=
∏
i
=
1
k
n
+
1
−
i
i
{\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\textstyle \prod \limits _{i=1}^{k}{\dfrac {n-(k-i)}{i}}=\prod \limits _{i=1}^{k}{\dfrac {n+1-i}{i}}}
で与えられる式を用いる。一つ目の分数の分子に現れる n k は下降階乗冪 である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は n 個の対象からなる集合から選ぶ順番を考慮して相異なる k 個の対象を取り出す方法の総数であり、分母は同じ k -組合せを与える相異なる並びの数を数えるものである。
最 後 に 、 計 算 論 的 に は 不 利 だ が 、 短 く 書 け る の で し ば し ば 証 明 や 導 出 に 用 い ら れ る よ く 知 ら れ た 階 乗 函 数 を 用 い た 式 は
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}}
で 与 え ら れ る 。 こ こ に n ! は n の 階 乗 で あ る 。 こ の 式 は 上 記 の 乗 法 表 示 式 に 、 分 子 分 母 に 対 し て ( n − k ) ! を 掛 け る こ と で 得 ら れ る ︵ そ の 結 果 、 こ の 式 に お い て 分 母 と 分 子 は 多 く の 共 通 因 数 を 持 つ こ と に な る ︶ 。 ︵ 特 に 階 乗 は 非 常 に 速 く 増 加 す る か ら ︶ こ の 式 を ︵ k が 小 さ く n が 大 き い 場 合 に ︶ 実 際 の 数 値 計 算 に 用 い る こ と は ︵ 先 に 共 通 因 数 を 約 分 し な い 限 り ︶ 実 用 的 で な い 。 こ の 式 は 上 記 の 乗 法 表 示 よ り は 二 項 係 数 が 対 称 性
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}
(1 )
を持つことを見るのに適している(二項係数の定義から対称性をもつことは分かる)。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば
(
n
k
)
=
{
n
k
_
/
k
!
if
k
≤
n
2
n
n
−
k
_
/
(
n
−
k
)
!
if
k
>
n
2
{\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 を任意の数 α (負の整数、実数、複素数、……)あるいは任意の整数が可逆となるような可換環 の元に取り換えて、
(
α
k
)
=
α
k
_
k
!
=
α
(
α
−
1
)
(
α
−
2
)
⋯
(
α
−
k
+
1
)
k
(
k
−
1
)
(
k
−
2
)
⋯
1
{\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}}}
により二項係数の定義を拡張することができる[注 1] 。この定義により、二項定理(の一方の変数を 1 としたもの)も一般化して
(
1
+
X
)
α
=
∑
k
=
0
∞
(
α
k
)
X
k
{\displaystyle (1+X)^{\alpha }=\textstyle \sum \limits _{k=0}^{\infty }{\dbinom {\alpha }{k}}X^{k}}
(2 )
と 書 く こ と が で き る 。 故 に こ の 場 合 も ( α
k ) を 二 項 係 数 と 呼 ぶ こ と は 正 当 化 さ れ る 。 こ の 等 式 は 任 意 の 複 素 数 α と | X | < 1 な る X に 対 し て 有 効 で あ る 。 こ れ は ま た X を 不 定 元 と す る 形 式 冪 級 数 の 等 式 と し て も 解 釈 で き 、 そ れ は 実 際 に 定 数 係 数 1 を 持 つ 級 数 の 任 意 の 冪 の 定 義 と し て 機 能 す る 。 こ の 定 義 を 用 い る ポ イ ン ト は 、 冪 乗 と し て 満 足 す る こ と が 期 待 さ れ る 全 て の 恒 等 式 ︵ 指 数 法 則 ︶ 、 特 に
●
(
1
+
X
)
α
(
1
+
X
)
β
=
(
1
+
X
)
α
+
β
,
{\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta },}
●
(
(
1
+
X
)
α
)
β
=
(
1
+
X
)
α
β
{\displaystyle ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }}
が 満 足 さ れ る こ と で あ る 。 α が 非 負 整 数 n の と き 、 k > n な る 全 て の 項 は 零 で あ り 、 上 記 の 無 限 級 数 は 有 限 和 と な り 、 し た が っ て も と も と の 二 項 定 理 が 再 び 得 ら れ る 。 し か し α が そ れ 以 外 の 値 な ら ば 、 負 の 整 数 や 有 理 数 の 場 合 も 含 め て 、 上 記 の 級 数 は 実 際 に 無 限 和 に な る 。
パスカルの三角形の第 1000 行 に並ぶ二項係数を縦に並べたもの。各二項係数を十進表示し、その各桁の数字を0-9に応じたグレイスケールの点で表してある。画像の左の境界は二項係数の対数グラフにほぼ対応しており、これらが対数凹列 (英語版 ) であることが見て取れる。
パスカルの法則 (英語版 ) は重要な漸化式
(
n
k
)
+
(
n
k
+
1
)
=
(
n
+
1
k
+
1
)
,
{\displaystyle {\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 か ら 始 め て 、 常 に 隣 り 合 う 2 項 を 加 え た 数 を そ の 真 下 に 書 い て い け ば よ い 。 こ の 方 法 に よ っ て 、 分 数 や 乗 算 を 使 わ ず に 二 項 係 数 を 手 早 く 計 算 す る こ と が で き る 。
例 え ば 三 角 形 の 5 行 目 を 見 れ ば
( x + y ) 5 = 1 x 5 + 5 x 4 y + 10 x 3 y 2 + 10 x 2 y 3 + 5 x y 4 + 1 y 5
が 直 ち に 読 み 取 れ る 。
他 の 対 角 線 上 の 数 と の 差 は 、 上 記 漸 化 式 ( 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 ) で あ る [ 5 ] 。
● カ タ ラ ン 数 ‥ 1 / n + 1 ( 2 n
n ) .
● 二 項 分 布 ‥ ( n
k ) p k ( 1 − p ) n − k .
t を 不 定 元 と し て 、 任 意 の 非 負 整 数 k に 対 し て 式
(
t
k
)
=
(
t
)
k
k
!
=
(
t
)
k
(
k
)
k
=
t
(
t
−
1
)
(
t
−
2
)
⋯
(
t
−
k
+
1
)
k
(
k
−
1
)
(
k
−
2
)
⋯
2
⋅
1
{\displaystyle {\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 ) と し て 特 徴 づ け る こ と が で き る 。
こ の 多 項 式 の 係 数 は 第 一 種 ス タ ー リ ン グ 数 を 用 い て
(
t
k
)
=
∑
i
=
0
k
[
k
i
]
t
i
k
!
{\displaystyle {\binom {t}{k}}=\textstyle \sum \limits _{i=0}^{k}\displaystyle \left[{k \atop i}\right]{\frac {t^{i}}{k!}}}
と 表 す こ と が で き る 。 こ の 導 函 数 は 対 数 微 分 法 に よ り
d
d
t
(
t
k
)
=
(
t
k
)
∑
i
=
0
k
−
1
1
t
−
i
{\displaystyle {\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
)
=
∑
k
=
0
d
a
k
(
t
k
)
{\displaystyle p(t)=\textstyle \sum \limits _{k=0}^{d}a_{k}{\dbinom {t}{k}}}
として一意に書ける。このときの係数 ak は数列 p (0), p (1), …, p (k ) の第 k -階差 で与えられ、明示的に書けば
a
k
=
∑
i
=
0
k
(
−
1
)
k
−
i
(
k
i
)
p
(
i
)
{\displaystyle a_{k}=\textstyle \sum \limits _{i=0}^{k}(-1)^{k-i}{\dbinom {k}{i}}p(i)}
(4 )
で決まる[注 2] 。
各二項係数多項式 ( t k ) は整数値(整数を代入したとき必ず整数を返す)である(これは例えばパスカルの等式 (英語版 ) を用いて k に関する帰納法で示せる)。従って、二項係数多項式の任意の整係数線型結合もまた整数値多項式になる。逆に等式 (4 ) により任意の整数値多項式がこれら二項係数多項式の正係数線型結合となることが示せる。より一般に標数 0 の体の任意の部分環 R に対し、K [t ] に属する多項式が任意の整数において R に値をとるための必要十分条件はそれが二項係数多項式の R -係数線型結合となっていることである。
階乗表示を用いれば近くにある二項係数の関係を容易に知ることができる。例えば k を正整数、n は任意として
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
{\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}
(5 )
が 成 り 立 ち 、 ま た 少 し の 計 算 で
(
n
−
1
k
)
−
(
n
−
1
k
−
1
)
=
n
−
2
k
n
(
n
k
)
{\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}}
が 得 ら れ る 。 さ ら に 言 え ば 以 下 の 結 果
(
n
h
)
(
n
−
h
k
)
=
(
n
k
)
(
n
−
k
h
)
{\displaystyle {\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}}
は 有 用 で あ る 。 例 え ば 定 数 n に 対 し て 以 下 の 漸 化 式
(
n
k
)
=
n
+
1
−
k
k
(
n
k
−
1
)
{\displaystyle {\binom {n}{k}}={\frac {n+1-k}{k}}{\binom {n}{k-1}}}
を 得 る こ と が で き る 。
等式
∑
k
=
0
n
(
n
k
)
=
2
n
{\displaystyle \textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}=2^{n}}
(∗∗ )
は 等 式 ( ∗ ) に お い て x = 1 か つ y = 1 と す れ ば 得 ら れ る 。 こ れ は パ ス カ ル の 三 角 形 の 各 行 に お い て 現 れ る 全 て の 数 を 足 し 合 わ せ れ ば 2 の 整 数 冪 に な る と 言 っ て も 同 じ で あ る 。 こ の 事 実 の 組 合 せ 論 的 解 釈 は 二 通 り に 数 え る 論 法 ︵ 英 語 版 ︶ ( d o u b l e c o u n t i n g ) で n 元 - 集 合 S の 位 数 i ( i = 1 , 2 , … , n ) の 部 分 集 合 を 数 え る こ と で あ る 。 任 意 の 位 数 i に 対 す る 部 分 集 合 を 数 え て い る の だ か ら 、 そ の 和 は S の 部 分 集 合 の 総 数 に 等 し く 、 そ れ が 2 n で あ る こ と は よ く 知 ら れ て い る 。 す な わ ち 、 等 式 ( ∗ ∗ ) は n 元 - 集 合 の 冪 集 合 の 位 数 が 2 n で あ る こ と を 述 べ る も の で あ る 。 よ り 明 確 に 、 n - 桁 の ビ ッ ト 列 を 考 え れ ば 、 こ の ビ ッ ト 列 は 2 n 個 の 数 を 表 す こ と に 利 用 で き る 。 そ の 中 で 一 つ も 1 を 含 ま な い ビ ッ ト 列 を 考 え れ ば 、 こ れ は ( n
0 ) = 1 通 り で あ る 。 ち ょ う ど 一 つ 1 を 含 む ビ ッ ト 列 は ( n
1 ) = n 通 り で あ る 。 こ の よ う に 数 え て 行 け ば 上 記 の 式 を 得 る 。
等 式
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
{\displaystyle \textstyle \sum \limits _{k=0}^{n}k{\dbinom {n}{k}}=n2^{n-1}}
(6 )
および
∑
k
=
0
n
k
2
(
n
k
)
=
(
n
+
n
2
)
2
n
−
2
{\displaystyle \textstyle \sum \limits _{k=0}^{n}k^{2}{\dbinom {n}{k}}=(n+n^{2})2^{n-2}}
は等式 (2 ) を x に関して(後者は2回)微分して x = 1 と置けば得られる。
朱ファンデルモンドの等式 (英語版 )
∑
j
=
0
k
(
m
j
)
(
n
−
m
k
−
j
)
=
(
n
k
)
{\displaystyle \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 )n の展開における xk の係数として、等式 (2 ) を用いて求めることができる。m = 1 のとき等式 (7 ) は等式 (3 ) に簡約される。
任意の整数 j , k , n (0 ≤ j ≤ k ≤ n ) に対して適用できる同様の等式
∑
m
=
0
n
(
m
j
)
(
n
−
m
k
−
j
)
=
(
n
+
1
k
+
1
)
{\displaystyle \textstyle \sum \limits _{m=0}^{n}{\dbinom {m}{j}}{\dbinom {n-m}{k-j}}={\dbinom {n+1}{k+1}}}
(8 )
は、
x
l
(
1
−
x
)
l
+
1
=
∑
p
=
0
∞
(
p
l
)
x
p
{\displaystyle {\frac {x^{l}}{(1-x)^{l+1}}}=\textstyle \sum \limits _{p=0}^{\infty }{\dbinom {p}{l}}x^{p}}
を用いれば
x
(
x
j
(
1
−
x
)
j
+
1
)
(
x
k
−
j
(
1
−
x
)
k
−
j
+
1
)
=
x
k
+
1
(
1
−
x
)
k
+
2
{\displaystyle 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 n +1 の係数として求められる。j = k のとき等式 (8 ) は
∑
m
=
0
n
(
m
k
)
=
(
n
+
1
k
+
1
)
{\displaystyle \textstyle \sum \limits _{m=0}^{n}{\dbinom {m}{k}}={\dbinom {n+1}{k+1}}}
となる。展開 (7 ) を n = 2m , k = m に対して用い、(1 ) を使えば
∑
j
=
0
m
(
m
j
)
2
=
(
2
m
m
)
{\displaystyle \textstyle \sum \limits _{j=0}^{m}{\dbinom {m}{j}}^{2}={\dbinom {2m}{m}}}
(9 )
を得る。
F (n ) で n 番目のフィボナッチ数 を表せば、パスカルの三角形の対角和に関する等式
∑
k
=
0
⌊
n
/
2
⌋
(
n
−
k
k
)
=
F
(
n
+
1
)
{\displaystyle \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 ) に 対 す る 閉 じ た 式 は ︵ 超 幾 何 函 数 を 用 い な け れ ば ︶ な い [ 6 ] が 、 再 び 等 式 ( 3 ) お よ び 帰 納 法 に よ り k = 0 , … , n − 1 に 対 し て ∑
k ( − 1 ) j ( n
j ) = ( − 1 ) k ( n − 1
k ) を 得 る 。 同 様 に ∑
n ( − 1 ) j ( n
j ) = 0 を 得 る [ 7 ] ︵ n = 0 の 自 明 な 場 合 は 除 く 。 こ の と き は 1 に な る ︶ 。 こ れ 自 身 は 次 数 高 々 n の 任 意 の 多 項 式 P ( x ) に 対 す る 和 分 差 分 学 に お け る 結 果 [ 8 ] ∑
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 ) に 対 し て
∑
j
=
0
n
(
−
1
)
j
(
n
j
)
P
(
n
−
j
)
=
n
!
a
n
{\displaystyle \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 に 対 し て
∑
j
=
0
n
(
−
1
)
j
(
n
j
)
P
(
m
+
(
n
−
j
)
d
)
=
d
n
n
!
a
n
{\displaystyle \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 n ⋅ a n で あ る こ と に 注 意 す れ ば 、 等 式 ( 11 ) を 適 用 し て 直 ち に 得 ら れ る 。
級 数
k
−
1
k
∑
j
=
0
∞
1
(
j
+
x
k
)
=
1
(
x
−
1
k
−
1
)
{\displaystyle {\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 に 対 し て 収 束 す る 。 こ の 等 式 は ド イ ツ の 戦 車 問 題 ︵ 英 語 版 ︶ を 調 べ る の に 利 用 で き る 。 こ れ を 見 る に は
k
−
1
k
∑
j
=
0
M
1
(
j
+
x
k
)
=
1
(
x
−
1
k
−
1
)
−
1
(
M
+
x
k
−
1
)
{\displaystyle {\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 ) 2 = n / 2 ( 2 n
n ) お よ び ∑
n i 2 ( n
i ) 2 = n 2 ( 2 n − 2
n − 1 ) が 得 ら れ る 。
S e r i e s m u l t i s e c t i o n ︵ 英 語 版 ︶ に よ り 、 0 ≤ t < s と し て t を 境 に s 刻 み に 取 っ た 二 項 係 数 の 総 和 と s 項 の 閉 じ た 形 の 式 の 和 と の 間 の 等 式
(
n
t
)
+
(
n
t
+
s
)
+
(
n
t
+
2
s
)
+
⋯
=
1
s
∑
j
=
0
s
−
1
(
2
cos
π
j
s
)
n
cos
π
(
n
−
2
t
)
j
s
{\displaystyle {\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 な る 非 負 整 数 に 対 し て
∑
k
=
q
n
(
n
k
)
(
k
q
)
=
2
n
−
q
(
n
q
)
{\displaystyle \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 通 り で あ る 。
パ ス カ ル の 法 則
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}
の 両 辺 は 集 合 [ n ] の k 元 - 部 分 集 合 を 数 え て い る の だ け れ ど も 、 右 辺 は 特 定 の 元 ︵ 例 え ば n ︶ を 含 む よ う に 選 ぶ 場 合 と 含 ま な い よ う に 選 ぶ 場 合 に 分 け て 数 え て い る 。
等 式 ( 9 ) , 再 掲 す る と
∑
k
=
0
n
(
n
k
)
2
=
(
2
n
n
)
{\displaystyle \textstyle \sum \limits _{k=0}^{n}{\dbinom {n}{k}}^{2}={\dbinom {2n}{n}}}
も 組 合 せ 論 的 に 証 明 で き る 。 2 n 個 の □ を 一 列 に 並 べ 、 そ れ ら の う ち の n 個 を 選 ん で 印 を 付 け る こ と を 考 え る 。 そ の よ う な 方 法 は ( 2 n
n ) 通 り で あ る ︵ 右 辺 ︶ 。 他 方 、 そ の よ う な n 個 の □ を 選 ぶ と き に 、 k 個 は 前 半 の n 個 か ら 、 残 り n − k 個 は 後 半 の n 個 か ら 選 ぶ と し て 1 ≤ k ≤ n に 亙 っ て 考 え る 。 こ れ に よ り ∑
n ( n
k ) ( n
n − k ) = ( 2 n
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 ) 通 り あ る こ と は 明 ら か で あ る 。
ディクソンの等式 (英語版 ) は
∑
k
=
−
a
a
(
−
1
)
k
(
2
a
k
+
a
)
3
=
(
3
a
)
!
(
a
!
)
3
{\displaystyle \textstyle \sum \limits _{k=-a}^{a}(-1)^{k}{\dbinom {2a}{k+a}}^{3}={\dfrac {(3a)!}{(a!)^{3}}}}
あるいはより一般に
∑
k
=
−
a
a
(
−
1
)
k
(
a
+
b
a
+
k
)
(
b
+
c
b
+
k
)
(
c
+
a
c
+
k
)
=
(
a
+
b
+
c
)
!
a
!
b
!
c
!
{\displaystyle \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 を非負整数として:
∫
−
π
π
cos
(
(
2
m
−
n
)
x
)
cos
n
x
d
x
=
π
2
n
−
1
(
n
m
)
{\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}x\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}}
∫
−
π
π
sin
(
(
2
m
−
n
)
x
)
sin
n
x
d
x
=
{
(
−
1
)
m
+
n
+
1
2
π
2
n
−
1
(
n
m
)
(
n
: odd
)
0
(
otherwise
)
{\displaystyle \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}}}
∫
−
π
π
cos
(
(
2
m
−
n
)
x
)
sin
n
x
d
x
=
{
(
−
1
)
m
+
n
+
1
2
π
2
n
−
1
(
n
m
)
(
n
: even
)
0
(
otherwise
)
{\displaystyle \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 ) , … の 通 常 母 函 数 は
∑
k
=
0
∞
(
n
k
)
x
k
=
(
1
+
x
)
n
{\displaystyle \textstyle \sum \limits _{k=0}^{\infty }{\dbinom {n}{k}}x^{k}=(1+x)^{n}}
で 与 え ら れ る 。 固 定 し た k に 対 し て 作 ら れ る 数 列 ( 0
k ) , ( 1
k ) , ( 2
k ) , … の 通 常 母 函 数 は
∑
n
=
k
∞
(
n
k
)
y
n
=
y
k
(
1
−
y
)
k
+
1
{\displaystyle \textstyle \sum \limits _{n=k}^{\infty }{\dbinom {n}{k}}y^{n}={\dfrac {y^{k}}{(1-y)^{k+1}}}}
で あ る 。 一 般 の 非 負 整 数 n , k に 対 す る 二 項 係 数 の 二 変 数 母 函 数 ︵ 英 語 版 ︶ は
∑
n
,
k
(
n
k
)
x
k
y
n
=
1
1
−
y
−
x
y
{\displaystyle \textstyle \sum \limits _{n,k}{\dbinom {n}{k}}x^{k}y^{n}={\dfrac {1}{1-y-xy}}}
を 満 た す 。 二 項 係 数 に 対 す る 別 の 形 の 二 変 数 母 函 数 は 、 対 称 函 数 と し て
∑
n
,
k
(
n
+
k
k
)
x
k
y
n
=
1
1
−
x
−
y
{\displaystyle \textstyle \sum \limits _{n,k}{\dbinom {n+k}{k}}x^{k}y^{n}={\dfrac {1}{1-x-y}}}
で 与 え ら れ る 。
二項係数に関する指数型二変数母函数 (英語版 ) は
∑
n
,
k
1
(
n
+
k
)
!
(
n
+
k
k
)
x
k
y
n
=
e
x
+
y
{\displaystyle \sum _{n,k}{\frac {1}{(n+k)!}}{\binom {n+k}{k}}x^{k}y^{n}=e^{x+y}}
となる。
1 8 5 2 年 、 ク ン マ ー は 非 負 整 数 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 ⁄ g c d ( n , k ) で 割 り 切 れ る こ と が 導 か れ る 。 し た が っ て 特 に 、 任 意 の 正 整 数 r お よ び s < p r な る 正 整 数 s に 対 し て p は ( p r
s ) を 割 り 切 る 。 し か し よ り 高 次 の p - 冪 に 対 し て こ れ は 正 し く な い ︵ 例 え ば 9 は ( 9
6 ) を 割 り 切 ら な い ︶ 。
S i n g m a s t e r ( 1 9 7 4 ) は ﹁ 任 意 の 整 数 が ほ と ん ど 全 て の 二 項 係 数 を 整 除 す る ﹂ と い う 幾 分 驚 く べ き 結 果 を 与 え た 。 よ り 精 確 に 言 え ば 、 整 数 d を 固 定 し て 、 f ( N ) は n < N な る 二 項 係 数 ( n
k ) の う ち d で 割 り 切 れ る も の の 総 数 を 表 す も の と す る と 、
lim
N
→
∞
f
(
N
)
N
(
N
+
1
)
/
2
=
1
{\displaystyle \lim _{N\to \infty }{\frac {f(N )}{N(N+1)/2}}=1}
が 成 り 立 つ と い う も の で あ る 。 n < N な る 二 項 係 数 ( n
k ) の 総 数 は 1 / 2 N ( N + 1 ) で あ る か ら 、 こ れ は d で 整 除 可 能 な も の の 占 め る 密 度 が 1 に 収 束 す る こ と を 意 味 す る 。
別 の 事 実 と し て 、 整 数 n ≥ 2 が 素 数 と な る 必 要 十 分 条 件 は 、 中 間 二 項 係 数
(
n
1
)
,
(
n
2
)
,
…
,
(
n
n
−
1
)
{\displaystyle {\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}}
の 全 て が n で 整 除 可 能 な こ と で あ る 。 実 際 、 p が 素 数 な ら ば 、 0 < k < p な る 任 意 の k に 対 し て p は
(
p
k
)
=
p
⋅
(
p
−
1
)
⋯
(
p
−
k
+
1
)
k
⋅
(
k
−
1
)
⋯
1
{\displaystyle {\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 か つ
(
n
p
)
=
n
(
n
−
1
)
(
n
−
2
)
⋯
(
n
−
p
+
1
)
p
!
=
k
(
n
−
1
)
(
n
−
2
)
⋯
(
n
−
p
+
1
)
(
p
−
1
)
!
{\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)!}}}
は 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 ) に 関 し て 以 下 の 評 価
(
n
k
)
k
≤
(
n
k
)
≤
n
k
k
!
≤
(
n
⋅
e
k
)
k
{\displaystyle \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 ( 2 n
n ) ≥ 2 2 n − 1 , 一 般 に
n
(
m
n
n
)
≥
m
m
(
n
−
1
)
+
1
(
m
−
1
)
(
m
−
1
)
(
n
−
1
)
{\displaystyle {\sqrt {n}}{\binom {mn}{n}}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}}
が m ≥ 2 か つ n ≥ 1 に 対 し て 成 立 す る 。 ま た n → ∞ の と き 近 似
(
2
n
n
)
∼
4
n
π
n
{\displaystyle {\binom {2n}{n}}\sim {\frac {4^{n}}{\sqrt {\pi n}}}}
が 成 り 立 つ 。 n , k が と も に 1 よ り 十 分 大 き け れ ば ス タ ー リ ン グ 近 似 か ら は 以 下 の 漸 近 近 似
log
2
(
n
k
)
∼
n
H
(
k
n
)
{\displaystyle \log _{2}{\binom {n}{k}}\sim nH\left({\frac {k}{n}}\right)}
も 従 う 。 こ こ に H ( ε ) = − ε l o g 2 ( ε ) − ( 1 − ε ) l o g 2 ( 1 − ε ) は ε の 二 値 エ ン ト ロ ピ ー 関 数 で あ る 。 よ り 精 確 に 、 任 意 の 整 数 n ≥ k ≥ 1 と ε ≐ k / n ≤ 1 / 2 に 対 し て 、 最 初 の k + 1 個 の 二 項 係 数 の 和 を
1
8
n
ϵ
(
1
−
ϵ
)
⋅
2
H
(
ϵ
)
⋅
n
≤
∑
i
=
0
k
(
n
i
)
≤
2
H
(
ϵ
)
⋅
n
{\displaystyle {\frac {1}{\sqrt {8n\epsilon (1-\epsilon )}}}\cdot 2^{H(\epsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon )\cdot n}}
と 評 価 す る こ と が で き る [ 10 ] 。
n が 大 き く 、 k が n に 対 し て 十 分 小 さ い と き
(
n
k
)
=
n
(
n
−
1
)
…
(
n
−
k
+
1
)
k
!
≈
(
n
−
k
/
2
)
k
k
k
e
−
k
2
π
k
=
(
n
/
k
−
0.5
)
k
e
k
2
π
k
{\displaystyle \textstyle {\binom {n}{k}}={\frac {n(n-1)\dots (n-k+1)}{k!}}\approx {\frac {(n-k/2)^{k}}{k^{k}e^{-k}{\sqrt {2\pi k}}}}={\frac {(n/k-0.5)^{k}e^{k}}{\sqrt {2\pi k}}}}
と 書 く こ と が で き る の で 、
log
(
n
k
)
≈
k
ln
(
n
k
−
0.5
)
+
k
−
0.5
ln
(
2
π
k
)
{\displaystyle \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
(
n
k
)
≈
(
n
+
0.5
)
ln
n
+
0.5
n
−
k
+
0.5
+
k
ln
n
−
k
+
0.5
k
−
0.5
ln
(
2
π
k
)
{\displaystyle \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 = 2 0 か つ k = 1 0 に 対 し て l o g ( n
k ) ≈ 1 2 . 1 2 7 お よ び こ れ ら 近 似 式 か ら そ れ ぞ れ 近 似 値 1 2 . 3 1 2 お よ び 1 2 . 1 3 3 を 得 る 。
ガ ン マ 函 数 の 無 限 積 表 示 に 基 づ く 無 限 積
(
−
1
)
k
(
z
k
)
=
(
−
z
+
k
−
1
k
)
=
1
Γ
(
−
z
)
1
(
k
+
1
)
z
+
1
∏
j
=
k
+
1
(
1
+
1
j
)
−
z
−
1
1
−
z
+
1
j
{\displaystyle (-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}}}}}
か ら 漸 近 公 式
(
z
k
)
≈
(
−
1
)
k
Γ
(
−
z
)
k
z
+
1
,
(
z
+
k
k
)
=
k
z
Γ
(
z
+
1
)
(
1
+
z
(
z
+
1
)
2
k
+
O
(
k
−
2
)
)
{\displaystyle {\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 → ∞ で 成 り 立 つ 。 こ の 漸 近 挙 動 は 近 似
(
z
+
k
k
)
≈
e
z
(
H
k
−
γ
)
Γ
(
z
+
1
)
{\displaystyle {\binom {z+k}{k}}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}
に も 表 れ て い る 。 こ こ に 、 H k は k 番 目 の 調 和 数 で 、 γ は オ イ ラ ー – マ ス ケ ロ ー ニ 定 数 で あ る 。 さ ら に 、 k → ∞ か つ 適 当 な 複 素 数 x に 対 し て j / k → x な る と き 、 漸 近 公 式
(
z
+
k
j
)
(
k
j
)
→
(
1
−
j
k
)
−
z
,
(
j
j
−
k
)
(
j
−
z
j
−
k
)
→
(
j
k
)
z
{\displaystyle {\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}}
が 成 り 立 つ 。
二 項 係 数 の 和 に つ い て 、 二 項 定 理 を 用 い る と
∑
i
=
0
k
(
n
i
)
≤
∑
i
=
0
k
n
i
⋅
1
k
−
i
=
(
1
+
n
)
k
{\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}=(1+n)^{k}}
と い う 単 純 で 粗 い 上 界 が 得 ら れ る 。
n が 十 分 大 き い と き 、
(
n
k
)
=
2
n
1
2
n
π
e
−
(
k
−
(
n
/
2
)
)
2
n
/
2
[
1
+
O
(
1
n
)
]
{\displaystyle {\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 n を 掛 け れ ば 、 中 心 極 限 定 理 に 対 す る 評 価 か ら 従 う 。
二 項 係 数 を 一 般 化 す る も の と し て
(
n
k
1
,
k
2
,
…
,
k
r
)
=
n
!
k
1
!
k
2
!
⋯
k
r
!
(
∑
i
=
1
r
k
i
=
n
)
{\displaystyle {\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 ) n の 係 数 で あ っ た の に 対 し 、 多 項 係 数 は ( x 1 + x 2 + … + x r ) n の 多 項 式 展 開 の 係 数 で あ り 、 r = 2 の と き 二 項 係 数 を 与 え る :
(
n
k
1
,
k
2
)
=
(
n
k
1
,
n
−
k
1
)
=
(
n
k
1
)
=
(
n
k
2
)
.
{\displaystyle {\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 個 の 元 を 含 む よ う な 分 け 方 の 総 数 と し て 組 合 せ 論 的 に 解 釈 で き る 。
多 項 係 数 は 二 項 係 数 の 性 質 と よ く 似 た た く さ ん の 性 質 を 満 た す 。 例 え ば 漸 化 式
(
n
k
1
,
k
2
,
…
,
k
r
)
=
(
n
−
1
k
1
−
1
,
k
2
,
…
,
k
r
)
+
(
n
−
1
k
1
,
k
2
−
1
,
…
,
k
r
)
+
⋯
+
(
n
−
1
k
1
,
k
2
,
…
,
k
r
−
1
)
{\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{r}}}={\binom {n-1}{k_{1}-1,k_{2},\ldots ,k_{r}}}+{\binom {n-1}{k_{1},k_{2}-1,\ldots ,k_{r}}}+\dotsb +{\binom {n-1}{k_{1},k_{2},\ldots ,k_{r}-1}}}
お よ び 任 意 の 置 換 σ に 関 す る 対 称 性
(
n
k
1
,
k
2
,
…
,
k
r
)
=
(
n
k
σ
1
,
k
σ
2
,
…
,
k
σ
r
)
{\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{r}}}={\binom {n}{k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}}}
が 挙 げ ら れ る 。 た だ し 、 ( σ i ) は ( 1 , 2 , … , r ) を 並 べ 替 え た も の で あ る 。
第一種スターリング数 を用いれば、二項係数の任意に選んだ点 z 0 の周りでのテイラー展開 は
(
z
k
)
=
1
k
!
∑
i
=
0
k
z
i
s
k
,
i
=
∑
i
=
0
k
(
z
−
z
0
)
i
∑
j
=
i
k
(
z
0
j
−
i
)
s
k
+
i
−
j
,
i
(
k
+
i
−
j
)
!
=
∑
i
=
0
k
(
z
−
z
0
)
i
∑
j
=
i
k
z
0
j
−
i
(
j
i
)
s
k
,
j
k
!
{\displaystyle {\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 に対して
(
1
/
2
k
)
=
(
2
k
k
)
(
−
1
)
k
+
1
2
2
k
(
2
k
−
1
)
{\displaystyle {\binom {1/2}{k}}={\binom {2k}{k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}}
が成り立つ。これは二項級数展開 √ 1 + x = ∑k ≥0 ( 1/2k ) xk に現れる。
二項係数の積は二項係数の線型結合として
(
z
m
)
(
z
n
)
=
∑
k
=
0
m
(
m
+
n
−
k
k
,
m
−
k
,
n
−
k
)
(
z
m
+
n
−
k
)
{\displaystyle {\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つの部分に分ける方法)の総数である。このように見ると、二項係数の母函数は下降階乗冪 に対する通常母函数に対応する指数型母函数である。
二項係数の逆数の部分分数分解 は
1
(
z
n
)
=
∑
i
=
0
n
−
1
(
−
1
)
n
−
1
−
i
(
n
i
)
n
−
i
z
−
i
{\displaystyle {\frac {1}{\binom {z}{n}}}=\textstyle \sum \limits _{i=0}^{n-1}(-1)^{n-1-i}{\dbinom {n}{i}}{\dfrac {n-i}{z-i}}}
および
1
(
z
+
n
n
)
=
∑
i
=
1
n
(
−
1
)
i
−
1
(
n
i
)
i
z
+
i
{\displaystyle {\frac {1}{\binom {z+n}{n}}}=\textstyle \sum \limits _{i=1}^{n}(-1)^{i-1}{\dbinom {n}{i}}{\dfrac {i}{z+i}}}
で与えられる。
ア イ ザ ッ ク ・ ニ ュ ー ト ン に 名 を 因 む ニ ュ ー ト ン の 二 項 級 数 は 、 二 項 定 理 の 級 数 版
(
1
+
z
)
α
=
∑
n
=
0
∞
(
α
n
)
z
n
=
1
+
(
α
1
)
z
+
(
α
2
)
z
2
+
⋯
{\displaystyle (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 で あ る 。
1
(
1
−
z
)
α
+
1
=
∑
n
=
0
∞
(
n
+
α
n
)
z
n
{\displaystyle {\frac {1}{(1-z)^{\alpha +1}}}=\textstyle \sum \limits _{n=0}^{\infty }{\dbinom {n+\alpha }{n}}z^{n}}
と も 書 け る 。
二 項 係 数 は 与 え ら れ た 集 合 か ら 決 め ら れ た 位 数 の 部 分 集 合 を 数 え 上 げ る も の で あ っ た 。 関 連 す る 組 合 せ 論 的 問 題 と し て 、 与 え ら れ た 集 合 か ら 元 を と っ て 作 ら れ る 決 め ら れ た 位 数 の 多 重 集 合 を 数 え 上 げ る 問 題 、 す な わ ち 与 え ら れ た 集 合 か ら 重 複 を 許 し て 決 め ら れ た 数 の 元 を 選 び 出 す 重 複 組 合 せ の 問 題 が あ る 。 そ の 総 数 は 多 重 集 合 係 数 と 呼 ば れ [ 11 ] 、 n 個 の 元 か ら k 個 選 ぶ 重 複 組 合 せ の 総 数 は
(
(
n
k
)
)
{\displaystyle \left(\!{\tbinom {n}{k}}\!\right)}
と 書 か れ る 。
以 下 議 論 の 便 宜 の た め n を 使 わ ず に 、 そ の 代 わ り f = r + ( k − 1 ) お よ び r = f − ( k − 1 ) な る 非 負 整 数 f , r を 用 い る 。
多 重 集 合 係 数 は 以 下 に 示 す 関 係
(
f
k
)
=
(
(
r
k
)
)
=
(
r
+
k
−
1
k
)
{\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}}
に よ り 二 項 係 数 と し て 書 け る 。 こ の 等 式 を 以 下 の よ う に も 特 徴 づ け る こ と が で き る 。
(
f
)
k
=
f
k
_
=
(
f
−
k
+
1
)
⋯
(
f
−
3
)
⋅
(
f
−
2
)
⋅
(
f
−
1
)
⋅
f
,
r
(
k
)
=
r
k
¯
=
r
⋅
(
r
+
1
)
⋅
(
r
+
2
)
⋅
(
r
+
3
)
⋯
(
r
+
k
−
1
)
{\displaystyle {\begin{aligned}(f )_{k}&=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,\\r^{(k )}&=r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1)\end{aligned}}}
が 等 し い こ と に 注 意 す れ ば 、 二 項 係 数 を 下 降 階 乗 冪 を 用 い て
(
f
k
)
=
(
f
)
k
k
!
=
(
f
−
k
+
1
)
⋯
(
f
−
2
)
⋅
(
f
−
1
)
⋅
f
1
⋅
2
⋅
3
⋅
4
⋅
5
⋯
k
{\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}}}
と 書 く と き 、 対 応 す る 多 重 集 合 係 数 は 下 降 階 乗 冪 を 対 応 す る 上 昇 階 乗 冪 で 置 き 換 え た
(
(
r
k
)
)
=
r
(
k
)
k
!
=
r
⋅
(
r
+
1
)
⋅
(
r
+
2
)
⋯
(
r
+
k
−
1
)
1
⋅
2
⋅
3
⋅
4
⋅
5
⋯
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
k
)
=
−
n
⋅
−
(
n
+
1
)
⋯
−
(
n
+
k
−
2
)
⋅
−
(
n
+
k
−
1
)
k
!
=
(
−
1
)
k
n
⋅
(
n
+
1
)
⋅
(
n
+
2
)
⋯
(
n
+
k
−
1
)
k
!
=
(
−
1
)
k
(
n
+
k
−
1
k
)
=
(
−
1
)
k
(
(
n
k
)
)
{\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}}}
が成り立つ。特に、負の整数における二項係数は符号付多重集合係数である。n = −1 なる特別の場合には、これは
(
−
1
)
k
=
(
−
1
k
)
=
(
(
−
k
k
)
)
{\displaystyle (-1)^{k}={\tbinom {-1}{k}}={\big (}\!{\tbinom {-k}{k}}\!{\big )}}
と簡単になる。
ガ ン マ 函 数 や ベ ー タ 函 数 を 用 い て
(
x
y
)
=
Γ
(
x
+
1
)
Γ
(
y
+
1
)
Γ
(
x
−
y
+
1
)
=
1
(
x
+
1
)
B
(
x
−
y
+
1
,
y
+
1
)
{\displaystyle {\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 つ の 引 数 を 任 意 の 実 数 ま た は 複 素 数 ま で 一 般 化 す る こ と が で き る 。 こ の 定 義 に お い て ガ ン マ 函 数 の 性 質 を 用 い れ ば 、
(
x
y
)
=
sin
(
y
π
)
sin
(
x
π
)
(
−
y
−
1
−
x
−
1
)
=
sin
(
(
x
−
y
)
π
)
sin
(
x
π
)
(
y
−
x
−
1
y
)
{\displaystyle {\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}}}
が 満 た さ れ る こ と も 分 か る 。 特 に
(
x
y
)
⋅
(
y
x
)
=
sin
(
(
x
−
y
)
π
)
(
x
−
y
)
π
{\displaystyle {\binom {x}{y}}\cdot {\binom {y}{x}}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}}
で あ る 。 こ の 一 般 化 に 関 す る 研 究 は 少 な い が 、 ( F o w l e r 1 9 9 6 ) な ど に は す で に 現 れ て い る 。 通 常 の 二 項 係 数 に 関 す る 多 く の 等 式 が も は や 成 り 立 た な く な っ て い る こ と に 注 意 す べ き で あ る ︵ 例 え ば 正 の n に 対 し て ( n
m ) = ( n
n − m ) や ( − n
m ) = ( − n
− n − m ) は 一 般 に は 正 し く な い ︶ 。 そ の 挙 動 は 極 め て 複 雑 で 、 x 軸 、 y 軸 と 直 線 y = x で 分 け ら れ る 八 分 象 限 ( o c t a n t ) の ど の 位 置 に あ る か で 著 し く 異 な る 。 負 の x に 対 し て は 負 の 整 数 の 位 置 に 特 異 点 を 持 ち 、 正 と 負 の 領 域 が 市 松 模 様 を 成 す :
● 0 ≤ y ≤ x な る 八 分 象 限 で は 、 通 常 の 二 項 係 数 を 滑 ら か に 補 間 し 、 稜 線 を 成 す ︵ ﹁ パ ス カ ル の 稜 線 ﹂ ( " P a s c a l ' s r i d g e " ) ︶ 。
● 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 -類似 はガウスの二項係数 (英語版 ) と呼ばれる。
部 分 集 合 の 数 を 数 え る 二 項 係 数 の 組 合 せ 論 的 定 義 を 、 基 数 α , β に 対 し て 濃 度 α を 持 つ 適 当 な 集 合 A を と っ て
(
α
β
)
=
|
{
B
⊆
A
:
|
B
|
=
β
}
|
{\displaystyle {\binom {\alpha }{\beta }}=|\{B\subseteq A:|B|=\beta \}|}
の 形 に 表 せ ば 、 無 限 基 数 に 対 し て も 一 般 化 で き る 。 基 数 α を 表 す 集 合 A の 取 り 方 に 依 ら ず ( α
β ) が 等 し い と い う 意 味 で こ の 一 般 化 は う ま く 定 義 さ れ て い る 。 有 限 基 数 に 対 し て こ れ が 通 常 の 二 項 係 数 の 定 義 に 一 致 す る の は 明 ら か で あ ろ う 。
選 択 公 理 を 仮 定 す れ ば 、 任 意 の 無 限 基 数 α に 対 し て ( α
α ) = 2 α が 示 せ る 。
^ Lilavati Section 6, Chapter 4 (see Knuth (1997) ).
^ Higham (1998)
^ Shilov (1977 , p. 92 )
^ Holton, Pedersen (1997), Mathematical Reflections: In a Room With Many Mirrors , Springer, ISBN 978-1-4612-1932-3
^ Thomas, Muir (1904). “Note on selected combinations” . Proceedings of the Royal Society of Edinburgh . doi :10.1017/S0370164600007768 . https://books.google.co.jp/books/reader?id=EN8vAAAAIAAJ&output=reader&pg=GBS.PA102&redir_esc=y&hl=ja .
^ Boardman, Michael (2004), “The Egg-drop numbers” , Mathematics Magazine 77 (5): 368-372, JSTOR 3219201 , MR 1573776 , https://jstor.org/stable/3219201 , "it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients" .
^ see induction developed in eq (7) p.1389 in Aupetit, Michael (2009), “Nearly homogeneous multi-partitioning with a deterministic generator”, Neurocomputing 72 (7-9): 1379-1389, doi :10.1016/j.neucom.2008.12.024 , ISSN 0925-2312 .
^ Ruiz, Sebastian (1996). “An algebraic identity leading to Wilson's theorem” . The Mathematical Gazette 80 (489): 579-582. doi :10.2307/3618534 . http://www.jstor.org/stable/3618534 .
^ see e.g. Ash (1990 , p. 121) or Flum & Grohe (2006 , p. 427).
^ Munarini, Emanuele (2011), “Riordan matrices and sums of harmonic numbers”, Applicable Analysis and Discrete Mathematics 5 (2): 176-200, doi :10.2298/AADM110609014M , MR 2867317 .
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