集合と位相の問題

$k$ 元集合から $3$ 元集合への全射の個数を $s(k)$ とする。包除原理により
$$s(k)=3^k-\left(\genfrac{}{}{0ex}{}{3}{1}\right)2^k+\left(\genfrac{}{}{0ex}{}{3}{2}\right)1^k=3^k-3\cdot 2^k+3.$$
よって $s(6)=729-192+3=540$、$s(5)=243-96+3=150$、$s(4)=81-48+3=36$。

全射 $f:A\to B$ 全体を $U$、そのうち $f(1)=f(2)$ を満たすものを $P$、$f(3)=f(4)$ を満たすものを $Q$ とする。求める個数は $|U|-|P\cup Q|=|U|-|P|-|Q|+|P\cap Q|$ である。

• $|U|=s(6)=540$。
• $P$ の元は、$1$ と $2$ を同じ元に送るので、$1,2$ をまとめた $1$ つの元と $3,4,5,6$ からなる $5$ 元集合からの全射と $1$ 対 $1$ に対応する。よって $|P|=s(5)=150$。同様に $|Q|=150$。
• $P\cap Q$ の元は、$\{1,2\},\{3,4\},\{5\},\{6\}$ をそれぞれ $1$ つの元とみた $4$ 元集合からの全射と対応するので $|P\cap Q|=s(4)=36$。

したがって
$$540-150-150+36=276.$$

値域を含む部分集合 $S\subseteq B$（$|S|=k$）への写像で条件を満たすものの個数を $N(k)$ とする。$(f(1),f(2))$ は異なる値なので $k(k-1)$ 通り、$(f(3),f(4))$ も $k(k-1)$ 通り、$f(5),f(6)$ は各 $k$ 通りで、$N(k)=k^2(k-1{)}^2\cdot k^2=k^4(k-1{)}^2$。$N(3)=81\cdot 4=324$、$N(2)=16\cdot 1=16$、$N(1)=0$。
包除原理により、全射の個数は $N(3)-\left(\genfrac{}{}{0ex}{}{3}{2}\right)N(2)+\left(\genfrac{}{}{0ex}{}{3}{1}\right)N(1)=324-48+0=276$。
検算: 余事象で数えると、条件を満たす写像全体は $324$、そのうち像が丁度 2 点のものは $3\cdot (16-0)=48$（像がちょうど 2 点の集合ごとに $N(2)-2N(1)=16$）、像が 1 点のものは 0。よって全射は $324-48=276$ ✓。