集合と位相の問題

同値関係 $R$ と、その同値類全体からなる $A$ の分割は一対一に対応する。そこで、条件を満たす分割を数える。

1. 条件の言い換え

$f$ は $f\circ f={\mathrm{id}}_A$ を満たす全単射である。条件を満たす $R$ の同値類 $C$ を 1 つとる。$x,y\in C$ なら $f(x)Rf(y)$ なので、$f(C)$ はある 1 つの同値類 $D$ に含まれる。同様に $f(D)$ もある 1 つの同値類に含まれる。$C=f(f(C))\subset f(D)$ であり、$f(D)$ はただ 1 つの同値類に含まれ、しかも $C$ と共通部分をもつので、その同値類は $C$ である。よって $C=f(f(C))\subset f(D)\subset C$ となり、$f(D)=C$ である。両辺に $f$ を施すと $D=f(C)$ が得られる。したがって $f$ は同値類を同値類にうつし、同値類の並べ替えを引き起こす。$f\circ f={\mathrm{id}}_A$ なので、各同値類 $C$ は次のどちらかである。

• (ア) $f(C)=C$（$f$ で動かない同値類）
• (イ) $f(C)\ne C$ であり、$C$ と $f(C)$ が互いに入れかわる 2 つの同値類の組をなす

逆に、分割が「どの同値類 $C$ についても $f(C)$ が同値類である」という性質をもてば、条件は満たされる。

2. 同値類の形

$A$ を $f$ で入れかわる組
$$P_1=\{1,6\},P_2=\{2,5\},P_3=\{3,4\}$$
に分ける。

• (ア)の同値類 $C$ は、$x\in C$ なら $f(x)\in C$ なので、いくつかの $P_i$ の和集合である。
• (イ)の組 $\{C,f(C)\}$ では、同値類どうしは交わらないので $C\cap f(C)=\varnothing$ である。よって $C$ は各 $P_i$ から高々 1 個しか元を含まない。$C\cup f(C)$ は、$C$ が元を含む $P_i$ たちの和集合になる。

そこで、$f$ で入れかわる同値類の組（または 1 つの不動な同値類）ごとに $P_1,P_2,P_3$ をまとめると、$\{P_1,P_2,P_3\}$ の分割が 1 つ決まる。

3. 重みの計算

$t$ 個の $P_i$ からなるグループ $T$ について、その上の同値類の作り方を数える。

• (ア)として 1 つの同値類 ${\bigcup }_{P_i\in T}{P}_i$ にする：$1$ 通り
• (イ)として $C,f(C)$ に分ける：$C$ は $T$ の各 $P_i$ からちょうど 1 個ずつ元を選んで作るので $2^t$ 通りある。$C$ と $f(C)$ を入れかえても同じ組なので、$2^t/2=2^{t-1}$ 通り

したがって重みは $1+2^{t-1}$ であり、$t=1,2,3$ に対してそれぞれ $2,3,5$ となる。

4. 合計

$\{P_1,P_2,P_3\}$ の分割の型ごとに数える。

• 1 グループ（大きさ 3）：$1$ 通りの分け方 $\times 5=5$
• 大きさ 2 と 1：$3$ 通りの分け方 $\times 3\times 2=18$
• 大きさ 1 が 3 つ：$1$ 通りの分け方 $\times 2^3=8$

よって求める個数は
$$5+18+8=31.$$

（確認として、$A=\{1,2,3,4\}$, $f(x)=5-x$ で同じ数え方をすると $3+2^2=7$ 通りになる。これは直接列挙した $\{1234\},\{14|23\},\{14|2|3\},\{1|4|23\},\{1|2|3|4\},\{12|34\},\{13|24\}$ の $7$ 通りと一致する。）

$f$ は $f\circ f=\mathrm{id}$ をみたす全単射なので、条件 ($xRy\Rightarrow f(x)Rf(y)$) は $f$ が $R$ を保つことと同値である。実際、$f(x)Rf(y)$ に条件をもう一度使うと $xRy$ が得られる。したがって、$A$ の分割（同値関係と対応）のうち $f$ で不変なものの個数を数えればよい。

$f$ は組 $\{1,6\},\{2,5\},\{3,4\}$ を入れ替える。分割の各ブロック $B$ は次のいずれかになる。
(i) $f(B)=B$ のとき、$B$ は組の和集合である。
(ii) $f(B)\ne B$ のとき、$B$ と $f(B)$ は互いに素で、対 $\{B,f(B)\}$ として現れる。このとき $B$ は各組から高々 1 元しか含まない。

3 つの組のうち、(i) 型のブロックに含まれるものの集合を $S$、(ii) 型に含まれるものの集合を $T$ とする。
- $S$ の分割の数は Bell 数 $B(|S|)$ である。
- $T$ を組のグループ $U$ に分ける。各グループで、$B$ は各組からどちらの元をとるかで $2^{|U|}$ 通りあり、$B$ と $f(B)$ が同じ対を与えるので対としては $2^{|U|-1}$ 通りである。
- $T$ の大きさ $t$ に対する重み $w(t)$ は、$w(0)=1$, $w(1)=1$, $w(2)=1+2=3$, $w(3)=1+3\cdot 2+4=11$ となる。

合計は ${\sum }_s\left(\genfrac{}{}{0ex}{}{3}{s}\right)B(s)w(3-s)$ である。
- $s=0$: $11$
- $s=1$: $3\cdot 1\cdot 3=9$
- $s=2$: $3\cdot 2\cdot 1=6$
- $s=3$: $5$

よって $11+9+6+5=31$。

検算として、組が 2 つの場合に同じ方法で $3+2+2=7$ となる。これは直接数えた結果と合う。