二項係数の重み付き和(微分・代入)

方針

解答

⓪ 発想 — どう考え始めるか。 ほしい和は $\sum k^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)$。二項定理 $(1+x{)}^n=\sum (\genfrac{}{}{0ex}{}{n}{k})x^k$ の係数に $k^2$ を掛けたい。

係数に $k$ を1つ掛ける操作が「微分してから $x$ を掛ける」だ($x^k$ が $k{x}^k$ になる)。$k^2$ ならこの操作を2回繰り返す。

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

① $1$ 回目(係数に $k$)。 両辺を微分して $x$ 倍: $$x\frac{d}{dx}(1+x{)}^n=nx(1+x{)}^{n-1}=\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k.$$ ② $2$ 回目(係数に $k^2$)。 これをもう一度微分して $x$ 倍する。左辺 $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$ を代入。 左辺は $$n\cdot 1\cdot 2^{n-1}+n(n-1)\cdot 1\cdot 2^{n-2}=2^{n-2}(2n+n(n-1))=2^{n-2}(n^2+n)=n(n+1)2^{n-2}.$$ よって $\sum _{k=0}^n{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n(n+1)2^{n-2}$。

まとめ 二項定理に「微分して $x$ 倍」を $2$ 回施して係数に $k^2$ を作り、$x=1$ を代入して $n(n+1)2^{n-2}$。二項定理と微分(重み付き和)の融合。

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

別解

別解 — 「委員会と役職」で数える(得意な人向けの高い視点)。 $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}.$$

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