集合と位相の問題

ステップ 1：同値関係を分割に言いかえる。

$A$ 上の同値関係 $R$ を 1 つ決めると、その同値類全体は $A$ の分割になります。どの同値類も空でなく、互いに交わらず、すべてを合わせると $A$ になるからです。逆に、$A$ の分割を 1 つ決めて「同じブロックに属するとき $xRy$」と定めると、同値関係が 1 つ決まります。この 2 つの対応は互いに逆なので、同値関係と分割は $1$ 対 $1$ に対応します。同値類が $3$ 個の同値関係は、$A$ をちょうど $3$ 個のブロックに分ける分割に対応します。したがって、求める個数は第 $2$ 種スターリング数 $S(5,3)$ です。

ステップ 2：$S(5,3)$ を漸化式で計算する。

漸化式 $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ と、$S(n,1)=S(n,n)=1$ を使って表を作ります。

• $S(3,2)=S(2,1)+2S(2,2)=1+2=3$
• $S(4,2)=S(3,1)+2S(3,2)=1+6=7$
• $S(4,3)=S(3,2)+3S(3,3)=3+3=6$
• $S(5,3)=S(4,2)+3S(4,3)=7+18=25$

確かめ（ブロックの大きさで直接数える）： $5$ 元を $3$ ブロックに分けるとき、ブロックの大きさの組は $3+1+1$ か $2+2+1$ のどちらかです。

• $3+1+1$ 型：$3$ 元のブロックの選び方で決まるので、$\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 通り
• $2+2+1$ 型：$1$ 元のブロックの選び方が $5$ 通りあります。残りの $4$ 元を $2$ 元ずつ $2$ 組に分ける方法は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)÷2=3$ 通りです。よって $5\times 3=15$ 通り

合計は $10+15=25$ となり、漸化式の結果と一致します。

よって、求める個数は $25$ です。

$A$ 上の同値関係は $A$ の分割と一対一に対応する。したがって、同値類がちょうど 3 個である同値関係の個数は、5 元集合を空でない 3 個の部分集合に分割する方法の数、すなわち第 2 種スターリング数 $S(5,3)$ に等しい。

分割のタイプは次の 2 通りである。
- 型 $3+1+1$：3 元部分集合の選び方は $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 通り。残り 2 元は単元集合になるので 10 通り。
- 型 $2+2+1$：単元集合になる元の選び方が 5 通り。残り 4 元を 2 組に分ける方法は $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{4}{2}\right)=3$ 通り。よって $5\times 3=15$ 通り。

合計は $10+15=25$。

検算：漸化式 $S(n,k)=kS(n-1,k)+S(n-1,k-1)$ より、$S(4,3)=6$、$S(4,2)=7$ なので $S(5,3)=3\cdot 6+7=25$。これは上の結果と一致する。