Vandermondeの恒等式
概要
Vandermondeの恒等式（Vandermonde's identity）とは、複素数 $r,s$ と $0$ 以上の整数 $k$ について $\sum_{j=0}^{k}\binom rj\binom s{k-j}=\binom{r+s}k$ が成り立つという二項係数の恒等式である。$r,s$ が $0$ 以上の整数なら、$r+s$ 個から $k$ 個を選ぶ方法を、前の $r$ 個から選ぶ個数で分けて数えた等式であり、両辺が $r,s$ の多項式であることから一般の $r,s$ に広がる。両辺に $k!$ を掛けると下降階乗冪の二項定理になり、$0$ 以上の整数 $n$ で $r=s=k=n$ とすると二項係数の平方和 $\sum_j\binom nj^2=\binom{2n}n$ を与える。
Vandermondeの恒等式（Vandermonde's identity）とは、複素数 $r,s$ と $0$ 以上の整数 $k$ について
$$
\sum_{j=0}^{k}\binom rj\binom s{k-j}=\binom{r+s}k
$$
が成り立つという、二項係数のもっとも基本的な恒等式の 1 つである。$r,s$ が $0$ 以上の整数なら、「男子 $r$ 人と女子 $s$ 人から $k$ 人を選ぶ方法を、選ばれる男子の人数 $j$ で分けて数える」という読み方ですぐに分かる。等式の両辺は $r,s$ の多項式なので、整数で成り立てば負の数や分数でも成り立つ。Chu–Vandermondeの恒等式、Vandermondeの畳み込みとも呼ばれる。行列式についての Vandermondeの行列式 とは別の事柄である。
恒等式の値打ちは、$r,s$ に何を入れてもよいところにある。$r=s=n$ とすれば二項係数の平方和 $\sum_j\binom nj^2=\binom{2n}n$ が、$r,s$ を負の整数にすれば、$0$ 以上の整数 $a,b,k$ についての「上の数」の和 $\sum_j\binom{a+j}a\binom{b+k-j}b=\binom{a+b+k+1}{a+b+1}$ が出る。両辺に $k!$ を掛けると、下降階乗冪についての二項定理になる。
この記事では、恒等式を組合せの数え上げで示し、多項式の論法で一般の $r,s$ に広げる。続いて同値な形（下降階乗冪・上昇階乗冪・多重の形）と特別な場合を導き、仮定を外すと何が崩れるかを反例で示す。
| 結果 | 内容 | 仮定 |
|---|---|---|
| thm-vdm-main | Vandermonde の恒等式 | $r,s$ は複素数、$k\ge0$ は整数 |
| cor-vdm-falling | 下降階乗冪・上昇階乗冪の二項定理 | $k\ge0$ は整数（多項式の等式） |
| cor-vdm-multi | $m$ 個の数への一般化 | $m\ge1$、$k\ge0$ は整数 |
| thm-vdm-upper | 上の数についての和 | $a,b,k\ge0$ は整数 |
定義と主張
二項係数 $\binom rk$ の $r$ を上の数、$k$ を下の数という。上の数が $0$ 以上の整数でない場合にも使うので、記号を定めておく。
複素数 $r$ と整数 $k$ に対し
$$
\binom rk:=\frac{r(r-1)\cdots(r-k+1)}{k!}\quad(k\ge1),\qquad\binom r0:=1,\qquad\binom rk:=0\quad(k< 0)
$$
と定める。分子 $r(r-1)\cdots(r-k+1)$（$k$ 個の因子の積）を $r^{\underline k}$ と書き、$r^{\underline 0}:=1$ とする（下降階乗冪）。
$r=n$ が $0$ 以上の整数のとき、$0\le k\le n$ なら $\binom nk=\frac{n!}{k!\,(n-k)!}$ は $n$ 元集合の $k$ 元部分集合の個数であり、$k>n$ なら分子が因子 $n-n=0$ を含むので $\binom nk=0$ である。したがってこの定義は、「$n$ 個から $k$ 個を選ぶ方法の数（$k< 0$ や $k>n$ なら $0$）」と一致する。$k\ge0$ を固定すると、$\binom rk$ は $r$ の $k$ 次の多項式で、係数は有理数である。
複素数 $r,s$ と $0$ 以上の整数 $k$ について
$$
\sum_{j=0}^{k}\binom rj\binom s{k-j}=\binom{r+s}k
$$
が成り立つ。同じ等式は、$\mathbb{Q}$ を含む可換環の元 $r,s$ についても（$\binom rk$ を同じ式で定めて）成り立つ。
和の範囲を $j\in\mathbb{Z}$ 全体に広げても、$j< 0$ と $j>k$ の項は def-vdm-binom の約束により $0$ なので値は変わらない。この形 $\sum_{j\in\mathbb{Z}}\binom rj\binom s{k-j}$ は、2 つの数列 $\bigl(\binom rj\bigr)_j$ と $\bigl(\binom sj\bigr)_j$ の畳み込みであり、「畳み込み」の名はここから来る。
証明
証明は 2 段に分かれる。まず $r,s$ が $0$ 以上の整数の場合を数え上げで示し、次に多項式の論法で一般の場合に広げる。
$r=m$、$s=n$ を $0$ 以上の整数とし、互いに交わらない集合 $A,B$ で $|A|=m$、$|B|=n$ となるものをとる。$A\cup B$ は $m+n$ 元集合なので、その $k$ 元部分集合 $X$ は $\binom{m+n}k$ 個ある。
各 $X$ を $j:=|X\cap A|$ で分類する。$j$ は $0\le j\le k$ の整数で、$|X\cap B|=k-j$ である。$j$ を固定すると、$X$ に組 $(X\cap A,\ X\cap B)$ を対応させる写像は、「$|X\cap A|=j$ となる $k$ 元部分集合 $X$」の全体から「$A$ の $j$ 元部分集合と $B$ の $(k-j)$ 元部分集合の組」の全体への全単射である。逆写像は $(Y,Z)\mapsto Y\cup Z$ で与えられる（$A,B$ が交わらないので $|Y\cup Z|=j+(k-j)=k$ であり、$(Y\cup Z)\cap A=Y$、$(Y\cup Z)\cap B=Z$ である）。組の個数は $\binom mj\binom n{k-j}$ である（$j>m$ や $k-j>n$ なら、そのような部分集合はなく、二項係数も $0$ である）。$j=0,1,\dots,k$ について足すと
$$
\binom{m+n}k=\sum_{j=0}^k\binom mj\binom n{k-j}
$$
を得る。$\square$
一般の場合に広げるために、2 変数の多項式についての次の補題を使う。
有理数係数の 2 変数多項式 $F(x,y)$ が、$0$ 以上の整数の組 $(a,b)$ すべてで $F(a,b)=0$ を満たすなら、$F$ は多項式として $0$ である。
1 変数の場合から始める。有理数係数の多項式 $g(x)\ne0$ の次数を $d$ とすると、$g$ の根は高々 $d$ 個である（根 $c$ があれば因数定理で $g(x)=(x-c)g_1(x)$ と書け、$g_1$ の次数は $d-1$ である。$c$ と異なる根は $g_1$ の根なので、帰納法により根は高々 $d$ 個）。したがって無限に多くの根をもつ 1 変数多項式は $0$ である。
$F(x,y)=\sum_{i=0}^{N}c_i(y)\,x^i$（$c_i$ は $y$ の多項式）と書く。$0$ 以上の整数 $b$ を固定すると、$x$ の多項式 $F(x,b)=\sum_ic_i(b)x^i$ はすべての $0$ 以上の整数 $a$ を根にもつので $0$ であり、各 $i$ で $c_i(b)=0$ である。これがすべての $0$ 以上の整数 $b$ で成り立つので、各 $c_i$ は無限に多くの根をもち $0$ である。よって $F=0$ である。$\square$
$k\ge0$ を固定し、有理数係数の 2 変数多項式
$$
F(x,y):=\sum_{j=0}^{k}\binom xj\binom y{k-j}-\binom{x+y}k
$$
を考える。ここで $\binom xj=\frac{x^{\underline j}}{j!}$ は $x$ の有理数係数の多項式である。prf-vdm-integer により、$0$ 以上の整数の組 $(a,b)$ すべてで $F(a,b)=0$ である。lem-vdm-poly により $F=0$ である。
$\mathbb{Q}$ を含む可換環 $R$ の元 $r,s$ について、$x\mapsto r$、$y\mapsto s$ の代入は $\mathbb{Q}[x,y]$ から $R$ への環準同型であり、$\binom xj$ の像は $\binom rj$ である（定義の式の各因子が対応する因子に移る）。$F=0$ の像をとれば、$R$ で $\sum_j\binom rj\binom s{k-j}=\binom{r+s}k$ が成り立つ。$R=\mathbb{C}$ とすれば複素数の場合である。$\square$
別の証明：多項式の係数を比べる（0 以上の整数の場合）
$m,n$ を $0$ 以上の整数とする。多項式の等式 $(1+t)^m(1+t)^n=(1+t)^{m+n}$ の両辺を 二項定理 で展開する。左辺は $\sum_i\binom mit^i\cdot\sum_l\binom nlt^l$ で、その $t^k$ の係数は $i+l=k$ となる組についての和 $\sum_{j=0}^k\binom mj\binom n{k-j}$ である。右辺の $t^k$ の係数は $\binom{m+n}k$ である。等しい多項式の係数は等しいので、恒等式を得る。一般の $r,s$ へは prf-vdm-main と同じ論法で広げる。
数え上げの証明が直接扱えるのは $0$ 以上の整数だけだが、補題によって等式は多項式の等式になり、どんな数を代入しても成り立つ。この「整数で示して多項式で広げる」論法は、二項係数の恒等式を一般の上の数に広げる標準的な方法である。
同値な形
下降階乗冪と上昇階乗冪
$k$ 次の上昇階乗冪を $x^{\overline k}:=x(x+1)\cdots(x+k-1)$（$x^{\overline 0}:=1$）と書く。
$0$ 以上の整数 $k$ について、多項式の等式
$$
(x+y)^{\underline k}=\sum_{j=0}^k\binom kj\,x^{\underline j}\,y^{\underline{k-j}},\qquad(x+y)^{\overline k}=\sum_{j=0}^k\binom kj\,x^{\overline j}\,y^{\overline{k-j}}
$$
が成り立つ。
thm-vdm-main を多項式の等式（prf-vdm-main の $F=0$）として読み、両辺に $k!$ を掛ける。$k!\binom xj\binom y{k-j}=\frac{k!}{j!\,(k-j)!}x^{\underline j}y^{\underline{k-j}}=\binom kjx^{\underline j}y^{\underline{k-j}}$、$k!\binom{x+y}k=(x+y)^{\underline k}$ なので、1 つめの等式を得る。
1 つめの等式に $x\mapsto-x$、$y\mapsto-y$ を代入する。各因子から $-1$ をくくり出すと $(-x)^{\underline j}=(-x)(-x-1)\cdots(-x-j+1)=(-1)^jx^{\overline j}$ なので、
$$
(-1)^k(x+y)^{\overline k}=\sum_{j=0}^k\binom kj(-1)^jx^{\overline j}(-1)^{k-j}y^{\overline{k-j}}
$$
である。両辺に $(-1)^k$ を掛ければ 2 つめの等式を得る。$\square$
$(x+y)^k=\sum_j\binom kjx^jy^{k-j}$ の冪をすべて階乗冪に置き換えた形をしている。逆に 1 つめの等式を $k!$ で割れば thm-vdm-main に戻るので、Vandermonde の恒等式と下降階乗冪の二項定理は同じ内容である。下降階乗冪の形には、$m+n$ 元集合から長さ $k$ の重複のない列を作る方法を数える直接の証明もある（順列 の記事の定理「下降階乗の二項定理」）。
多重の形
$m\ge1$、$k\ge0$ を整数とし、$r_1,\dots,r_m$ を複素数とする。このとき
$$
\sum_{\substack{j_1,\dots,j_m\ge0\\ j_1+\cdots+j_m=k}}\ \prod_{i=1}^m\binom{r_i}{j_i}=\binom{r_1+\cdots+r_m}k
$$
が成り立つ。
$m=1$ では左辺は $j_1=k$ の 1 項 $\binom{r_1}k$ だけで、主張は明らかである。$m\ge2$ とし、$m-1$ で正しいとする。左辺の和を $j_m=:l$ の値で分けると、残りの $j_1,\dots,j_{m-1}$ は和が $k-l$ の $0$ 以上の整数の組全体を動くので、帰納法の仮定により
$$
\text{左辺}=\sum_{l=0}^k\binom{r_m}l\binom{r_1+\cdots+r_{m-1}}{k-l}
$$
である。thm-vdm-main を $r=r_m$、$s=r_1+\cdots+r_{m-1}$ に使うと、これは $\binom{r_1+\cdots+r_m}k$ に等しい。$\square$
$r_i$ がすべて $0$ 以上の整数なら、互いに交わらない $m$ 個の集合の和集合から $k$ 個を選ぶ方法を、各集合から選ぶ個数で分類した等式と読める。
特別な場合と例
$n\ge0$ を整数とし、thm-vdm-main で $r=s=k=n$ とおく。$0\le j\le n$ では $\binom n{n-j}=\binom nj$ なので
$$
\sum_{j=0}^n\binom nj^2=\binom{2n}n
$$
である。$n=3$ では $1+9+9+1=20=\binom63$、$n=4$ では $1+16+36+16+1=70=\binom84$ である。
$r=s=-1$ とする。$\binom{-1}j=\frac{(-1)(-2)\cdots(-j)}{j!}=(-1)^j$ なので、左辺は $\sum_{j=0}^k(-1)^j(-1)^{k-j}=(k+1)(-1)^k$ である。右辺は $\binom{-2}k=\frac{(-2)(-3)\cdots(-k-1)}{k!}=(-1)^k\frac{(k+1)!}{k!}=(-1)^k(k+1)$ で、両辺は一致する。この場合は「人を選ぶ」という読み方ができないが、prf-vdm-main により等式は成り立っている。
上の数を負の整数にすると、次の形の和が得られる。
$a,b,k$ を $0$ 以上の整数とする。
- $\displaystyle\sum_{j=0}^k\binom{a+j}a\binom{b+k-j}b=\binom{a+b+k+1}{a+b+1}$。
- $n:=a+b+k$ とおくと、1 は $\displaystyle\sum_{t=0}^{n}\binom ta\binom{n-t}b=\binom{n+1}{a+b+1}$ と同じである。
1：$0$ 以上の整数 $c,j$ について、分子の各因子から $-1$ をくくり出すと
$$
\binom{-c-1}j=\frac{(-c-1)(-c-2)\cdots(-c-j)}{j!}=(-1)^j\frac{(c+1)(c+2)\cdots(c+j)}{j!}=(-1)^j\binom{c+j}j=(-1)^j\binom{c+j}c
$$
である。thm-vdm-main を $r=-a-1$、$s=-b-1$ に使うと、左辺は $\sum_j(-1)^j\binom{a+j}a(-1)^{k-j}\binom{b+k-j}b=(-1)^k\sum_j\binom{a+j}a\binom{b+k-j}b$、右辺は $\binom{-(a+b+1)-1}k=(-1)^k\binom{a+b+1+k}k$ である。$(-1)^k$ で割り、$\binom{a+b+k+1}k=\binom{a+b+k+1}{a+b+1}$ を使えば 1 を得る。
2：2 の和で $t< a$ の項は $\binom ta=0$、$t>n-b=a+k$ の項は $\binom{n-t}b=0$ なので、残るのは $t=a+j$（$0\le j\le k$）の項で、そのとき $n-t=b+k-j$ である。よって 2 の左辺は 1 の左辺と同じ和である。$\square$
2 には直接の数え上げの証明もある。$\{0,1,\dots,n\}$（$n+1$ 元集合）の $(a+b+1)$ 元部分集合を、小さい方から $a+1$ 番目の元 $t$ で分類すると、$t$ より小さい $a$ 個は $\{0,\dots,t-1\}$ から $\binom ta$ 通り、$t$ より大きい $b$ 個は $\{t+1,\dots,n\}$ から $\binom{n-t}b$ 通りに選べる。$b=0$ とすると $\sum_{t=0}^n\binom ta=\binom{n+1}{a+1}$ で、これは Pascal の三角形の斜めの列の和についてのホッケースティック恒等式である（二項定理と組合せの恒等式）。たとえば $a=1$、$n=3$ では $0+1+2+3=6=\binom42$ である。
赤玉 $m$ 個と白玉 $n$ 個が入った袋から、$k$ 個（$0\le k\le m+n$）を同時に取り出す。$m+n$ 個の玉を区別すると、取り出し方は $\binom{m+n}k$ 通りで、どれも同じ確率で起こるとする。赤玉がちょうど $j$ 個である取り出し方は $\binom mj\binom n{k-j}$ 通りなので、その確率は
$$
p_j=\frac{\binom mj\binom n{k-j}}{\binom{m+n}k}\qquad(0\le j\le k)
$$
である（この分布を超幾何分布という）。thm-vdm-main により $\sum_jp_j=1$ である。たとえば $m=3$、$n=2$、$k=2$ では $p_0=\frac1{10}$、$p_1=\frac6{10}$、$p_2=\frac3{10}$ である。同じ恒等式は、成功確率が等しい独立な二項分布の和がまた二項分布になることの計算にも現れる（二項分布 の命題「独立な二項分布の和」）。
thm-vdm-main は Gauss の超幾何級数が有限で終わる場合の和公式の特別な場合でもある（超幾何級数 の系「Chu–Vandermondeの恒等式」）。
反例と注意
等式 $\binom{r+s}k=\binom rk+\binom sk$ は一般には成り立たない。$r=s=1$、$k=2$ では左辺は $\binom22=1$、右辺は $\binom12+\binom12=0$ である。$k$ 次式である $\binom rk$ は $k\ge2$ では $r$ について加法的でなく、正しい式は thm-vdm-main のように $j=1,\dots,k-1$ の「交差項」を含む。この例では $\sum_j\binom1j\binom1{2-j}$ の $j=1$ の項 $1\cdot1=1$ が右辺の値 $1$ のすべてである。$k=1$ では $\binom{r+s}1=r+s=\binom r1+\binom s1$ で成り立つ。
$0$ 以上の整数 $n$ では $\binom nj=\binom n{n-j}$（すべての整数 $j$）が成り立つ。これと thm-vdm-main を合わせると、$s$ が $0$ 以上の整数のとき $\sum_j\binom rj\binom sj=\sum_j\binom rj\binom s{s-j}=\binom{r+s}s$ が出る。$s$ が $0$ 以上の整数という仮定を外すと、この式は成り立たない。$r=1$、$s=-2$ では
$$
\sum_j\binom1j\binom{-2}j=1+1\cdot(-2)=-1,\qquad\binom{r+s}s=\binom{-1}{-2}=0
$$
である（$\binom{-1}{-2}$ は下の数が負なので $0$）。崩れるのは対称性で、$\binom{-2}1=-2$ だが $\binom{-2}{-3}=0$ である。この例では $r=1$ が $0$ 以上の整数なので、対称性を $r$ の側で使って $\sum_j\binom r{r-j}\binom sj=\binom{r+s}r=\binom{-1}1=-1$ と正しく計算できる。
名前について
Stanley は、この恒等式を二項係数の恒等式のうちおそらく最も古いものとし、朱世傑（c. 1260–c. 1320）と A.-T. Vandermonde（1735–1796）にちなんで Chu–Vandermonde の恒等式などと呼ばれると述べている（Sta12 第 1 章の注）。$0$ 以上の整数の場合の 2 つの証明（係数の比較と数え上げ）は Sta12 Example 1.1.17 にある。
関連項目
- 前提: 二項係数, 二項定理, 多項式
- 比較: Vandermondeの行列式, 順列
- 直後に読む: 下降階乗冪, 二項定理と組合せの恒等式
- 発展: 超幾何級数, 母関数
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
