Def：binomial coefficient
二項係数とは, 整数 $n \ge 0$ および $0 \le k \le n$ に対して次の式で定義される.\[\binom{n}{k} = \frac{n!}{k! \, (n-k)!}\]ここで, $n!$ は階乗であり,\[n! = n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1, \quad 0! = 1\]と定義される.また, 二項係数 $\binom{n}{k}$ は, $n$ 個の異なる物から $k$ 個を順序を考慮せずに選ぶ組み合わせの数を表す.
$n$ 個の異なる物から $k$ 個を順序を考慮して選ぶ場合, まず 1つ目 に選ぶ物は $n$ 通りある.
次に 2つ目 に選ぶ物は, すでに1つ選んでいるので残り $n-1$ 通りある.
同様に 3つ目 は残り $n-2$ 通り, \dots 最後の $k$ 個目は残り $n-(k-1) = n-k+1$ 通りから選ぶことになる.
したがって, 順序を考慮した $k$ 個の選び方の総数は, これらの数を掛け合わせた\[n \cdot (n-1) \cdot (n-2) \cdots (n-k+1)\]で表される.
上式は階乗を使うと次のように書き換えられる.\[n \cdot (n-1) \cdot \dots \cdot (n-k+1) = \frac{n!}{(n-k)!}\]ここで, $n! = n \cdot (n-1) \cdot \dots \cdot 1$ と定義される.
分子の $n!$ は $n$ 個の全ての物を順序付きで並べる総数である.
分母の $(n-k)!$ は残り $n-k$ 個の物の順列数を除外することで, 最初の $k$ 個を順序付きで選ぶ場合の数を得る.
次に, 順序を考慮せず $k$ 個の組み合わせを考える場合, 同じ $k$ 個の選択肢が $k!$ 通りずつ順列として重複してカウントされている.
したがって $k!$ で割ると順序を無視した組み合わせの数が得られる.\[\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1)}{k!} = \frac{n!}{k!(n-k)!}\]これが二項係数 $\binom{n}{k}$ の定義であり, $n$ 個の異なる物から $k$ 個を順序を考慮せずに選ぶ組み合わせの数を表す.
Mathematics is the language with which God has written the universe.