全射の個数の問題について

${}$

この記事では, 以下の問題の解答を書こうと思います. 正整数の集合を$\Z_{>0}$と書きます.
${}$

(解答)

$i\in Y$に対し$f(x)=i$となる$x\in X$の個数を$a_i$とおきます. すると$\ds\sum_{i=1}^m a_i=n$であり, 逆にこれを満たす正整数の組$(a_1,\ldots,a_m)$に対し, 全射$f:X\to Y$がいくつか存在します.

これは具体的には, $1$から$n$の整数を$a_1$個, $a_2$個, ..., $a_m$個, のグループに分ける場合の数を考えれば, このような全射$f$は$\ds\frac{n!}{a_1!a_2!\cdots a_m!}$通りあり得ます.

従って求める個数$S$は
$$ S=\sum_{\begin{array}{c}a_1+\cdots +a_m=n\\[-5pt]a_i\in\Z_{>0}\end{array}}\frac{n!}{a_1!a_2!\cdots a_m!}$$
と書けます.

ここで関数$g(x)$の(Maclaurin展開の)$x^k$の係数を$[x^k]g(x)$と書くことにすると, $\ds[x^k]e^x=\frac1{k!}$が成り立つことを利用します. 即ち, $x_1,x_2,\ldots,x_m$の式
$$\ds\prod_{i=1}^m(e^{x_i}-1)$$
を展開することを考えたとき, その$n$次の項全ての係数の和は, 和が$n$である正整数の組$(a_1,\ldots,a_m)$全てに対して$\ds\frac{1}{a_1!\cdots a_m!}$を足し合わせたものに等しいのです！($e^x-1$に$0$次の項はないことが効いてきます)

さらにこの値は, $x_1,\ldots,x_m$を全て同一視して$x$とした式 $(e^x-1)^m$ の$x^n$の係数に等しいので,

$$\beq S&=&n!\cdot\sum_{\begin{array}{c}a_1+\cdots +a_m=n\\[-5pt]a_i\in\Z_{>0}\end{array}}\frac{1}{a_1!\cdots a_m!}\\[5pt] &=&n!\cdot\sum_{\begin{array}{c}a_1+\cdots +a_m=n\\[-5pt]a_i\in\Z_{>0}\end{array}}[x_1^{a_1}\cdots x_m^{a_m}]\prod_{i=1}^m(e^{x_i}-1)\\[5pt] &=&n!\cdot [x^n](e^x-1)^m\\[5pt] &=&n!\sum_{k=0}^m(-1)^{m-k}\binom{m}{k}[x^n]e^{kx}\\[5pt] &=&\sum_{k=1}^m(-1)^{m-k}\binom{m}{k}k^n \eeq$$

よって示すことができました. □

${}$

実はこれは, 私の過去の記事の主張を用いるととても簡潔に解くことができます.
${}$

(解答2)

求める全射の個数を$S_m$とおきます($n$は固定する). 全射と限らない$X$から$Y$への写像は$m^n$通りあることに注意します.

$m^n$通りの写像$f$を$\#\mathrm{Im}f$によって場合分けすると, $\#\mathrm{Im}f=k$なる$\mathrm{Im}f\subset Y$は$\binom{m}{k}$通りとれ, そのそれぞれに対し$f:X\to\mathrm{Im}f$は全射だから$S_k$通りとれます. 従って
$$ \sum_{k=1}^m\binom{m}{k}S_k=m^n$$
が, 各$m$に対して成立します.

これに この記事 の主張で$n$を$m$と置き換えてから, $a_k=(-1)^kS_k$, $b_m=n^m$としたものを適用すれば,
$$ (-1)^mS_m=\sum_{k=1}^m(-1)^k\binom{m}{k}k^n$$

よって示すことができました. □
${}$

読んでくださった方, ありがとうございました.

${}$

${}$