集合と位相の問題

方針：同値関係を分割に言いかえる

集合 $A$ 上の同値関係 $R$ を 1 つ決めると、$A$ は同値類に分かれます。同値類は空でなく、互いに交わらず、全部の和集合は $A$ になるので、同値類の全体は $A$ の分割になります。

逆に、$A$ の分割を 1 つ決めて「$x$ と $y$ が同じブロックに属するとき $xRy$」と定めると、同値関係が 1 つ得られます。この 2 つの対応は互いに逆なので、
$$\{A\text{ 上の同値関係}\}⟷\{A\text{ の分割}\}$$
は 1 対 1 に対応します。したがって、求める個数は $5$ 元集合の分割の個数、つまりベル数
$$B_5=\sum _{k=1}^{5}S(5,k)$$
です。ここで $S(n,k)$ は $n$ 元集合を $k$ 個のブロックに分ける分割の個数（第 2 種スターリング数）です。

スターリング数の表を作る

漸化式 $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ と、$S(n,1)=S(n,n)=1$ を使います。

• $n=2$：$S(2,1)=1,S(2,2)=1$
• $n=3$：$S(3,2)=S(2,1)+2S(2,2)=1+2=3$。よって $1,3,1$
• $n=4$：
• $S(4,2)=S(3,1)+2S(3,2)=1+6=7$
• $S(4,3)=S(3,2)+3S(3,3)=3+3=6$
• よって $1,7,6,1$
• $n=5$：
• $S(5,2)=S(4,1)+2S(4,2)=1+14=15$
• $S(5,3)=S(4,2)+3S(4,3)=7+18=25$
• $S(5,4)=S(4,3)+4S(4,4)=6+4=10$
• よって $1,15,25,10,1$

合計する

$$B_5=1+15+25+10+1=52$$

よって、$A$ 上の同値関係は $52$ 個です。

A 上の同値関係は A の分割と一対一に対応するので、個数は 5 個の元の集合の分割の数、すなわちベル数 $B_5$ に等しい。

スターリング数 $S(5,k)$ を使うと、$S(5,1)=1$、$S(5,2)=15$、$S(5,3)=25$、$S(5,4)=10$、$S(5,5)=1$ なので、合計は $1+15+25+10+1=52$。

検算として、ベル数の漸化式 $B_{n+1}={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)B_k$ を使う。$B_0=1$、$B_1=1$、$B_2=2$、$B_3=5$、$B_4=15$ より、
$B_5=1+4\cdot 1+6\cdot 2+4\cdot 5+1\cdot 15=1+4+12+20+15=52$。

よって答えは 52。