大学の『集合論』 と 高校の『場合の数』 との関係
有限集合 $A_1,\dots,A_k$ が相互に素、すなわち $i\ne j$ なら $A_i\cap A_j=\varnothing$ とする。このとき
$$
\left|\bigcup_{i=1}^k A_i\right|=\sum_{i=1}^k |A_i|
$$
が成り立つ。
数学的帰納法により示す。
- $k=1$ の場合
$|A_{1}|=|A_{1}|$より、これは明らか。
$ $ - $k=2$ の場合
$ |A_1| = n $ および $ |A_2| = m $ とすると、$A_1$ と $A_2$ それぞれに対して、
$$ f: A_1 \to \{1,2,\dots,n\} \quad\text{および}\quad g: A_2 \to \{1,2,\dots,m\} $$
が全単射として存在する(証明下の補足を参照)。これらを用いて、
$$ h: A_1 \cup A_2 \to \{1,2,\dots,n+m\} $$
を、$A_1\cap A_2=\varnothing$ より(仮定)、任意の $x\in A_1\cup A_2$ はちょうど一方にのみ属することから、
$$ h(x) = \begin{cases} f(x), & \text{if } x\in A_1,\\ n + g(x), & \text{if } x\in A_2, \end{cases} $$
と定めると、$h$ は全単射となる(証明下の補足を参照)。
これにより、$h$ の像の要素数は$\{1,2,\cdots,n+m\}$の要素数に等しい。
したがって、
$$ |A_1 \cup A_2| = n + m = |A_1| + |A_2| $$
となることが確認できる。
$ $ - 帰納法の仮定
そこで、ある自然数 $k\geq 1$ に対して、互いに素な有限集合 $A_1, A_2, \dots, A_k$ について
$$ \left|\bigcup_{i=1}^k A_i\right| = \sum_{i=1}^k |A_i| $$
が成立すると仮定する。
$ $ - $k+1$の場合
次に、$A_1, A_2, \dots, A_k, A_{k+1}$ が互いに素であるとする。このとき、和集合の定義から、
$$ \bigcup_{i=1}^{k+1} A_i = \left(\bigcup_{i=1}^k A_i\right) \cup A_{k+1} $$
である。ここで、$\bigcup_{i=1}^k A_i$ という集合と $A_{k+1}$ という集合は互いに素である
（なぜなら、各 $A_i$ 同士が互いに素であるため...証明下の補足を参照）。
したがって、$2$つの集合の場合の結果より、
$$ \left|\left(\bigcup_{i=1}^k A_i\right) \cup A_{k+1}\right| = \left|\bigcup_{i=1}^k A_i\right| + |A_{k+1}| $$
左辺は、あらためて$\bigcup_{i=1}^{k+1} A_i$であり、
右辺の第一項は帰納法の仮定により $\left|\bigcup_{i=1}^k A_i\right| = \sum_{i=1}^k |A_i|$ であるため、
$$ \left|\bigcup_{i=1}^{k+1} A_i\right| = \sum_{i=1}^k |A_i| + |A_{k+1}| = \sum_{i=1}^{k+1} |A_i| $$
$ $
-これにより、$k+1$ 個の場合も成立することが示され、
帰納法により任意の自然数 $k$ に対して命題が成立することが証明された。
$$ \Box$$
集合 $A$ に対して、ある $n\in\mathbb N_0$ との全単射
$$
\varphi : [n] \longrightarrow A
$$
が存在するとき、$A$ を有限集合といい、そのときの $n$ を $|A|$ と書く。
$ $
すなわち、証明中の$|A_1|=n$ から、定義より、ある全単射
$$
\varphi : [n] \longrightarrow A_1
$$
が存在し、全単射には逆写像が存在するので、
$$
\varphi^{-1} : A_1 \longrightarrow [n]
$$
もまた全単射である。ここで $\{1,\dots,n\}:=[n]$ なので、
$$
f := \varphi^{-1} : A_1 \longrightarrow \{1,\dots,n\}
$$
と置けば、証明の中で触れられている
$$
f : A_1 \to \{1,\dots,n\}
$$
という全単射が存在することになる。
もし $\bigcup_{i=1}^k A_i$ という集合と $A_{k+1}$ という集合は互いに素でない場合、
ある $j \leq k$ に対して $x \in A_j$ かつ $x \in A_{k+1}$ となる。
しかしこれは $j \neq k+1$ なので、仮定（$A_i$ が相互に素）に矛盾する。
ゆえに共通部分は空である。
-◇ 単射性の証明
$h(x)=h(y)$ を仮定して場合分けする。
- $x,y\in A_1$ のとき：$h(x)=f(x),\ h(y)=f(y)$ だから、仮定より $f(x)=f(y)$ である。
ここで、$f$ は全単射より(特に単射だから) $x=y$ である。
$ $ - $x,y\in A_2$ のとき：
$h(x)=n+g(x),\ h(y)=n+g(y)$ だから $g(x)=g(y)$ である。
$g$ は全単射より(特に単射だから) $x=y$ である。
$ $ - $x\in A_1,\ y\in A_2$ のとき：
$h(x)=f(x)\le n$ に対し、$h(y)=n+g(y)\ge n+1$ なので $h(x)\ne h(y)$ で仮定と矛盾
(故、そのようなケースは存在しない)。
$ $ - $x\in A_2,\ y\in A_1$ のとき：
$h(x)=n+g(x)\ge n+1$ に対し、$h(y)=f(y)\le n$ なので $h(x)\ne h(y)$ で仮定と矛盾
(故、そのようなケースは存在しない)。
$ $
以上より $h$ は単射である。
-◇ 全射性の証明
終域の任意の元 $z \in \{1, 2, \dots, n+m\}$ をとり、
その値の範囲によって場合分けをして、対応する元の存在を示す。
$ $
- $1 \le z \le n$ の場合
仮定より $f: A_1 \to \{1, \dots, n\}$ は全単射(特に全射)である。
全射の定義より、$f(x) = z$ を満たす $x \in A_1$ が存在する。
この $x$ に対して $h$ の値を考えると、$x \in A_1$ なので定義より
$$ h(x) = f(x) = z $$
となる。したがって、この範囲の $z$ に対して $h(x)=z$ となる $x$ が存在する。
$ $ - $n+1 \le z \le n+m$ の場合
このとき、$z' = z - n$ とおくと、$1 \le z' \le m$ である。
仮定より $g: A_2 \to \{1, \dots, m\}$ は全単射(特に全射)である。
全射の定義より、この $z'$ に対して、$g(y) = z'$ を満たす $y \in A_2$ が存在する。
この $y$ に対して $h$ の値を考えると、$y \in A_2$ なので定義より
$$ h(y) = n + g(y) $$
ここで $g(y) = z' = z - n$ を代入すると、
$$ h(y) = n + (z - n) = z $$
となる。したがって、この範囲の $z$ に対しても $h(y)=z$ となる $y$ が存在する。
$ $
-したがって、1, 2 のいずれの場合も、任意の $z \in \{1, \dots, n+m\}$ に対して、
$h(x) = z$ となる $x \in A_1 \cup A_2$ が見つかった。ゆえに、$h$ は全射である。
$ $
-結論
以上から $h$ は全単射である事が示された。
互いに素な事象$A,B$について、 $A$ が $m$ 通り、事象 $B$ が $n$ 通りの方法で起こるとする。
このとき、「$A$ または $B$ のいずれかが起こる」方法の総数は、
$$
m + n
$$
通りである。
この命題は「有限加法性（加法原理）」の特別な場合（$k=2$)のケース）にすぎない。
既に示した通り、相互に素な有限集合族 ($(A_i)_{i=1}^k$) に対して
$$
\left|\bigcup_{i=1}^k A_i\right|=\sum_{i=1}^k |A_i|
$$
が成り立つ、というもので、この命題はこれの $k=2$（かつ$|A|=m,\ |B|=n$）に相当し、
$$
|A\cup B|=|A|+|B|=m+n
$$
となる、という位置づけである。
互いに素な事象 $A,B$ があり、$A$ は互いに素な事象 $A_1,\dots,A_m$ の和、
$B$ もまた互いに素な事象 $B_1,\dots,B_n$ の和で、
$$
A=\bigsqcup_{i=1}^m A_i,\quad B=\bigsqcup_{j=1}^n B_j,\quad |A_i|=|B_j|=1,\quad A\cap B=\varnothing
$$
とする。すると
$$
\begin{aligned}
|A\cup B|
&=\Bigl|\bigl(\bigsqcup_{i=1}^m A_i\bigr)\cup \bigl(\bigsqcup_{j=1}^n B_j\bigr)\Bigr| \quad \because\ \text{仮定より }A=\bigsqcup_{i=1}^m A_i,\ B=\bigsqcup_{j=1}^n B_j \\
&=\sum_{i=1}^m |A_i|+\sum_{j=1}^n |B_j| \quad \because\ A=\bigsqcup_{i=1}^m A_i,\ B=\bigsqcup_{j=1}^n B_j,\ A\cap B=\varnothing\ \text{なので互いに素な族の有限加法性より}\\
&=\sum_{i=1}^m 1+\sum_{j=1}^n 1 \quad \because\ |A_i|=|B_j|=1\\
&=m+n \quad \because\ \sum_{i=1}^m 1=m,\ \sum_{j=1}^n 1=n
\end{aligned}
$$
より、方法の総数は $m+n$ 通りである。
$$ \Box$$
有限集合 $ A $ と $ B $ に対して、
$$
A \times B := \{ (a, b) \mid a \in A,\ b \in B \}
$$
を $ A $ と $ B $ の直積と定義する。このとき、直積の元の個数は
$$
|A \times B| = |A| \cdot |B|
$$
となる。
有限集合 $ A $ と $ B $ に対して、各集合の要素数を、いま
$$
|A|=n
$$
$$
|B|=m
$$
とする。集合$A$の各元 $a \in A$ に対して、
$$
B_a = \{(a, b) \mid b \in B\}
$$
と定義する。この集合は、$a$が固定されているから、固定された$a$に対して各$b$のタプルからなる集合である。
例えば、$a=1$のとき$B=\{1,2,3\}$ならば
$$
B_1=\{(1,1),(1,2),(1,3)\}
$$
といった感じである。
このとき、定義から
$$
A \times B = \bigcup_{a \in A} B_a\cdots①
$$
が言える。
例えば$A=\{1,2,3\}$と$B=\{1,2,3\}$からなる集合であるとき、
$$
\bigcup_{a \in A} B_a=\{(1,1),(1,2),(1,3)\}\cup \{(2,1),(2,2),(2,3)\}\cup \{(3,1),(3,2),(3,3)\}
$$
となり、これは確かに直積
$$
A \times B=\{(a,b)|\ a\in A,b \in B\}
$$
と一致する。
また、この和は $a \neq a'$ のとき、$B_a$ の元は $(a, b)$、$B_{a'}$ の元は $(a', b')$ の形をしており、
第$1$成分が異なるため決して一致しない。ゆえに $B_a \cap B_{a'} = \varnothing$ である(=互いに素)。
$ $
ここで、一般に、有限集合 $ A_1, A_2, \dots, A_k $ が相互に素、すなわち $ A_i \cap A_j = \varnothing $ （$ i \neq j $）であるとき、
$$
\left| \bigcup_{i=1}^k A_i \right| = \sum_{i=1}^k |A_i|\cdots②
$$
が成り立つ(既に上で示した)。
ここで、任意の $a \in A$ に対して、$B_a$ の元は
$$
B_a = \{(a, b) \mid b \in B\}
$$
であったので、$B$ の各 $b$ に対して一意な組 $(a, b)$ が対応する。
$ $
さらに、$a$ は固定であるから、各$B_a$は$B$の要素数に一致する。したがって、
$$
|B_a| = |B| = m\cdots③
$$
である。
①より、$A \times B$ は $A$ の各元 $a$ に対応する $B_a$ の和集合（かつ各 $B_a$ は互いに素）である事を踏まえ、
$$
\begin{align}
|A \times B| &= \left|\bigcup_{a \in A} B_a \right|\ \because\ ①\\
&= \sum_{a \in A} |B_a|\ \because\ ②\\
&= \sum_{a \in A} m\ \because\ ③\\
&= |A| \times m \\
&= n \times m
\end{align}
$$
有限集合 $A$ と $B$ に対して
$$
|A|=n
$$
$$
|B|=m
$$
であるから、
$$
|A \times B| = |A| \cdot |B|
$$
が成り立つことが示された。
$$ \Box$$
すなわち、ある事象$A$が$m$通りの方法で起こり、その後に事象$B$が$n$通りの方法で起こる場合、
$A$と$B$が同時に行う場合の総数は
$$
m \times n
$$
通りである。
「異なる $n$ 個のもの」を集めた集合を
$$
X = \{x_1, x_2, \dots, x_n\}
$$
とする。「重複を許して順番を考慮して $r$ 個取る」とは、長さ $r$ の列
$$
(x_1,\dots,x_r)
$$
であって、各成分 $x_i$ が $X$ の元（すなわち $x_i \in X$）であるようなもの全体を数えることである。
このような長さ $r$ の列全体の集合を
$$
X^r := \underbrace{X \times X \times \cdots \times X}_{r\ \text{回}}
$$
と書く。このとき、$X^r$ の元の個数は
$$
|X^r| = n^r
$$
である。
$|X^r|=n^r$ を $r$ についての帰納法で示す。
- $r=0$ の場合
定義より
$$ X^0 := \{\text{長さ0の列}\} $$
とする（これは「長さ $0$ の列という“$1$つの値”を元に持つ集合」）。
長さ$0$の列は $1$ 通りしかないので
$$ |X^0| = 1 $$
一方、指数の定義より
$$ n^0 = 1 $$
したがって
$$ |X^0| = n^0 $$
が成り立つ。
$ $ - 帰納法の仮定
ある $r\in\mathbb N_0$ に対して
$$ |X^r| = n^r $$
が成り立つと仮定する。
$ $ - $r+1$ の場合
$X^{r+1}$ は定義より
$$ X^{r+1} = X^r \times X $$
である（長さ $r+1$ の列は「長さ $r$ の列」と「最後の$1$要素」の組とみなせる）。
(上で示した)直積の要素数の性質 $|A\times B|=|A|\cdot|B|$ を $A=X^r,\ B=X$ に適用すると
$$ |X^{r+1}| = |X^r\times X| = |X^r|\cdot|X| $$
ここで帰納法の仮定 $|X^r|=n^r$ と $|X|=n$ を代入すれば
$$ |X^{r+1}| = n^r\cdot n = n^{r+1} $$
したがって、$r+1$ に対しても
$$ |X^{r+1}| = n^{r+1} $$
が成り立つ。
$ $
-以上より、 $r=0$ で成り立ち、「$r$ で成り立つなら $r+1$ でも成り立つ」ことを示したので、
数学的帰納法により、任意の $r\in\mathbb N_0$ に対して
$$
|X^r| = n^r
$$
が成り立つ。
$$ \Box$$
したがって、異なる$n$個のものから重複を許して$r$個取ってできる順列の総数は
$$
n^r
$$
である。
$n^r$を$_n\Pi_r$と書くこともある。
この記事を高評価した人
この記事に送られたバッジ
投稿者
