ヴァンデルモンドの畳み込みとは？わかりやすく解説

ヴァンデルモンドの畳み込み（ヴァンデルモンドのたたみこみ、英: Vandermonde's convolution）またはヴァンデルモンドの恒等式（ヴァンデルモンドのこうとうしき、英: Vandermonde's identity）とは、組合せ数学における二項係数に関する恒等式の一種。具体的には、任意の自然数 $r,m,n$ に対する次の恒等式のことを指す:

{m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}

この恒等式の名前はフランスの数学者ヴァンデルモンド(1772)に因んでいるが、式自体は中国の数学者・朱世傑によって1303年に発見されていた^[1]。そのため、朱-ヴァンデルモンドの恒等式（しゅ-ヴァンデルモンドのこうとうしき、英: Chu-Vandermonde's identity）と呼称されることもある。

また、この定理とq-類似なqヴァンデルモンドの畳み込み（英語版）も存在する。

さらに、ヴァンデルモンドの恒等式には次のような多項係数に関する一般化形も存在する:

{n_{1}+\dots +n_{p} \choose m}=\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}

証明

代数学による証明

一般的に、次数がそれぞれ $m,n$ であるような多項式同士の積は、

{\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r}

で与えられる。ただし、多項式の係数について $i>m$ ならば $a_{i}=0$ であるとし、 $b_{j}$ についても同様の制約を課す。ここで、二項定理より、

(1+x)^{l}=\sum _{r=0}^{l}{l \choose r}x^{r}

が任意の自然数 $l$ に対して成立することに注意すると、 $l$ として $m,n,m+n$ をそれぞれ代入した式を利用することで、

{\begin{aligned}\sum _{r=0}^{m+n}{m+n \choose r}x^{r}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{i=0}^{m}{m \choose i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}{n \choose j}x^{j}{\biggr )}\\&=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}{m \choose k}{n \choose r-k}{\biggr )}x^{r}\end{aligned}}

が得られる。ただし、最後の変形で証明冒頭で述べた式を利用した。なお、二項係数 ${\binom {a}{b}}$ は $a<b$ の時0となるので、 $i>m$ の場合の係数 $a_{i}$ に関する制約は守られていることに注意せよ。

この式の $x^{r}$ の係数同士を比較することで、 $0\leq r\leq m+n$ なる自然数 $r$ に関するヴァンデルモンドの恒等式が証明される。 $r>m+n$ である場合は、示すべき式の両辺が0であるので、直ちに示される。以上より、任意の自然数について示すべき式が示される。

組み合わせ論による証明

ダブルカウンティング（英語版）を利用することで、ヴァンデルモンドの恒等式を組み合わせ論により証明することができる。 $1,2,\ldots ,m$ の番号が振られた白玉および、 $1,2,\ldots ,n$ の番号が振られた赤玉からなる、合計 $m+n$ 個の玉の中から $r$ 個の玉を選択して袋に詰める問題を考える。袋に玉を入れる方法は全部で

{m+n \choose r}

通りだけある。一方、 $k$ 個の白玉と $r-k$ 個の赤玉を袋に詰める方法は ${\binom {m}{k}}{\binom {n}{r-k}}$ 通りあり、これを $k=0,1,\ldots ,r$ について足し合わせることで、袋に玉を入れる方法全てを記述することができる。以上より、

{\binom {m+n}{r}}=\sum _{k=0}^{r}{m \choose k}{n \choose r-k}

が示される。これはヴァンデルモンドの恒等式に他ならない。

幾何学による証明

座標平面上に点A $(r,m+n-r)$ をとる。今、点Pが原点 $(0,0)$ を出発し、各ステップで $x$ 座標または $y$ 座標を +1 しつつ、最終的に点Aへ到達するとしたとき、そのような経路が何通りあるかを考える。点Aに辿り着くためには、 $m+n$ 回のステップ中に $r$ 回だけ $x$ 座標を+1する必要があるので、このような経路は

{\binom {m+n}{r}}

通りだけある。

ここで、 $m$ ステップ後に点Aがどこにあるかによって、全経路を場合分けする。 $m$ ステップ後の点Aの座標は $(m,0),(m-1,1),\ldots ,(0,m)$ のいずれかであり、 $(k,m-k)$ にいるような経路が実現されるには、 $m$ ステップの間に $x$ 座標が+1されることがちょうど $k$ 回発生する必要があるので、そのような経路は ${\binom {m}{k}}$ 通りだけある。同様に、 $(k,m-k)$ を出発して点Aに到着するような経路は ${\binom {n}{r-k}}$ 通りだけある。したがって、原点を出発し、 $(k,m-k)$ を中継して点Aに到達するような経路は

{\binom {m}{k}}{\binom {n}{r-k}}

通りある。これを可能な $k$ について足し合わせることで、原点を出発し点Aに到着するすべての経路が得られるので、ヴァンデルモンドの恒等式が示される。

一般化

多項係数に対する一般化

ヴァンデルモンドの恒等式を、以下のように一般化できる:

\sum _{k_{1}+\cdots +k_{p}=m}{n_{1} \choose k_{1}}{n_{2} \choose k_{2}}\cdots {n_{p} \choose k_{p}}={n_{1}+\dots +n_{p} \choose m}

