集合と位相の問題

手順 1：同値関係を分割に置き換える。
$A$ 上の同値関係 $R$ を与えると、その同値類全体は $A$ の分割になります。逆に $A$ の分割を与えると、「同じブロックに属する」という関係は同値関係になり、その同値類はもとのブロックに一致します。この対応は $1$ 対 $1$ です。

したがって、同値類がちょうど $3$ 個の同値関係の個数は、$5$ 元集合を空でない $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$$

確認（ブロックの大きさで数える）：
- 大きさが $3,1,1$ の分割：$3$ 元のブロックの選び方は $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 通りです。
- 大きさが $2,2,1$ の分割：$1$ 元のブロックの選び方が $5$ 通りあります。残りの $4$ 元を $2$ 元ずつ $2$ 組に分ける方法は $\frac{\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)$ に等しい。

分割のブロックの大きさの型は (3,1,1) と (2,2,1) の 2 通りである。

(3,1,1) の型：3 元部分集合を選ぶ方法は $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ 通りで、残り 2 個は単元素集合になる。よって 10 通り。

(2,2,1) の型：単元素になる要素を選ぶ方法が 5 通り。残り 4 個を 2 個ずつの 2 組に分ける方法が $\left(\genfrac{}{}{0ex}{}{4}{2}\right)/2=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$。一致する。