数学A / 場合の数

符号つき二項和(全射の数え上げ)

実戦編数え上げ包除原理二項係数全射単元横断

問題

$n$ を自然数とする。 $k = 0 \sum n (- 1)^{k} (k n) k^{n}$ を求めよ。

ヒントを見る

$n$ 個から $n$ 個への全射は全単射だから $n!$ 通り。これを「 $k$ 個の要素が値域から抜ける」包除で数えると $\sum (- 1)^{k} (k n) (n - k)^{n}$ 。 $k$ を $n - k$ に置き換えると?

解答・解説

方針

写像 ${1, \dots, n} \to {1, \dots, n}$ の全射の数を、包除原理で $\sum (- 1)^{k} (k n) (n - k)^{n}$ と表す。全射=全単射なので $n!$ 。置換で目的の和に直す。

解答

⓪ 発想 — どう考え始めるか。 交互符号 $\times$ 二項係数 $\times$ べき — この組合せは包除原理の指紋だ。何かの数え上げの式ではないか、と疑う。

$n$ 人から $n$ 人への写像で「全員が像に現れる」(全射)を包除で数えると

$\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{n}$ — 使われない人を $k$ 人選んで除外する形。全射=全単射で答えは $n!$ だ。

あとは $k \to n - k$ の置き換えで、与えられた和の形に直せば $(- 1)^{n} n!$ 。

定理包除原理による全射の数

k = 0 \sum n (- 1)^{k} (k n) (n - k)^{n}

(

n

個から

n

個への全射)

① 全射 $=$ 全単射で $n!$ 。 ${1, \dots, n} \to {1, \dots, n}$ の写像が全射なら、値域が $n$ 個すべてを覆い、大きさが等しいので単射でもある(全単射)。よって全射の数は $n!$ 。

② 包除で数える。 値域の $k$ 個の要素を“覆わない”とする場合を包除で足し引きすると、全射の数は $k = 0 \sum n (- 1)^{k} (k n) (n - k)^{n} = n! .$ ③ 置換して目的の和に。 $k \to n - k$ と置換する。 $(n - k n) = (k n)$ 、 $(- 1)^{n - k} = (- 1)^{n} (- 1)^{k}$ だから $n! = k = 0 \sum n (- 1)^{n - k} (k n) k^{n} = (- 1)^{n} k = 0 \sum n (- 1)^{k} (k n) k^{n} .$ よって $k = 0 \sum n (- 1)^{k} (k n) k^{n} = (- 1)^{n} n!$ 。

まとめ 符号つき二項和は「全射の個数」の包除表示。全射=全単射で $n!$ 、置換 $k \to n - k$ で目的の和が $(- 1)^{n} n!$ と分かる。数え上げ・包除・二項の融合。 $n = 3$ なら $- 6$ 。

発展 — 一歩先へ。 べきを下げると $\sum (- 1)^{k} (k n) k^{m} = 0$ ( $0 \leq m < n$ )— 「 $n$ 回差分すると $n$ 次未満は消える」の言い換えで、こちらも全射の数え上げ(不足するから0)として読める。この「二項係数×交互符号は $n$ 階差分」という翻訳は、スターリング数の一般式 $S (n, m) = \frac{1}{m !} \sum (- 1)^{k} (k m) (m - k)^{n}$ の背景でもある。

答

$n$ 個から $n$ 個への全射(=全単射 $n!$ 通り)を包除で数えると $\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{n} = n!$ 。 $k \to n - k$ の置換で $\sum (- 1)^{k} (k n) k^{n} = (- 1)^{n} n!$ 。

別解

「n 回差をとる」と読む(階差の言葉)。 数列 $f (x)$ の階差を $Δ f (x) = f (x + 1) - f (x)$ とすると、 $n$ 回繰り返した階差は二項係数で書ける:

$Δ^{n} f (0) = k = 0 \sum n (- 1)^{n - k} (k n) f (k)$

— 与えられた和は( $(- 1)^{n}$ 倍を除いて) $f (x) = x^{n}$ の $n$ 階の階差そのものだ。

ここで階差の性質: 多項式の階差は次数を1下げ、先頭係数に次数を掛ける( $Δ x^{m} = m x^{m - 1} + \dots$ 、微分とそっくり)。 $n$ 次の $x^{n}$ を $n$ 回差分すると、 $n \cdot (n - 1) \dots 1 = n!$ という定数だけが残る(低次の項は途中で消滅する)。よって

$k = 0 \sum n (- 1)^{k} (k n) k^{n} = (- 1)^{n} Δ^{n} (x^{n})_{x = 0} = (- 1)^{n} n!$

全射の数え上げ(本解)は組合せの物語、階差は「離散の微分を $n$ 回」という解析の物語。同じ和が2つの世界の橋になっている。

ポイント

$n$ 個から $n$ 個への全射は全単射で $n!$ 通り。
包除で $\sum (- 1)^{k} (k n) (n - k)^{n} = n!$ 。
$k \to n - k$ の置換で $\sum (- 1)^{k} (k n) k^{n} = (- 1)^{n} n!$ 。

よくある間違い

包除の式を $(n - k)^{n}$ でなく $k^{n}$ で立てて符号がずれる( $k \to n - k$ の置換で $(- 1)^{n}$ 倍が出る — この符号が答えの $(- 1)^{n}$ )。
「全射 $=$ 全単射」( $n$ 人から $n$ 人へ)の理由(有限集合で個数が同じ)を書かない。
$k = 0$ の項( $0^{n}$ や $n^{n}$ )の扱いを雑にして和の端が崩れる。