母関数をいじって得られた等式

はじめに

こんにちは。母関数で遊んでいたら面白い等式が得られたので共有します。
と思ったら、 カタラン数と中心二項係数の等式一覧(結果のみ) で既出だったそうです...(証明は載っていないのでその証明ということで)

得られた等式

以下でこの式を導出した過程を説明するので、考えたい方はここで一度止めて考えてみてください。

この等式がどのようにして出てきたか

ここではどのようにしてこの等式を思いついたのかを説明します。
まず私は以下の等式について考えていました。

$$ \sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n ・・・① $$

これは、有名な
$$ \displaystyle \sum_{n=0}^{\infty} \binom{2n}{n}x^{n} = \frac{1}{\sqrt{1-4x}} ・・・② $$
の畳み込みの形になっているので、
$$ \sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = [x^n]\left(\sum_{k=0}^{\infty} \binom{2k}{k}x^{k}\right)^{2} = [x^n]\frac{1}{1-4x} = 4^{n} $$
から導けます。逆に言うと、①をうまいこと導出できれば②が導けるわけです。そして、①は組み合わせ的解釈によって導けそうな見た目をしていたので、考えてみることにしました。色々考える過程で命題１のような式が出てきました。

証明

それでは早速証明していきましょう！
まず①の左辺を言い換えていきます。$\displaystyle \binom{2k}{k} \binom{2(n-k)}{n-k}$は、$n$個の$1$と$n$個の$-1$からなる数列$a_{1}, \cdots,a_{2n}$のうち以下を満たすものの個数と言い換えられます。
・$a_{1},\cdots,a_{2k}$の中に$1,-1$はそれぞれちょうど$k$個．
・$a_{2k+1},\cdots,a_{2n}$の中に$1,-1$はそれぞれちょうど$n-k$個．
このことから、長さ$2n$の$1$と$-1$からなる数列に$a_{1}, \cdots,a_{2n}$ついて、
$\displaystyle\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k}$における寄与の回数は、$a_{1},\cdots,a_{2l}$の中に$1,-1$がそれぞれちょうど$l$個となるような$l \, (0\le l \le n)$の個数と等しくなります。
例えば、$n=4$のとき、$\{1,-1,1,1,-1,-1,1,-1\}$は、$\displaystyle\binom{0}{0} \binom{8}{4}, \binom{2}{1} \binom{6}{3},\binom{6}{3} \binom{2}{1},\binom{8}{4} \binom{0}{0}$でそれぞれ$1$つずつ寄与するので、合計で寄与は$4$回となります。
次に、寄与の回数$m \, (2 \le m \le n+1)$を固定して、寄与の回数が$m$となるような数列の個数を考えます。これは、$1$を右移動、$-1$を上移動に対応させることで、$(+1,0),(0,+1)$のいずれかを繰り返して$(0,0)$から$(n,n)$まで行く経路のうち、$(x,x) \, (0 \le x \le n)$を通る回数が$m$回であるものの個数と等しいので、この個数を考えたいです。

これを証明するために以下の有名な公式を(証明せずに)用います。

補題2より、
$$ \begin{aligned}\ \sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} \ &=\sum_{m=2}^{n+1}m\times2^{m-1}\frac{m-1}{2n-m+1}\binom{2n-m+1}{n} \\ &=\sum_{k=0}^{n-1}\frac{2^{k+1}(k+1)(k+2)}{2n-k-1}\binom{2n-k-1}{n} \end{aligned} $$
これで命題1を示すことができました。

母関数による表示

$\displaystyle\sum_{k=0}^{n-1}\frac{2^{k+1}(k+1)(k+2)}{2n-k-1}\binom{2n-k-1}{n}$は見るからに畳み込みの形をしているので、母関数を考えてみましょう。
$$ \begin{aligned}\ & \sum_{k=0}^{n-1}\frac{2^{k+1}(k+1)(k+2)}{2n-k-1}\binom{2n-k-1}{n} \\ &=[x^{n-1}]\left(\sum_{k=0}^{\infty}2^{k+1}(k+1)(k+2)x^k \right) \left(\sum_{k=0}^{\infty} \frac{1}{n+k}\binom{n+k}{n}x^k\right) \\ &=[x^{n-1}]\frac{4}{(1-2x)^3}\frac{1}{n(1-x)^n} \\ &=[x^{n-1}]\frac{4}{n(1-2x)^3(1-x)^{n}} \end{aligned} $$
となるので、
$$ [x^n]\frac{1}{(n+1)(1-2x)^3(1-x)^{n+1}}=4^{n} $$
という式が導けました。結構綺麗な形だと思ったのですがいかがでしょうか？

おまけ

当初の目的であった、$\displaystyle\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k}$の組み合わせ的解釈の1つを簡単に説明します。
数直線上を原点から出発して、毎秒$+1,-1$のどちらかを選び移動する操作を$2n$回行うことを考えます。当然全部で$2^{2n}=4^n$通りあります。別の数え上げ方として、最後に原点を通った時刻$2k \, (0 \le k \le n)$を固定します。$2k$までは$+1,-1$の個数は等しいので、$\displaystyle\binom{2k}{k}$通りあります。最後に原点を通る時刻は$2k$なので、それ以降の移動は原点を通らないように移動する方法の総数となります。証明はしませんが、実はこれは$\displaystyle\binom{2(n-k)}{n-k}$通りあります(証明は https://manabitimes.jp/math/2716 に載っています）。これより、$\displaystyle\sum_{k=0}^{n} \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n$がいえました。

まとめ

MARTHさんが母関数を使った導出方法を教えてくれました。 https://x.com/MARTH_math/status/2046966535139606658
この記事の議論を母関数を使って書くとこんな感じになると思います。

有名な等式を別の角度からみることで非自明な等式が簡単に生えたりするのは面白いですね。もっと深堀していきたいです。(次は既出じゃないのを...)
この等式の他の示し方や、①の他の組み合わせ的解釈が見つかったら教えてくださるとうれしいです。また、一部厳密性に欠けているところがあるかもしれません。議論の誤りや誤植は指摘していただけると助かります。

参考文献

1. https://manabitimes.jp/math/2716
2. https://maspypy.com/fps-power-projection
3. https://kanpurin.hatenablog.com/entry/2021/09/15/220913
4. https://combinatorics-fun.vercel.app/natori/202304/
5. https://mathlog.info/articles/Af0tMoD7Pls6355PMkw8
6. https://combinatorics-fun.vercel.app/posts/snake-oil/