ヴァンデルモンドの恒等式と下降冪版二項定理

1416

はじめに

　この記事ではVandermondeの恒等式とその一般化について紹介します。
　まずヴァンデルモンドの恒等式とは以下の公式のことを言うのでした。

ヴァンデルモンドの恒等式

　非負整数 $m, n, k$ と二項係数
$(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$
について
$(\binom{m + n}{k}) = \sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n}{k - j})$
が成り立つ。

　日本語では"ヴァンデルモンドの畳み込み"と言われることが多い(っぽい)ですが、この記事では"Vandermonde's identity"の直訳として"ヴァンデルモンドの恒等式"という名称を使っています。
　またこの一般化として以下の恒等式が成り立ちます。

下降冪版二項定理

　非負整数 $n$ とポッホハマー記号
$(x)_{n} = x (x - 1) (x - 2) \dots (x - n + 1)$
について $x, y$ についての恒等式
$(x + y)_{n} = \sum_{k = 0}^{n} (\binom{n}{k}) (x)_{k} (y)_{n - k}$
が成り立つ。

　下降冪版"二項定理"と表した通りこれは通常の二項定理
$(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}$
の類似になっています。
　また非負整数 $n, k$ に対して
$(n)_{k} = \frac{n!}{(n - k)!}$
が成り立つので
$\begin{array}{rcl} (m + n)_{k} & = & k! \cdot \frac{(m + n)!}{k! (m + n - k)!} = k! (\binom{m + n}{k}) \\ = & \sum_{j = 0}^{k} (\binom{k}{j}) (m)_{j} (n)_{k - j} \\ = & \sum_{j = 0}^{k} \frac{k!}{j! (k - j)!} \cdot \frac{m!}{(m - j)!} \cdot \frac{n!}{(n - k + j)!} \\ = & k! \sum_{j = 0}^{k} \frac{m!}{j! (m - j)!} \cdot \frac{n!}{(k - j)! (n - k + j)!} \\ = & k! \sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n}{k - j}) \end{array}$
とヴァンデルモンドの恒等式の一般化となっていることがわかります。

証明

　下降冪版二項定理(定理2)を数学的帰納法で示します。

　 $n = 0$ のときは明らか。 $n$ のときに成り立つとすると
$\begin{array}{rcl} (x + y)_{n + 1} & = & (x + y - n) (x + y)_{n} \\ = & \sum_{k = 0}^{n} ((x - k) + (y - n + k)) (\binom{n}{k}) (x)_{k} (y)_{n - k} \\ = & \sum_{k = 0}^{n} (\binom{n}{k}) ((x)_{k + 1} (y)_{n - k} + (x)_{k} (y)_{n + 1 - k}) \\ = & \sum_{k = 1}^{n + 1} (\binom{n}{k - 1}) (x)_{k} (y)_{n + 1 - k} + \sum_{k = 0}^{n} (\binom{n}{k}) (x)_{k} (y)_{n + 1 - k} \\ = & \sum_{k = 0}^{n + 1} ((\binom{n}{k - 1}) + (\binom{n}{k})) (x)_{k} (y)_{n + 1 - k} \\ = & \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) (x)_{k} (y)_{n + 1 - k} \end{array}$
と $n + 1$ のときにも成り立つ(ただし $n < k$ においては $(\binom{n}{k}) = 0$ と定めるものとした)。

　通常の二項定理も
$\begin{array}{rcl} (x + y)^{n + 1} & = & (x + y) \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k} \\ = & \sum_{k = 0}^{n} (\binom{n}{k}) x^{k + 1} y^{n - k} + \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n + 1 - k} \\ = & \sum_{k = 0}^{n + 1} ((\binom{n}{k - 1}) + (\binom{n}{k})) x^{k} y^{n + 1 - k} \\ = & \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) x^{k} y^{n + 1 - k} \end{array}$
と示されるので本質的に同じと言えますね。