1.2. 数学記号

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

• \(\mathbb{N}=\left\{0,1,2,\ldots\right\} \) と定める。つまり \(0\in\mathbb{N}\) が成り立つ。

• 有限集合 \(S\) の大きさ (濃度) を \(\left\vert S\right\vert \) と表記する。

• 集合 \(S\) の冪集合 (powerset) とは、\(S\) の部分集合全体からなる集合を意味する。集合 \(S\) の冪集合を \(\mathcal{P}\left( S\right) \) と表記する。 さらに、集合 \(S\) と整数 \(k\) に対して、\(k\) 個の要素を持つ \(S\) の部分集合全体からなる集合を \(\mathcal{P}_{k}\left( S\right) \) と表す。例えば、次の等式が成り立つ:

  \[ \mathcal{P}_{2}\left( \left\{1,2,3\right\} \right) =\left\{\left\{1,2\right\} ,\ \left\{1,3\right\} ,\ \left\{2,3\right\}\right\} \]

• 任意の実数 \(n\) と任意の \(k\in\mathbb{N}\) に対して、二項係数 (binomial coefficient) と呼ばれる値 \(\dbinom{n}{k}\) を次のように定める:

  \[ \dbinom{n}{k} \colonequals \dfrac{n\left( n-1\right) \left( n-2\right) \cdots\left( n-k+1\right) }{k!}=\dfrac{\displaystyle \prod_{i=0}^{k-1}\left( n-i\right) }{k!} \]

  二項係数は興味深い性質を多く持つ。詳しくは [19fco, Chapter 2] などの数え上げ組合せ論の教科書を参照してほしい。二項係数の最も重要な性質を示す:

  • 階乗公式: \(n,k\in\mathbb{N}\) かつ \(n\geq k\) なら \(\dbinom{n}{k}=\dfrac{n!}{k!\cdot\left( n-k\right) !}\) が成り立つ。

  • 組合せ論的解釈: \(n,k\in\mathbb{N}\) とする。\(S\) が \(n\) 要素の集合なら、\(\dbinom{n}{k}\) は \(k\) 個の要素を持つ \(S\) の部分集合の個数と等しい。言い換えれば、\(\left\vert \mathcal{P}_{k}\left( S\right) \right\vert =\dbinom{n}{k}\) が成り立つ。

  • パスカルの再帰方程式: 任意の実数 \(n\) と任意の正の整数 \(k\) に対して、次の等式が成り立つ:

    \[ \dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k} \]