中心二項係数の二乗(2nCn)²になる和とその組み合わせ論的解釈

組み合わせ,二項定理,二項係数

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

はじめまして, 星林と言います. そこらへんの高校生です. 初記事です.

先日友達ととあるトピックについて議論していたところ,いい感じの恒等式が得られました. その議論を基に問題を作ったので,まずはその問題をご覧ください.

問題

（まずはご自身で考えてみることをお勧めします. そうすることで後ろの議論が読みやすくなります. ）
解答は一番最後に貼ります.
もんだい

東大入試っぽくなりました.

友達との議論

以下、友達とどのような議論をしたかをお伝えします。

ランダムウォークの問題

最初, 点$P$が問題文中の「動き」を2m回行った後に原点に戻ってくる場合の数を求めていました. 私の考え方はこうです. 上に移動する回数を$k$とすると, 下, 右, 左に移動する回数はそれぞれ$k$回,$m-k$回,$m-k$回. あとは$\overbrace{上上...上}^{k個}\overbrace{下下...下}^{k個}\overbrace{右右...右}^{m-k個}\overbrace{左左...左}^{m-k個}$を並べ替える場合の数を求め, それを$k=0$から$k=m$まで足し合わせれば良い. よって,
$$\sum_{k=0}^{m} \frac{(2m)!}{(k!)^2 ((m-k)!)^2} $$
が答え. 友達も同じ考え方で同じ答えを出していました.

原点から出発し, 距離1の格子点に移動し続けて, 2m回目の移動で原点にたどり着く移動の仕方は
$$\sum_{k=0}^{m} \frac{(2m)!}{(k!)^2 ((m-k)!)^2} $$
通り

うーん. . このシグマを陽に表したいですね. . そこで二手に分かれました. 友達のほうはこの問題の(シグマを使わない)別解を探し, 私はこのシグマを直接解きにかかることで解決を試みました.

直接解きにかかる

最初の数項を計算します

m	0	1	2	3	4	5	6
和の値	1	4	36	400	4900	63504	853776

パット見でわかることは平方数だということぐらいですね
ということで平方根を取ります

m	0	1	2	3	4	5	6
√(和の値)	1	2	6	20	70	252	924

こ, これは...!?中心二項係数!!!!!!(OEIS中心二項係数にぶち込みました)
道順を計算してたら中心二項係数が出てきました...美しい. パスカルの三角形の赤丸の部分と一致していることをお確かめください.
人間は考える葦である
証明は簡単でした. 式変形するだけ.

任意の非負整数mについて以下の等式が成り立つ.
$$\sum_{k=0}^{m} \frac{(2m)!}{(k!)^2 ((m-k)!)^2}=\binom{2m}{m}^2 $$

式変形

\begin{align*} \sum_{k=0}^{m} \frac{(2m)!}{(k!)^2 ((m-k)!)^2} &= \sum_{k=0}^{m} \frac{(2m)!}{(m!)^2} \left( \frac{m!}{k!(m-k)!} \right)^2 \\ &= \frac{(2m)!}{(m!)^2} \sum_{k=0}^{m} \binom{m}{k}^{\!2} \\ &= \binom{2m}{m} \sum_{k=0}^{m} \binom{m}{k}^{\!2} \\ &= \binom{2m}{m}^{\!2} \end{align*}
(Q.E.D.)

3行目から4行目の式変形は有名な恒等式
$$\sum_{k=0}^{m} \binom{m}{k}^{\!2}=\binom{2m}{m}$$
を使いました. 自明な恒等式$(1+x)^m(1+x)^m=(1+x)^{2m}$の両辺の$x^m$の係数を比較することで証明できます.

これであの汚い和をきれいに表せました. 陽に表せるかすら不安でしたが, ここまできれいになるのは驚きです. 一方そのころ友達のほうは...

もう一つの組み合わせ論的解釈

先ほどのランダムウォークの問題を別の方法で解くことに成功したようです. 「右」または「上」への移動の回数と, 「左」または「下」への移動の回数が一致していることに注目します. とりあえず上への移動回数を$k$と置きます. さて, 「上」$k$文字, 「下」$k$文字, 「右」$m-k$文字, 「左」$m-k$文字, 合計$2m$文字を横一列に並べることを考えます. 「上」または「右」がどこに配置されるかは$\binom{2m}{m}$通りあります. この中で「上」をどこに配置するかは$\binom{m}{k}$通りあります. (残った所には「右」が入ります). 「下」と「左」の配置数も同様に考えて$\binom{m}{k}$通りあります. したがって, このとき並べ替え方は$\binom{2m}{m}\binom{m}{k}^2$通りあります. これを$k=0$から$k=m$まで足し上げます. すると,
$$ \begin{align*} \sum_{k=0}^{m} \frac{(2m)!}{(k!)^2 ((m-k)!)^2} &= (点Pが原点に戻ってくる場合の数) \\ &= \sum_{k=0}^{m}{\binom{2m}{m}\binom{m}{k}^2}\\ &= \binom{2m}{m} \sum_{k=0}^{m} \binom{m}{k}^{\!2} \\ &= \binom{2m}{m}^{\!2} \end{align*} $$
となり, 同じ結論を導くことができました.
(ここでも先ほどの恒等式を使いました. )