# 二項係数 ## 定義 n要素集合のk要素部分集合の個数を表す記号 $\binom{n}{k}$(「n choose k」と読む)を二項係数(binomial coefficient)と呼ぶ。部分集合の規則(Subset Rule、定理14.5.1)により $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ が成り立つ。この式は、n要素集合の順列(n!通り)を「先頭k個の要素からなる部分集合」へ写す写像を考え、同じ部分集合に写る順列がちょうど k!(n−k)! 個ずつ存在すること(先頭k個の並べ方 k! 通り × 残りn−k個の並べ方 (n−k)! 通り)を除法の規則で処理することで導かれる。二項係数はn要素集合をサイズ$(k_1,\dots,k_m)$の複数の部分集合へ分割する場合の数を与える多項係数 $\binom{n}{k_1,\dots,k_m} \coloneqq n!/(k_1!\cdots k_m!)$ の特別な場合(m=2)であり、後者は繰り返し文字を含む数列の並べ替え数(簿記の規則、Bookkeeper Rule)としても現れる。二項係数の名前の由来である二項定理(Binomial Theorem)は $(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k$ を主張し、$(a+b)^n$ を分配法則で展開した際にb をk個・aをn−k個含む項の個数が$\binom{n}{k}$個であることから、簿記の規則により証明される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.5〜§14.6) ## 横断的知見 - 二項係数の総和 $\sum_{k=0}^n \binom{n}{k} = 2^n$ という事実は、第14章では二項定理に a=b=1 を代入することで代数的に得られる(暗黙の系)。一方、第4章はこれと同じ事実 $|\mathrm{pow}(A)|=2^n$(n要素集合の部分集合の総数が$2^n$であること)を、部分集合とn桁ビット列の間の明示的な全単射を構成することで独立に証明している(定理4.5.5)。両章を突き合わせると、同一の等式 $\sum_k \binom{n}{k}=2^n$ に対して、第4章は「全単射による直接証明」、第14章は「二項定理という代数的な系」という異なる経路からたどり着いており、これ自体が第14章§14.10で導入される組合せ論的証明(同じ量を2通りに数えて等式を導く技法)の先取り的な実例になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] 定理4.5.5, [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.6.3) ## 未解決の問い - 二項係数の漸近的な振る舞い(nが大きいときに$\binom{n}{k}$がどう増大するか、特に中心付近の$\binom{n}{n/2}$の大きさ)は第14章では扱われない。第13章の[[和の近似]]・Stirlingの近似公式を使えばおおよその評価が可能なはずだが、その具体的な計算は本章の範囲外であり、後続章または確率論の章(第16〜20章)で二項分布との関連で扱われる可能性がある。 - 第14章§14.9.5は包除原理を使ってEulerのφ関数の明示公式を証明するが、二項係数と包除原理の一般的な関係(包除原理の各項の係数が二項係数的な構造を持つこと)は明示的には論じられていない。[[包除原理]] の横断的知見でこの関係を確認する余地がある。 ## 関連 - 概念: [[数え上げ]] / [[濃度]](部分集合の総数$2^n$の別証明) / [[包除原理]] / [[鳩の巣原理]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 14 §14.5〜§14.6, §14.10.