先ず階乗から。
0! = 1, 1! = 1, 2! = 1×2 = 2, 3! = 1×2×3 = 6, ……
というように, n > 0 が自然数のとき,
n! = n×(n-1)!
と決め, これを n の階乗 (factorial) という。 n! は n が少し大きくなるだけで, 驚くほど大きくなる。
これを用いて
と定義し, これを二項係数 binomial coefficient という。 記号 C は組み合わせ combination という意味である。
公式:
(1) nCn = nC0 = 1.
(2) nC1 = n.
(3) nCr = nCn-r.
(4) nCr + nCr-1 = n+1Cr. (この公式はパスカルの三角形と関係している)
(1) — (3) の証明は ! で書いた定義に代入すればすぐ得られるので省略。
(4) の証明:
これに意味をつければつけられないわけではないが, 意味をつけると却って分かりにくいと思われるので省略 (笑)。