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

2420

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

　整数

n, m

は

1 \leq m \leq n

を満たす. 集合

X = {1, 2, \dots, n}

から集合

Y = {1, 2, \dots, m}

への全射の個数は

\sum_{k = 1}^{m} (- 1)^{m - k} (\binom{m}{k}) k^{n}

に等しいことを示せ.

(解答)

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

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

従って求める個数 $S$ は
$S = \sum_{\begin{matrix} a_{1} + \dots + a_{m} = n \\ a_{i} \in Z_{> 0} \end{matrix}} \frac{n!}{a_{1}! a_{2}! \dots a_{m}!}$
と書けます.

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

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

$\begin{array}{rcl} S & = & n! \cdot \sum_{\begin{array}{c} a_{1} + \dots + a_{m} = n \\ a_{i} \in Z_{> 0} \end{array}} \frac{1}{a_{1}! \dots a_{m}!} \\ = & n! \cdot \sum_{\begin{array}{c} a_{1} + \dots + a_{m} = n \\ a_{i} \in Z_{> 0} \end{array}} [x_{1}^{a_{1}} \dots x_{m}^{a_{m}}] \prod_{i = 1}^{m} (e^{x_{i}} - 1) \\ = & n! \cdot [x^{n}] (e^{x} - 1)^{m} \\ = & n! \sum_{k = 0}^{m} (- 1)^{m - k} (\binom{m}{k}) [x^{n}] e^{k x} \\ = & \sum_{k = 1}^{m} (- 1)^{m - k} (\binom{m}{k}) k^{n} \end{array}$

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

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

(解答2)

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

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

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