数学B / 数列

二項係数の2乗和(ヴァンデルモンドの畳み込み)

実戦編数列二項定理組合せ係数比較単元横断

問題

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

ヒントを見る

$(1 + x)^{2 n}$ を2つの $(1 + x)^{n}$ の積とみて、 $x^{n}$ の係数を両辺で比較する。 $(k n) = (n - k n)$ が効く。

解答・解説

方針

$(1 + x)^{2 n} = (1 + x)^{n} (1 + x)^{n}$ の $x^{n}$ の係数を、右辺の積の展開(畳み込み)で作り、 $(k n) = (n - k n)$ を使ってまとめる。

解答

⓪ 発想 — どう考え始めるか。 二項係数の和の等式は、「同じ式の係数を2通りに読む」のが強い。

$(1 + x)^{2 n}$ は $(1 + x)^{n} \cdot (1 + x)^{n}$ と全く同じ式。だから展開したときの $x^{n}$ の係数も一致する。

右辺の積で $x^{n}$ を作るには、前の因子から $x^{k}$ 、後ろから $x^{n - k}$ を取る。総和に対称性 $(n - k n) = (k n)$ を使うと、平方和 $\sum (k n)^{2}$ が現れる。

定理

(k n) = (n - k n)

、および

(1 + x)^{2 n} = (1 + x)^{n} \cdot (1 + x)^{n}

① 右辺の積で $x^{n}$ の係数を作る。 $(1 + x)^{n} = i \sum (i n) x^{i}$ を2つ掛けて $x^{n}$ を作るには、指数が $i + j = n$ となる組を集める。よって $x^{n}$ の係数は $k = 0 \sum n (k n) (n - k n) .$ ② $(n - k n) = (k n)$ でまとめる。 上式は $k = 0 \sum n (k n) (k n) = k = 0 \sum n (k n)^{2}$ 。

③ 左辺の係数と比較する。 一方 $(1 + x)^{2 n}$ の $x^{n}$ の係数は $(n 2 n)$ 。同じ多項式の同じ次数の係数だから等しく $k = 0 \sum n (k n)^{2} = (n 2 n) .$

まとめ 「2乗の和」は $(k n) = (n - k n)$ で“畳み込み”に化け、 $(1 + x)^{2 n} = (1 + x)^{n} (1 + x)^{n}$ の係数比較で $(n 2 n)$ と分かる。数え上げの和を母関数の一致で閉じる典型。 $n = 3$ なら $1 + 9 + 9 + 1 = 20 = (3 6)$ 。

発展 — 一歩先へ。 一般には $\sum_{k} (k m) (p - k n) = (p m + n)$ (ヴァンデルモンドの畳み込み)。重みを付けた $\sum k (k n)^{2} = n (n - 1 2 n - 1)$ なども同じ係数比較で出る。「2つのグループから合わせて選ぶ」という数え上げが、二項係数の恒等式の共通の源だ。

答

$(1 + x)^{n} (1 + x)^{n} = (1 + x)^{2 n}$ の $x^{n}$ の係数を両辺で比べ、 $k = 0 \sum n (k n)^{2} = (n 2 n)$ 。

別解

別解 — 「男女 $n$ 人ずつから $n$ 人選ぶ」と読む(得意な人向けの高い視点)。 右辺 $(n 2 n)$ は、男 $n$ 人・女 $n$ 人の計 $2 n$ 人から $n$ 人選ぶ場合の数だ。

同じ選び方を、女子の人数 $k$ で場合分けして数え直す。女子を $k$ 人選ぶと男子は $n - k$ 人で、その数は

$(k n) (n - k n) = (k n) (k n) = (k n)^{2}$

( $(n - k n) = (k n)$ )。 $k = 0, \dots, n$ で足せば左辺になる。

同じ集合を2通りに数えただけで、式変形は一度もしていない。係数比較(本解)で $x^{k}$ と $x^{n - k}$ が分担していたのは、この「女子 $k$ 人・男子 $n - k$ 人」の分担そのものだ。

ポイント

$(k n)^{2} = (k n) (n - k n)$ と見て畳み込みに直す。
$(1 + x)^{2 n} = (1 + x)^{n} (1 + x)^{n}$ の $x^{n}$ の係数を両辺で比較。
答えは中心二項係数 $(n 2 n)$ 。

よくある間違い

対称性 $(n - k n) = (k n)$ を使う一言を飛ばし、畳み込みが平方和にまとまらない。
$x^{n}$ の係数を「 $x^{k}$ どうしの積」で数える(前 $x^{k}$ ・後ろ $x^{n - k}$ でべきの合計が $n$ )。
小さい $n$ で検算しない( $n = 2$ : $1 + 4 + 1 = 6 = (2 4)$ )。