1.2. 数学記号

本書で利用される数学記号を次に示す:

$N = {0, 1, 2, \dots}$ と定める。つまり $0 \in N$ が成り立つ。
有限集合 $S$ の大きさ (濃度) を $∣ S ∣$ と表記する。
集合 $S$ の冪集合 (powerset) とは、 $S$ の部分集合全体からなる集合を意味する。集合 $S$ の冪集合を $P (S)$ と表記する。さらに、集合 $S$ と整数 $k$ に対して、 $k$ 個の要素を持つ $S$ の部分集合全体からなる集合を $P_{k} (S)$ と表す。例えば、次の等式が成り立つ:

$P_{2} ({1, 2, 3}) = {{1, 2}, {1, 3}, {2, 3}}$
任意の実数 $n$ と任意の $k \in N$ に対して、二項係数 (binomial coefficient) と呼ばれる値 $(k n)$ を次のように定める:

$(k n) : = \frac{n ( n - 1 ) ( n - 2 ) \dots ( n - k + 1 )}{k !} = \frac{i = 0 \prod k - 1 ( n - i )}{k !}$

二項係数は興味深い性質を多く持つ。詳しくは [19fco, Chapter 2] などの数え上げ組合せ論の教科書を参照してほしい。二項係数の最も重要な性質を示す:
- 階乗公式: $n, k \in N$ かつ $n \geq k$ なら $(k n) = \frac{n !}{k ! \cdot ( n - k ) !}$ が成り立つ。
- 組合せ論的解釈: $n, k \in N$ とする。 $S$ が $n$ 要素の集合なら、 $(k n)$ は $k$ 個の要素を持つ $S$ の部分集合の個数と等しい。言い換えれば、 $∣ P_{k} (S) ∣ = (k n)$ が成り立つ。
- パスカルの再帰方程式: 任意の実数 $n$ と任意の正の整数 $k$ に対して、次の等式が成り立つ:
  
  $(k n) = (k - 1 n - 1) + (k n - 1)$