📂レンマ

組合せ論における分割原理

定理 ¹

多対1写像の定義

有限集合 $S$ と $T$、および自然数 $d \in \mathbb{N}$ が与えられているとする。各 $s \in S$ に対してちょうど $d$ 個の $t \in T$ が $f(t) = s$ のように対応する関数 $f : T \to S$ を $d$対一^$d$-to-oneと呼ぶ。

分割原理^{division principal}

有限集合 $S$ と $T$ の間に $d$対一の対応 $f : T \to S$ が存在するとき、次が成り立つ。 $$ |S| = {\frac{ |T| }{ d }} $$ ここで $|X|$ は集合 $X$ の基数である。

説明

例えば上の図のように定義された関数 $f$ は3対1の対応である。

多対1対応はその名の通り一対一対応^{one-to-one corresponding}の一般化であり、$d = 1$ の場合はちょうど単射^injectiveである².

分割原理は多対1対応の定義から自然に得られる結論であり、別個の証明は省略する。

例: 円順列

分割原理の代表的な応用として円順列^{circular permutations}を考える。$n$ 個のアイテムがあるとき、それらを一列に並べることを順列と呼び、その場合の数は通常 $_{n} P _{n} = n!$ のように表される。

一方、円順列は開始と終了が存在しない円卓にこれらを並べることとして定義され、配置自体が異なって見えても回転によって同じ形を取るなら同一の円順列と見なす。‘円卓’や’回転’という表現を使わずに数学的に円順列を扱うには、まず次のように有限リストに対するシフト演算子^{shift operator} $S$ を定義する方法がある。 $$ \begin{align*} S :& \left( a_{1} , \cdots , a_{n} \right) \mapsto \left( a_{2} , \cdots , a_{n} , a_{1} \right) \\ S^{k} :=& S \circ S^{k-1} \end{align*} $$ シフト演算子はご覧の通りリストの最初のアイテムを最後に送る操作であり、上付きは演算子が何度も適用されたことを意味する。したがって、二つのリスト $L_{1}$ と $L_{2}$ が円順列の文脈で等しいという同値関係 $L_{1} \equiv L_{2}$ は、$L_{1} = S^{k} \left( L_{2} \right)$ を満たす自然数 $k$ が存在するということと同値である、として定義できる。アイテムの数が $n$ のとき、リスト $L$ は次のように $n$ 個の変形を持つ。 $$ L \equiv S \left( L \right) \equiv \cdots \equiv S^{n-1} \left( L \right) $$ ここで $T$ を単に $n$ 個のアイテムから作られる順列の集合とし、$S$ を $n$ 個のアイテムから作られる円順列の集合とする。このとき $f : T \to S$ は一つの円順列 $s \in S$ に対して $n$ 個の順列 $t \in T$ が対応する $n$対一の対応となる。分割原理によれば $S$ の基数は次のようになり、$S$ の基数はすなわち $n$ 個のアイテムから作られる円順列の総数となる。 $$ \left| S \right| = {\frac{ \left| T \right| }{ n }} = \frac{ n! }{ n } = (n - 1)! $$