ある組み合わせ的恒等式の二通りの証明（組み合わせ論・形式的冪級数）(OMC267Fから)

この記事では, $M\le N$を非負整数として

\begin{align} \sum_{a+b+c=M}\binom{N-a}{a}\binom{N-b}{b}\binom{N-c}{c}=\sum_{k=0}^{M}(-1)^k(k+1)\binom{3N-M-k}{M-k}\\ \end{align}

及び$K\ge 2$での一般化
\begin{align} \sum_{\sum_{i=1}^{K}a_i=M}\prod_{i=1}^{K}\binom{N-a_i}{a_i} =\sum_{k=0}^{M}(-1)^k\binom{K-2+k}{k}\binom{KN-M-k}{M-k} \end{align}
を二通りの方法で示す.

なお, 元の問題 （OMC267 F） では$M=102, N=207$である. 上の等式に適用すると $3N-M=519$ となるが, Lucasの定理などを用いれば, $\bmod 419\cdot 421$ において総和に寄与するのは $k=99, 100, 101, 102$ の項のみであることがわかる. したがって, これらを計算すれば答えが求まる.

以下では, 上の式($K=3$の場合)を示す. 一般化はほぼ同様の手順で示される.

組み合わせ的証明

$\binom{N-a}{a}$は, $N$段の階段を一段または二段上ることを繰り返して$N$段目まで上る方法のうち, 二段上る行動を$a$回行うものの数に等しい.
ここで, $A(x, y, z, m)$ を「$x+y+z$段の階段を一段または二段上ることを繰り返して上る方法」のうち, 以下の2つの条件を満たすものの数とする.

• 二段上る行動を$m$回行う
• $x$段目, $x+y$段目を飛ばさずに上る

このとき, 求める左辺は $A(N, N, N, M)$ に等しいことがわかる.
また, 便宜上$m$が負の時は$A(x, y, z, m)=0$とすると, 二つ目の条件に違反するものを除くことで,
\begin{align} A(x, y, z, m)=\binom{x+y+z-m}{m}-A(x-1, y-1, z, m-1)-A(x, y-1, z-1, m-1)-A(x-1, y-2, z-1, m-2) \end{align}
が得られる. この漸化式の構造は包除原理そのものであるから,
各$i, j\ (i+j\le \min\{x, y, z\})$に対する二項係数$\binom{((x-i)+(y-i-j)+(z-j))-(m-i-j)}{m-i-j}$の寄与は$(-1)^{i+j}$となる(後述の説明も参照).
よって, $M\le N$であることから左辺は次のように計算できる.
\begin{align} LHS &=A(N, N, N, M)\\ &=\sum_{\substack{i,j \ge 0 \\ i+j \le M}}(-1)^{i+j}\binom{((N-i)+(N-i-j)+(N-j))-(M-i-j)}{M-i-j}\\ &=\sum_{k=0}^M \sum_{i=0}^k (-1)^k\binom{3N-M-k}{M-k}\quad (k=i+j)\\ &=\sum_{k=0}^M (-1)^k(k+1)\binom{3N-M-k}{M-k} \quad\square \\ \end{align}

形式的冪級数による証明

\begin{align*} LHS&=\sum_{a+b+c=M}\binom{N-a}{a}\binom{N-b}{b}\binom{N-c}{c}\\ &=[x^M]\left([t^N]\frac{1}{1-t-xt^2}\right)^3\\ &=[x^M]\left([t^N]\frac{1}{(1-\alpha t)(1-\beta t)}\right)\quad \left(\alpha = \frac{1+\sqrt{1+4x}}{2}, \beta = \frac{1-\sqrt{1+4x}}{2}\right)\\ &=[x^M]\left(\frac{\alpha^{N+1}-\beta^{N+1}}{\alpha-\beta}\right)^3 \\ &=[x^M]\frac{\alpha^{3N+3}-\beta^{N+1}(3\alpha^{2N+2}-3\alpha^{N+1}\beta^{N+1}+\beta^{2N+2})}{(\alpha-\beta)^3}\\ &=[x^M]\frac{\alpha^{3N+3}}{(\alpha-\beta)^3}\\ \end{align*}
最後の変形（4行目から5行目）は, $M \le N$ という条件と, $\beta(x) = O(x)$であることに基づく.
これにより $\beta^{N+1}(\dots)$ の項は $O(x^{N+1})$ となり, 分母 $(\alpha-\beta)^3 = (\sqrt{1+4x})^3$ は定数項が $1 \ne 0$ であることから, $[x^M]$には寄与しない.

ここで(やや唐突だが)$z=1-\frac{1}{\alpha}$とおく.
また, $g(x) = \frac{\alpha^{3N+3}}{(\alpha-\beta)^3}$ とおき, これを $z$ の関数$G(z)$として表すと,
($\alpha = \frac{1}{1-z}$, $\alpha-\beta = \frac{1+z}{1-z}$などに注意して)
\begin{align*}     g(x) = G(z) = \frac{(1/(1-z))^{3N+3}}{((1+z)/(1-z))^3} = \frac{1}{(1+z)^3 (1-z)^{3N}} \end{align*}

求めたいのは $[x^M]g(x)$ である.
$x=\frac{z}{(1-z)^2}$が成り立つので, これを$\phi(z)$とする.  $\frac{dx}{dz} = \phi'(z)=\frac{1+z}{(1-z)^3}$ である.
$\phi(0)=0, \phi'(0)\ne 0$が確認できるので, Lagrangeの反転公式(または置換積分)より,
\begin{align*} LHS&=[x^M] g(x)\\ &=\frac{1}{2\pi i}\oint \frac{g(x)}{x^{M+1}}\ dx\\ &= \frac{1}{2\pi i} \oint \frac{G(z)}{(\phi(z))^{M+1}} \phi'(z)\ dz \\ &= \frac{1}{2\pi i} \oint \frac{1}{(1+z)^3 (1-z)^{3N}} \cdot \frac{1}{(z/(1-z)^2)^{M+1}} \cdot \frac{1+z}{(1-z)^3}\ dz \\ &= \frac{1}{2\pi i} \oint \frac{1}{z^{M+1}} \frac{1}{(1+z)^2(1-z)^{3N-2M+1}}\ dz \\ &= [z^M] \frac{1}{(1+z)^2 (1-z)^{3N-2M+1}} \\ &=\sum_{k=0}^{M}(-1)^k(k+1)\binom{3N-2M+(M-k)}{M-k}\quad \square \end{align*}
また一般化も同様に
\begin{align*} LHS&=[x^M]\frac{\alpha^{K(N+1)}}{(\alpha-\beta)^{K}}\\ &=\frac{1}{2\pi i} \oint \frac{1}{z^{M+1}} \frac{1}{(1+z)^{K-1}(1-z)^{KN-2M+1}}\ dz \\ &=\sum_{k=0}^{M}(-1)^k\binom{K-2+k}{k}\binom{KN-2M+(M-k)}{M-k} \end{align*}
と示される.

余談

この形式的冪級数による証明の肝は, $z=1-\frac{1}{\alpha}$の置換にある.
私はこの置換を最初組み合わせ的な証明で得た結果から逆算して得たが,
形式的冪級数による証明における動機としては,

• $\alpha, \beta$に出てくる$\sqrt{1+4x}$をzの有理式で表したい
• 反転後の展開を考えて, $\phi(z), \phi'(z), G(z)$が単純になるようにしたい
  (今回の場合すべて$z, (1+z), (1-z)$の積で表される)

などを考えると自然なようにも思える(気がする)