Vandermondeの畳み込みと一般化二項係数

以前 2nCnの公式 - Lilliput Steps という記事を書いたのですが、ここで示した等式は Vandermonde の畳み込みという名前が付いていました。
実は、二項係数を以下のように拡張した枠組み

$\displaystyle\binom{r}{k} := \begin{cases} \dfrac{r \cdot (r - 1) \cdot (r - 2) \cdot \ldots \cdot (r - k + 1)}{k!} & (k \geq 0) \\ 0 & ({\rm otherwise}) \end{cases},\quad r \in \mathbb{R}, k \in \mathbb{Z}$

を考えると、Vandermondeの畳み込みを出発点として様々な畳込み公式を導くことができます。
ここでは、上記の二項係数を一般化二項係数と呼ぶことにします。

Vandermonde の畳み込みを再確認

まず、一般化二項係数について、通常の Vandermonde の畳み込み

$\displaystyle\binom{r}{n} = \sum_{k \in \mathbb{Z}} \binom{r - r'}{k} \binom{r'}{n - k},\quad r, r' \in \mathbb{R}, n \in \mathbb{Z}$

が成り立つことを確認します。 $n$ が負の整数のときは両辺ともに $0$ となります。 $n$ が非負整数の場合を考えます。実数 $r$ に対して、関数 $(1 + x)^r$ の形式的冪級数展開が

$(1 + x)^r = \displaystyle\sum_{k \geq 0} \binom{r}{k} x^k$

で与えられることを利用し、 $(1 + x)^r = (1 + x)^{r - r'}(1 + x)^{r'}$ の $n$ 次の項の係数を考えることで従います。

上記の右辺の式の $k$ のインデックスを適切にずらすことで、二項係数の「下側」のインデックスをずらした式

$\displaystyle\binom{r}{n} = \sum_{k \in \mathbb{Z}} \binom{r - r'}{n_1 + k} \binom{r'}{n_2 - k},\quad r, r' \in \mathbb{R}, n, n_1, n_2 \in \mathbb{Z}, n = n_1 + n_2$

も示すことができます。

符号反転公式

一般化二項係数 $\displaystyle\binom{r}{n}$ に対して、次の符号反転公式

$\displaystyle \binom{r}{n} = (-1)^n \binom{-r + n - 1}{n}, \quad r \in \mathbb{R}, n \in \mathbb{Z}$

が成り立ちます。これは一般化二項係数の定義からすぐに確認できます。

二項係数の「上側」についての畳込み公式の導出

以上で確認した2つの式を利用することで、二項係数の「上側」についての畳み込みの公式

$\displaystyle\binom{r}{n} = \sum_{1 \leq k \leq r} \binom{k - 1}{m - 1}\binom{r - k}{n - m}, \quad r, n, m \in \mathbb{Z}_{\geq 0}, n \geq m$

が示せます。*1

まず、非負整数 $n$ と整数 $k$ に対しての一般化二項係数で $\displaystyle\binom{n}{k} = \binom{n}{n - k}$ が成り立つので、

$\begin{align} \sum_{1 \leq k \leq r} \binom{k - 1}{m - 1}\binom{r - k}{n - m} &= \sum_{1 \leq k \leq r} \binom{k - 1}{k - 1 - m + 1}\binom{r - k}{r - k - n + m} \\ &= \sum_{1 \leq k \leq r} \binom{k - 1}{k - m}\binom{r - k}{r - k - n + m} \end{align}$

が従います。右辺の 2 つの二項係数に符号反転公式を利用することで、

$\begin{align} \sum_{1 \leq k \leq r} \binom{k - 1}{k - m}\binom{r - k}{r - k - n + m} &= \sum_{1 \leq k \leq r} \binom{(k - m) - (k - 1) - 1}{k - m}\binom{(r - k - n + m) - (r - k) - 1}{r - k - n + m} \cdot (-1)^{r - n} \\ &= (-1)^{r-n} \sum_{1 \leq k \leq r} \binom{-m}{k - m}\binom{-n + m - 1}{r - k - n + m} \end{align}$

が従います。ここに Vandermonde の畳み込みと符号反転公式を再度利用することで、

$\begin{align} (-1)^{r-n} \sum_{1 \leq k \leq r} \binom{-m}{k - m}\binom{-n + m - 1}{r - k - n + m} &= (-1)^{r - n} \binom{-n-1}{r-n} \\ &= (-1)^{r - n} \binom{-r + (r -n) -1}{r - n} \\&= \binom{r}{r - n} \\&= \binom{r}{n}\end{align}$

となり、最初に示した等式

$\displaystyle\binom{r}{n} = \sum_{1 \leq k \leq r} \binom{k - 1}{m - 1}\binom{r - k}{n - m}$

が成り立つことが示せました。

あとがき

最後に示した「上側」の畳み込み公式自体の組み合わせ的な解釈やべき級数による証明は知っていたのですが、参考文献2.を眺めていると「Vandermondeの畳み込み公式から「上側」の畳み込み公式を示せる」と書かれていたので、色々調べてみて証明を書き上げてみました。

参考文献

Summing binomial coefficients
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 1994. Concrete Mathematics: A Foundation for Computer Science (2nd. ed.). Addison-Wesley Longman Publishing Co., Inc., USA.

*1:この畳込み公式自体は、関数 $x^r/(1-x)^{r+1}$ の形式的冪級数展開を考えるともっと簡単に示すことができます。組み合わせ的な解釈も可能です。