二項係数の2乗重み和(母関数の微分)

方針

解答

⓪ 発想 — どう考え始めるか。 $\sum k^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ を1項ずつ足すのは無理。二項定理 $(1+x{)}^n=\sum (\genfrac{}{}{0ex}{}{n}{k})x^k$ を土台にして、係数に $k^2$ を出させる操作を探す。

$x^k$ を微分して $x$ を掛けると $k{x}^k$ に戻る。この「微分して $x$ 倍」を1回で係数に $k$ が1つ、2回で $k^2$ が現れる。

仕上げに $x=1$ を代入すれば、左辺が求める和、右辺が閉じた式になる。

① 1回目の微分。 両辺を $x$ で微分して $x$ を掛けると $$x\cdot n(1+x{)}^{n-1}=\sum _{k=0}^{n}k(\genfrac{}{}{0ex}{}{n}{k})x^k.$$ ② 2回目の微分。 左辺 $nx(1+x{)}^{n-1}$ をもう一度 $x$ で微分して $x$ を掛ける。積の微分から $$\frac{d}{dx}\{nx(1+x{)}^{n-1}\}=n(1+x{)}^{n-1}+n(n-1)x(1+x{)}^{n-2},$$ これに $x$ を掛けると $$nx(1+x{)}^{n-1}+n(n-1)x^2(1+x{)}^{n-2}=\sum _{k=0}^n{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k.$$ ③ $x=1$ を代入する。 左辺に $x=1$ を入れると $(1+1)=2$ より $$\sum _{k=0}^n{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\cdot 2^{n-1}+n(n-1)\cdot 2^{n-2}=2^{n-2}\{2n+n(n-1)\}=n(n+1)2^{n-2}.$$

まとめ 二項係数に $k,k^2$ が重みでつく和は、$(1+x{)}^n$ を“微分して $x$ 倍”して $k$ を下ろす母関数の技で取り出せる。$k^2$ なら2回。$x=1$ 代入で $n(n+1)2^{n-2}$。数列の和と微分が母関数で結びつく。$n=3$ なら $3\cdot 4\cdot 2=24$ で検算できる。

発展 — 一歩先へ。 同じ手を3回使えば $\sum k^3\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n^2(n+3)2^{n-3}$ も出る。組合せの読み(別解)では「委員長・書記・会計」の兼任パターンに対応する。「係数に $k$ を掛ける=役職を1つ増やす」という対応で、微分と数え上げが翻訳し合える。

別解

別解 — 「委員会と2つの役職」で数える(得意な人向けの高い視点)。 $n$ 人から委員会を作り、その中から委員長と書記を選ぶ(兼任可)。この選び方の総数を2通りに数える。

数え方1: 委員会の人数 $k$ で場合分け。委員会が $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 通り、役職が $k\times k=k^2$ 通り。合計は左辺 $\sum k^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)$。

数え方2: 役職から先に決める。

• 委員長と書記が別人: $n(n-1)$ 通り。残り $n-2$ 人は入るか入らないか自由で $2^{n-2}$。
• 兼任: $n$ 通り。残り $n-1$ 人が自由で $2^{n-1}$。

$$n(n-1)2^{n-2}+n{2}^{n-1}=n{2}^{n-2}\{(n-1)+2\}=n(n+1)2^{n-2}.$$

母関数の微分(本解)が機械的に押すところを、こちらは「誰から決めるか」の順序を入れ替えるだけで出す。$n+1$ や $2^{n-2}$ の出どころが目に見える。