集合と位相の問題

全射とは、$B$ のどの元も少なくとも $1$ つの $A$ の元の像になっている写像のことです。そこで、写像全体から「$B$ のある元が像に現れない写像」を包除原理で取り除きます。

ステップ 1：条件を集合で表す

写像 $f:A\to B$ 全体の集合を $U$ とします。$|A|=5$, $|B|=4$ なので $|U|=4^5=1024$ です。$B$ の各元 $y$ に対して
$$E_y=\{f\in U\mid y\notin f(A)\}$$
とおきます。全射とは、どの $E_y$ にも属さない写像のことです。

ステップ 2：$k$ 個の $E_y$ の共通部分の大きさ

$B$ の $k$ 個の元を指定し、それらがどれも像に現れない写像は、残りの $4-k$ 個の元への写像です。その個数は $(4-k{)}^5$ です。$k$ 個の元の選び方は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りあります。

ステップ 3：包除原理を適用する

$$\#\{\text{全射}\}=\sum _{k=0}^4(-1{)}^k(\genfrac{}{}{0ex}{}{4}{k})(4-k{)}^5$$

各項を計算します。
- $k=0$: $\left(\genfrac{}{}{0ex}{}{4}{0}\right)\cdot 4^5=1\cdot 1024=1024$
- $k=1$: $\left(\genfrac{}{}{0ex}{}{4}{1}\right)\cdot 3^5=4\cdot 243=972$
- $k=2$: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 2^5=6\cdot 32=192$
- $k=3$: $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 1^5=4\cdot 1=4$
- $k=4$: $\left(\genfrac{}{}{0ex}{}{4}{4}\right)\cdot 0^5=0$

これらに符号をつけて足すと
$$1024-972+192-4+0=240$$

検算

$5$ 個の元を $4$ つの値に全射で送るには、ちょうど $2$ 個の元が同じ値をとり、残り $3$ 個はそれぞれ別の値をとる必要があります。
- 同じ値をとる $2$ 個の選び方は $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通りです。
- できた $4$ つのまとまりを $B$ の $4$ 元に $1$ 対 $1$ に割り当てる方法は $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$。

検算として、第2種スターリング数を使う。$4!S(5,4)=24\cdot 10=240$ で一致する。

さらに直接数える。5個の元を4つの像に割り当てるには、ちょうど1つの像に2個が対応し、残りの3つの像に1個ずつ対応する形しかない。2個が対応する像の選び方は4通り、その2個の元の選び方は $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通り、残り3個の元を残り3つの像に割り当てる方法は $3!=6$ 通りである。よって $4\cdot 10\cdot 6=240$ で、これも一致する。