集合と位相の問題

写像 $f:A\to B$ 全体の集合を $U$ とします。$|A|=5$、$|B|=4$ なので、重複順列より $|U|=4^5=1024$ です。

$B$ の各元 $y\in \{a,b,c,d\}$ について、
$$A_y=\{f\in U\mid y\notin f(A)\}$$
とおきます。これは「$y$ が値として一度も使われない写像」の集合です。$f$ が全射であることは、どの $y$ についても $f\notin A_y$ であることと同じです。したがって、全射の個数は
$$\left|\overline{A_a}\cap \overline{A_b}\cap \overline{A_c}\cap \overline{A_d}\right|$$
であり、これを一般の包除原理で求めます。

$B$ の元のうち特定の $k$ 個を値に使わない写像は、各元の行き先を残りの $4-k$ 個から選ぶので $(4-k{)}^5$ 個です。$k$ 個の選び方は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りあります。よって
$$\sum _{k=0}^4(-1{)}^k(\genfrac{}{}{0ex}{}{4}{k})(4-k{)}^5$$
が全射の個数です。各項を計算すると、次のとおりです。
- $k=0$：$1\cdot 4^5=1024$
- $k=1$：$4\cdot 3^5=4\cdot 243=972$
- $k=2$：$6\cdot 2^5=6\cdot 32=192$
- $k=3$：$4\cdot 1^5=4$
- $k=4$：$1\cdot 0^5=0$

したがって、全射の個数は
$$1024-972+192-4+0=240$$
です。

（検算）$5$ 個の元を $4$ つの値に割り当てて全射にするには、ちょうど $2$ 個の元が同じ値をとり、残りはすべて異なる値をとる必要があります。同じ値をとる $2$ 個の選び方が $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通り、できた $4$ つのグループに $B$ の $4$ 元を割り当てる方法が $4!=24$ 通りなので、$10\times 24=240$ となり一致します。

答え：$240$

全射の個数は包除原理で求める。$|A|=5$、$|B|=4$ なので、全射の個数は ${\sum }_{k=0}^4(-1{)}^k(\genfrac{}{}{0ex}{}{4}{k})(4-k{)}^5$ である。

各項は次のとおり。
- $k=0$: $4^5=1024$
- $k=1$: $-4\cdot 3^5=-972$
- $k=2$: $+6\cdot 2^5=192$
- $k=3$: $-4\cdot 1^5=-4$
- $k=4$: $0$

合計は $1024-972+192-4=240$。

検算: 5個の元を 4 個の空でない部分集合に分ける方法は、スターリング数 $S(5,4)=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通り（大きさ 2,1,1,1 の分け方）である。これを $B$ の 4 元に対応させる方法が $4!=24$ 通りあるので、$10\cdot 24=240$。一致する。