集合と位相の問題

用いてよい事実より、有限集合 $S$ 上の同値関係の個数は $S$ の分割の個数に等しい。そこで $S$ の分割の個数を $p(S)$ と書くと $E(m)=p([m])$ である。$n$ を 0 以上の整数として固定し、$[n+1]$ の分割を「$n+1$ を含むブロック」で分類して数える。

段階 1: 全単射の構成.

集合 $\mathcal{A}$ を $[n+1]$ の分割全体、集合 $\mathcal{B}$ を組 $(T,\mathcal{Q})$（$T\subset [n]$、$\mathcal{Q}$ は $T$ の分割）全体とする。

写像 $\Phi :\mathcal{A}\to \mathcal{B}$ を次で定める。$\mathcal{P}\in \mathcal{A}$ に対し、$\mathcal{P}$ の元の和集合は $[n+1]$ なので $n+1$ を含む元があり、相異なる元は交わらないのでそれはただ 1 つである。これを $B$ とし、
$$T=[n+1]\setminus B,\mathcal{Q}=\mathcal{P}\setminus \{B\},\Phi (\mathcal{P})=(T,\mathcal{Q})$$
とおく。$n+1\in B$ なので $T\subset [n]$ である。また $\mathcal{Q}$ の元は $\mathcal{P}$ の元なので空でなく、互いに交わらない。$\mathcal{Q}$ の各元は $B$ と交わらないので $T$ に含まれ、逆に $T$ の点は $\mathcal{P}$ のある元に属し、それは $B$ ではないので $\mathcal{Q}$ の元である。よって $\mathcal{Q}$ の元の和集合は $T$ であり、$\mathcal{Q}$ は $T$ の分割である。したがって $\Phi (\mathcal{P})\in \mathcal{B}$。

写像 $\Psi :\mathcal{B}\to \mathcal{A}$ を $\Psi (T,\mathcal{Q})=\mathcal{Q}\cup \{[n+1]\setminus T\}$ で定める。$T\subset [n]$ より $n+1\in [n+1]\setminus T$ なのでこの集合は空でない。$\mathcal{Q}$ の元は $T$ に含まれるので $[n+1]\setminus T$ と交わらず、$\mathcal{Q}$ の元どうしも交わらない。和集合は $T\cup ([n+1]\setminus T)=[n+1]$ である。よって $\Psi (T,\mathcal{Q})$ は $[n+1]$ の分割である。

$\Phi$ と $\Psi$ が互いに逆写像であることを確かめる。
- $(T,\mathcal{Q})\in \mathcal{B}$ に対し、$\Psi (T,\mathcal{Q})$ で $n+1$ を含むブロックは $[n+1]\setminus T$ であるから（$\mathcal{Q}$ の元は $T\subset [n]$ に含まれ $n+1$ を含まない）、$\Phi (\Psi (T,\mathcal{Q}))=([n+1]\setminus ([n+1]\setminus T),\mathcal{Q})=(T,\mathcal{Q})$。なお $[n+1]\setminus T\notin \mathcal{Q}$ なので、これを取り除くと $\mathcal{Q}$ に戻る。
- $\mathcal{P}\in \mathcal{A}$ に対し、$\Phi (\mathcal{P})=(T,\mathcal{P}\setminus \{B\})$ で $[n+1]\setminus T=B$ だから、$\Psi (\Phi (\mathcal{P}))=(\mathcal{P}\setminus \{B\})\cup \{B\}=\mathcal{P}$。

よって $\Phi$ は全単射であり、$|\mathcal{A}|=|\mathcal{B}|$。

段階 2: $\mathcal{B}$ の元の個数.

$\mathcal{B}$ の元を $T$ ごとに数えると $|\mathcal{B}|={\sum }_{T\subset [n]}p(T)$ である。$|T|=j$ のとき、全単射 $\sigma :T\to [j]$ をとると、$T$ の分割 $\mathcal{Q}$ に $\{\sigma (Q):Q\in \mathcal{Q}\}$ を対応させる写像は $[j]$ の分割全体への全単射である（${\sigma }^{-1}$ による像をとる写像が逆写像になり、$\sigma$ が全単射なので空でないこと・交わらないこと・和集合が全体になることが保たれる）。よって $p(T)=p([j])=E(j)$ であり、これは $|T|$ だけで決まる。$[n]$ の $j$ 元部分集合は $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ 個あり、$j$ は $0$ から $n$ までを動くので
$$|\mathcal{B}|=\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)E(j).$$
（$j=0$ の項は $T=\varnothing$ で、$\varnothing$ の分割は空集合族 1 つなので $E(0)=1$ と合っている。）

結論. $E(n+1)=p([n+1])=|\mathcal{A}|=|\mathcal{B}|={\sum }_{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)E(j)$。$n$ は任意の 0 以上の整数だったので、示すべき等式が成り立つ。$■$