ヴァンデルモンドの畳み込み定理とは，二項係数に関する等式のひとつです．二項係数に関する等式は数多くありますが，その中でも代表的なものです．この定理を用いると，数え上げの計算が楽になることがあります．高校数学においてはマニアックな定理ですが，定理の証明過程などはよくある議論なので，知っておいて損はないでしょう．
ヴァンデルモンドの畳み込み定理: $m,n,r$ を非負整数とするとき，次の等式が成り立つ． $$\large \sum_{k=0}^r {} _m \mathrm{C} _k\cdot {} _n \mathrm{C} _{r-k}={} _{m+n} \mathrm{C} _r$$
注意
二項係数は，一般には $m\ge n$ であるような非負整数 $m,n$ に対して定義されますが，この記事では，定義を拡張して， $$m< n \ \text{または} n< 0 \Rightarrow {} _m \mathrm{C} _n =0$$ と約束します．要するに，二項係数が組合せ的な意味を超えてしまうような場合は，その値を $0$ と定めるということです．この約束のもとで，ヴァンデルモンドの畳み込み定理は任意の非負整数 $m,n,r$ に対して成り立ちます．
具体例
・$m=2,n=3,r=2$ のとき $${} _{2} \mathrm{C} _{0}\cdot {} _{3} \mathrm{C} _{2}+{} _{2} \mathrm{C} _{1}\cdot {} _{3} \mathrm{C} _{1}+ {} _{2} \mathrm{C} _{2}\cdot {} _{3} \mathrm{C} _{0}$$ $$=1\cdot 3+2\cdot 3+1\cdot 1=10$$ 一方，${} _{2+3} \mathrm{C} _{2}=10$ なので，確かに等式が成り立っています． ・$m=2,n=1,r=4$ のとき $${} _{2} \mathrm{C} _{0}\cdot {} _{1} \mathrm{C} _{4}+{} _{2} \mathrm{C} _{1}\cdot {} _{1} \mathrm{C} _{3}+ {} _{2} \mathrm{C} _{2}\cdot {} _{1} \mathrm{C} _{2}+{} _{2} \mathrm{C} _{3}\cdot {} _{1} \mathrm{C} _{1}+{} _{2} \mathrm{C} _{4}\cdot {} _{1} \mathrm{C} _{0}$$ $$=2\cdot 0+2\cdot 0+1\cdot 0+0\cdot 1+0\cdot 1=0$$ 一方，${} _{3} \mathrm{C} _{4}=0$ なので，確かに等式が成り立っています． この例のように，$r> m+n$ である場合は，左辺も右辺も必ず $0$ になります．
・$m=n=r$ のとき $${} _{n} \mathrm{C} _{n-k}={} _{n} \mathrm{C} _{k}$$ を用いると， $$\large \sum_{k=0}^n ({} _n \mathrm{C} _k)^2={} _{2n} \mathrm{C} _n$$ を得ます．この等式も比較的有名です．
二項係数に関する等式証明は，数学的帰納法がうまくいくことが多いです．ヴァンデルモンドの畳み込み定理も数学的帰納法で証明することができます．ポイントは以下の二項係数に関する公式です．
二項係数に関する公式: $${}_{n} \mathrm{C} _{k} ={}_{n-1} \mathrm{C} _{k-1} +{}_{n-1} \mathrm{C} _{k}$$
この公式の証明は，別記事 →二項係数のいろいろな公式 で紹介しているのでそちらを参考にしてください．上の公式を用いて，ヴァンデルモンドの畳み込み定理を証明します．
数学的帰納法による証明： $n,r$ に関する数学的帰納法で示す． $n=0$ のとき，(左辺)=(右辺)=${}_ m \mathrm{C} _r$ となり成立． $r=0$ のとき，(左辺)=${}_m \mathrm{C} _0\cdot {}_n \mathrm{C} _0=1$，(右辺)=${} _{m+n} \mathrm{C} _0=1$ となり成立． $(n-1,r),(n-1,r+1)$ のとき，等式が成り立つと仮定して，$(n,r+1)$ のとき，等式が成立することを示す．
仮定より，$(n-1,r)$ で等式が成り立つから， $$\color{red}{\underline{\color{black}{\sum_{k=0}^r {} _m \mathrm{C} _k\cdot {} _{n-1} \mathrm{C} _{r-k}={} _{m+n-1} \mathrm{C} _r}}}$$ また，$(n-1,r+1)$ で等式が成り立つから， $$\color{blue}{\underline{\color{black}{\sum_{k=0}^{r+1} {} _m \mathrm{C} _k\cdot {} _{n-1} \mathrm{C} _{r+1-k}={} _{m+n-1} \mathrm{C} _{r+1}}}}$$ さて， $$\sum_{k=0}^{r+1} {} _m \mathrm{C} _k\cdot {} _{n} \mathrm{C} _{r+1-k}$$ $$=\sum_{k=0}^{r+1} {} _m \mathrm{C} _k\cdot {} _{n-1} \mathrm{C} _{r-k}+\sum_{k=0}^{r+1} {} _m \mathrm{C} _k\cdot {} _{n-1} \mathrm{C} _{r+1-k}\ \ \ (\because\text{二項係数の公式})$$ $$=\color{red}{\underline{\color{black}{\sum_{k=0}^{r} {} _m \mathrm{C} _k\cdot {} _{n-1} \mathrm{C} _{r-k}}}}+\color{blue}{\underline{\color{black}{\sum_{k=0}^{r+1} {} _m \mathrm{C} _k\cdot {} _{n-1} \mathrm{C} _{r+1-k}}}}\ \ \ (\because {} _{n-1} \mathrm{C} _{r-(r+1)}={} _{n-1} \mathrm{C} _{-1}=0)$$ $$=\color{red}{\underline{\color{black}{{} _{m+n-1} \mathrm{C} _r}}}+\color{blue}{\underline{\color{black}{{} _{m+n-1} \mathrm{C} _{r+1}}}}$$ $$={} _{m+n} \mathrm{C} _{r+1}\ \ \ (\because\text{二項係数の公式})$$ したがって，$(n,r+1)$ のときも等式は成立する．
二項係数は，もともと組合せ的な意味をもつ数であることから想像できるように，ヴァンデルモンドの畳み込み定理にも，組合せ的な解釈を与えることができます．
場合の数による証明： $m$ 人の男子と $n$ 人の女子の中から $r$ 人選ぶ場合の数を $2$ 通りの方法で考える． $(1)$ $m+n$ 人の人から $r$ 人選ぶ場合の数は ${} _{m+n} \mathrm{C} _r$ である．
$(2)$ 一方，男子を何人選ぶかで場合分けして考える．$k=0,1,…,r$ に対して，男子を $k$ 人，女子を $r-k$ 人選ぶ場合の数は $${} _m \mathrm{C} _k\cdot {} _n \mathrm{C} _{r-k}$$ である．したがって， $$\sum_{k=0}^r {} _m \mathrm{C} _k\cdot {} _n \mathrm{C} _{r-k}={} _{m+n} \mathrm{C} _r$$ を得る．
問 $A$ さんと $B$ さんがそれぞれ独立に $n$ 回コインをなげるとき，表が出る回数が一致する確率はいくつか．
$n$ 回コインをなげて，表が $k$ 回 ($0\le k \le n$) 出る確率は， $$\frac{{} _n \mathrm{C} _k}{2^n}$$ である．したがって，求める確率は， $$\sum_{k=0}^n \left(\frac{{} _n \mathrm{C} _k}{2^n}\right)^n$$ $$=\frac{1}{2^{2n}}\sum_{k=0}^n ({} _n \mathrm{C} _k)^2$$ $$=\frac{{} _{2n} \mathrm{C} _n}{2^{2n}}$$ ただし最後の等式は，ヴァンデルモンドの畳み込み定理において，$m=r=n$ として適用した．
