集合と位相の問題

$A$ 上の同値関係と $A$ の分割（同値類全体）は $1$ 対 $1$ に対応するので、$A$ の分割で条件を満たすものを数える。

(1) 条件 $(1)$ を満たす分割の総数

どのブロック（同値類）も $2$ 個以上の元をもつ $7$ 元集合の分割の、ブロックの大きさの組は
$$\{7\},\{5,2\},\{4,3\},\{3,2,2\}$$
の $4$ 通りである（$2+2+2=6<7$ なので $4$ ブロック以上はありえず、$7=6+1=3+3+1$ などは大きさ $1$ のブロックを含む）。それぞれの個数は
- $\{7\}$: $1$
- $\{5,2\}$: 大きさ $2$ のブロックを選んで $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$
- $\{4,3\}$: 大きさ $3$ のブロックを選んで $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$
- $\{3,2,2\}$: 大きさ $3$ のブロックを選んで $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$、残り $4$ 個を $2$ 個ずつの組に分ける方法が $3$ 通りで、$35\times 3=105$

よって総数は $1+21+35+105=162$ である。

(2) 条件 $(1)$ を満たし、$1$ と $2$ が同じブロックに入る分割の数

大きさの組ごとに、$1,2$ が入るブロックで場合を分ける。
- $\{7\}$: $1$
- $\{5,2\}$: $1,2$ が大きさ $5$ のブロックに入るとき、残り $5$ 個から $3$ 個を選んで $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$。大きさ $2$ のブロック $\{1,2\}$ になるとき $1$。合計 $11$
- $\{4,3\}$: 大きさ $4$ のブロックに入るとき $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$、大きさ $3$ のブロックに入るとき $\left(\genfrac{}{}{0ex}{}{5}{1}\right)=5$。合計 $15$
- $\{3,2,2\}$: 大きさ $3$ のブロックに入るとき、残りの $1$ 個を $\left(\genfrac{}{}{0ex}{}{5}{1}\right)=5$ 通りに選び、残り $4$ 個を $2$ 個ずつに分けて $3$ 通りなので $15$。大きさ $2$ のブロック $\{1,2\}$ になるとき、残り $5$ 個を大きさ $3$ と $2$ に分けて $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$。合計 $25$

よって $1+11+15+25=52$ である。

（検算: $1$ と $2$ を $1$ つの元 $\ast$ にまとめると、$\ast$ だけは $1$ 元のブロックになってよい $6$ 元集合の分割に対応する。$\ast$ が $1$ 元のブロックでないものは「どのブロックも $2$ 個以上の $6$ 元集合の分割」で $1+\left(\genfrac{}{}{0ex}{}{6}{2}\right)+\frac{1}{2}\left(\genfrac{}{}{0ex}{}{6}{3}\right)+15=1+15+10+15=41$ 個、$\ast$ が $1$ 元のブロックのものは残り $5$ 元の同様の分割で $1+\left(\genfrac{}{}{0ex}{}{5}{2}\right)=11$ 個。合計 $52$ で一致する。）

(3) 答え

条件 $(1)$, $(2)$ をともに満たすものは
$$162-52=110$$
個である。

答えは $110$ である。

同値関係は $A$ の分割と 1 対 1 に対応する。条件 (1) は「どのブロックも大きさ 2 以上」。$g(m)$ を $m$ 元集合の、どのブロックも大きさ 2 以上の分割の個数とする。$g(0)=1,g(1)=0,g(2)=1,g(3)=1$。

$m$ 元集合で特定の 1 元を含むブロックの大きさを $k+1(k\ge 1)$ とすると $g(m)={\sum }_{k\ge 1}\left(\genfrac{}{}{0ex}{}{m-1}{k}\right)g(m-1-k)$。これより
$g(4)=3g(1)...$ ではなく順に計算する: $g(4)=\left(\genfrac{}{}{0ex}{}{3}{1}\right)g(2)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)g(1)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)g(0)=3+0+1=4$、
$g(5)=\left(\genfrac{}{}{0ex}{}{4}{1}\right)g(3)+\left(\genfrac{}{}{0ex}{}{4}{2}\right)g(2)+\left(\genfrac{}{}{0ex}{}{4}{3}\right)g(1)+\left(\genfrac{}{}{0ex}{}{4}{4}\right)g(0)=4+6+0+1=11$、
$g(6)=\left(\genfrac{}{}{0ex}{}{5}{1}\right)g(4)+\left(\genfrac{}{}{0ex}{}{5}{2}\right)g(3)+\left(\genfrac{}{}{0ex}{}{5}{3}\right)g(2)+\left(\genfrac{}{}{0ex}{}{5}{4}\right)g(1)+\left(\genfrac{}{}{0ex}{}{5}{5}\right)g(0)=20+10+10+0+1=41$、
$g(7)=\left(\genfrac{}{}{0ex}{}{6}{1}\right)g(5)+\left(\genfrac{}{}{0ex}{}{6}{2}\right)g(4)+\left(\genfrac{}{}{0ex}{}{6}{3}\right)g(3)+\left(\genfrac{}{}{0ex}{}{6}{4}\right)g(2)+\left(\genfrac{}{}{0ex}{}{6}{5}\right)g(1)+\left(\genfrac{}{}{0ex}{}{6}{6}\right)g(0)=66+60+20+15+0+1=162$。

次に、$1$ と $2$ が同値となる (1) を満たす分割の個数を数える。$1,2$ を含むブロックには、残りの $3,\dots ,7$（5 個）から $k$ 個が入り（$k=0,\dots ,5$、大きさは $k+2\ge 2$ で常に条件を満たす）、残る $5-k$ 個は大きさ 2 以上のブロックに分割する。個数は
${\sum }_{k=0}^5\left(\genfrac{}{}{0ex}{}{5}{k}\right)g(5-k)=g(5)+5g(4)+10g(3)+10g(2)+5g(1)+g(0)=11+20+10+10+0+1=52$。

よって求める個数は $162-52=110$。

検算: $1$ と $2$ が別のブロックにある場合を直接数えると、$1$ のブロック $B_1$ と $2$ のブロック $B_2$ を決める。$3,\dots ,7$ のうち $B_1$ に $i$ 個、$B_2$ に $j$ 個入れる（$i,j\ge 1$）と、残り $5-i-j$ 個を大きさ 2 以上のブロックに分割する。${\sum }_{i,j\ge 1}\frac{5!}{i!j!(5-i-j)!}g(5-i-j)$ を計算する: $(i+j=2)$: 組 $(1,1)$ で $20\cdot g(3)=20$; $(i+j=3)$: $(1,2),(2,1)$ で $2\cdot 30\cdot g(2)=60$... ここで $\frac{5!}{1!2!2!}=30$ なので $60$; $(i+j=4)$: $(1,3),(3,1)$ は各 $\frac{5!}{1!3!1!}=20$ で $g(1)=0$、$(2,2)$ は $\frac{5!}{2!2!1!}=30$ で $g(1)=0$; $(i+j=5)$: $(1,4),(4,1)$ は各 $5$、$(2,3),(3,2)$ は各 $10$、合計 $30$ で $g(0)=1$ なので $30$。ここで $i+j=2$ の $(1,1)$ は $\frac{5!}{1!1!3!}=20$、残り 3 個で $g(3)=1$ なので $20$。合計 $20+60+0+30=110$。一致。