この恒等式の証明も、ヴァンデルモンド恒等式と同様に代数的な手法や組み合わせ論に依拠した手法によって可能である。例えば、組み合わせ論であれば、次のような議論によって示される:

$i\in \{1,2,\ldots ,p\}$ 番目の色の玉が $n_{i}$ 個だけあり、それぞれの玉に $1,2,\ldots ,n_{i}$ の番号が割り振られているとする。全部で $n_{1}+\cdots +n_{p}$ 個ある玉の中から $m$ 個の玉を選ぶ場合の数は ${\binom {n_{1}+\cdots +n_{p}}{m}}$ である。一方、それぞれの色からそれぞれ $k_{i}$ 個ずつ玉を選択し、合計で $m$ 個の玉を選ぶような選び方は ${\binom {n_{1}}{k_{1}}}{\binom {n_{2}}{k_{2}}}\cdots {\binom {n_{p-1}}{k_{p-1}}}{\binom {n_{p}}{m-k_{1}-\cdots -k_{p-1}}}$ 通りある。これを可能な $k$ の組み合わせ全てについて数え上げれば、元の選び方に一致する。

複素数への一般化

ここまでの議論では、ヴァンデルモンドの恒等式に出てくる文字は全て自然数であるとしてきたが、その一部を複素数へと一般化することもできる。この場合、この恒等式は朱-ヴァンデルモンド恒等式と呼ばれることが多い。一般化された恒等式は

{s+t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose n-k}

という形となる。ここで、 $n$ は非負整数だが、 $s,t$ は一般に複素数である。この式を示す際は、 $(1+x)^{s}$ と $(1+x)^{t}$ を二項級数で表し、それらのコーシー積をとった結果が $(1+x)^{s+t}$ の二項級数表示に等しいことを利用する。

ヴァンデルモンドの畳み込み式を下降階乗冪を表すポッホハマー記号を使って表せば、

(s+t)_{n}=\sum _{k=0}^{n}{n \choose k}(s)_{k}(t)_{n-k}

となる。この形では、この恒等式が二項定理の陰変種の一つであることが明確に認識できる(二項定理の陰変種に関する詳細は、二項型多項式列を参照)。また、この恒等式は、ガウスの超幾何定理の特別な場合であると見なすこともできる。同定理によれば、

\;_{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (c-a-b)}{\Gamma (c-a)\Gamma (c-b)}}

が成立する。ここで、

$\;_{2}F_{1}(a,b;c;z)={\frac {\Gamma (c)}{\Gamma (a)\Gamma (b)}}\sum _{k=0,1,\ldots }{\frac {\Gamma (a+k)\Gamma (b+k)}{\Gamma (c+k)}}{\frac {z^{k}}{k!}}$

は超幾何関数であり、 $\Gamma (\cdot )$ はガンマ関数である。また、定理の要請より ${\text{Re}}(c-a-b)>0$ である。この定理からヴァンデルモンドの恒等式を再現するには、 $a=-n$ とした上で、次の式

{\frac {\Gamma (k-z)}{\Gamma (-z)}}=(-1)^{k}{\frac {\Gamma (z+1)}{\Gamma (z-k+1)}}

を必要に応じて適用すればよい。なお、この式はガンマ関数の反射公式（英語版）から導かれる。

また、Rothe–Hagen identityとして知られる次の恒等式は、この恒等式をさらに一般化したものである^[2]:

$\sum _{k=0}^{n}{\frac {x}{x+kz}}{x+kz \choose k}{\frac {y}{y+(n-k)z}}{y+(n-k)z \choose n-k}={\frac {x+y}{x+y+nz}}{x+y+nz \choose n}$

超幾何分布との関係

ヴァンデルモンドの恒等式の両辺を左辺で割ると、総和に出現する各項が非負かつそれらの合計値が1であるような項が出現するので、これらを離散的な確率とみなすことができる。このようにして得られる確率分布は超幾何分布と呼ばれ、例えば、「 $n$ 個の赤玉、 $m$ 個の白玉が入った袋から無作為に $r$ 個を同時に取り出した時に、取り出した玉の中にある赤玉の個数が $k$ 個である確率」などを記述できる。

脚注

^ Askey, Richard (1994). Orthogonal polynomials and special functions (2nd printing ed.). Philadelphia, Pa: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-018-2
^ Gould, H. W. (1956). “Some Generalizations of Vandermonde's Convolution”. The American Mathematical Monthly 63 (2): 84–91. doi:10.2307/2306429. ISSN 0002-9890. https://www.jstor.org/stable/2306429.

[1] Askey, Richard (1994). Orthogonal polynomials and special functions (2nd printing ed.). Philadelphia, Pa: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-018-2

[2] Gould, H. W. (1956). “Some Generalizations of Vandermonde's Convolution”. The American Mathematical Monthly 63 (2): 84–91. doi:10.2307/2306429. ISSN 0002-9890. https://www.jstor.org/stable/2306429.

[1]

[2]

ヴァンデルモンドの畳み込みとは？わかりやすく解説

ヴァンデルモンドの畳み込み