ヴァンデルモンドの正体

組合せ論において、ヴァンダーモンドの恒等式（またはヴァンダーモンドの畳み込み）は、二項係数に対する次の恒等式です。

${\displaystyle {m+n \choose r}=\sum _{k=0}^{r}{m \choose k}{n \choose rk}}$

任意の非負整数 r、m、nに対して成り立つ。この恒等式はアレクサンドル＝テオフィル・ヴァンデルモンド（1772）にちなんで名付けられたが、1303年には中国の数学者 朱世傑によってすでに知られていた。^[1]

この定理にはq類似のq -ヴァンデルモンド恒等式と呼ばれるものがあります。

ヴァンデルモンドの恒等式は、次のような恒等式を含む様々な方法で一般化することができる。

${\displaystyle {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の2つの多項式の積は次のように表される。

${\displaystyle {\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_{rk}{\biggr )}x^{r},}$

ここで、すべての整数i  >  mに対してa _i  = 0 、 すべての整数j  >  nに対してb _j = 0という規則を使用します。二項定理により、

${\displaystyle (1+x)^{m+n}=\sum _{r=0}^{m+n}{m+n \choose r}x^{r}.}$

指数mとnについても二項定理を適用し、多項式の積についても上記の式を適用すると、次の式が得られます。

${\displaystyle {\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 rk}{\biggr )}x^{r},\end{aligned}}}$

ここで、多項式の係数に関する上記の規則は、二項係数の定義と一致しています。なぜなら、両方とも、それぞれすべてのi  >  mおよびj  >  nに対してゼロになるからです。

x ^rの係数を比較すると、0 ≤  r  ≤  m  +  nを満たすすべての整数rに対して、ヴァンダーモンドの恒等式が成り立ちます。 rがより大きい整数の場合、二項係数の定義により、ヴァンダーモンドの恒等式の両辺はゼロになります。 

ヴァンデルモンドの恒等式は、次のように組み合わせの二重カウント証明も許します。委員会がm人の男性とn人の女性で構成されているとします。r人の委員からなる小委員会を構成する方法は何通りありますか？答えは

${\displaystyle {m+n \choose r}.}$

答えは、k 人の男性とr  −  k 人の女性 で構成される小委員会の数をkのすべての可能な値にわたって合計したものです。

${\displaystyle \sum _{k=0}^{r}{m \choose k}{n \choose rk}.}$

r x ( m + n − r ) 個の正方形からなる長方形の格子を取ります。

${\displaystyle {\binom {r+(m+nr)}{r}}={\binom {m+n}{r}}}$

左下の頂点から始まり、上方向または右方向にのみ移動し、右上の頂点で終了するパス (これは、r右移動とm + n - r上移動 (またはその逆) を任意の順序で行う必要があり、パスの合計の長さがm  +  nであるためです)。左下の頂点を (0, 0) と呼びます。

(0, 0) から始まり ( k , m − k )で終わる経路があり、k 回の右移動とm − k回の上方向の移動を行う必要があります (経路の長さはm )。同様に、( k , m − k ) から始まり ( r , m + n − r ) で終わる経路があり、合計r − k回の右移動と ( m + n − r ) − ( m − k ) 回の上方向の移動を行う必要があり、経路の長さはr − k + ( m + n − r ) − ( m − k ) = nである必要があります。したがって、 ${\displaystyle {\binom {m}{k}}}$${\displaystyle {\binom {n}{rk}}}$

${\displaystyle {\binom {m}{k}}{\binom {n}{rk}}}$

(0, 0) で始まり、( r , m + n − r ) で終わり、( k , m − k ) を通過するパス。これは、 (0, 0) で始まり、( r , m + n − r )で終わるすべてのパスのサブセットなので、 k = 0からk = rまでを合計して(点 ( k , m − k ) は正方形内に制限されるため)、(0, 0) で始まり、( r , m + n − r )で終わるパスの総数を取得します。

ヴァンダーモンドの恒等式は次のように一般化できます。

${\displaystyle \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}.}$

この恒等式は、2 つ以上の多項式が使用される場合の上記の代数的導出、または単純な二重カウントの議論を通じて取得できます。

まず、最初の要素セットから要素を選択し、次に別のセットから要素を選択し、これを繰り返して、合計で 個の要素がセットから選択されるまで続けます。したがって、左側では から要素を選択しますが、これは右側でもまったく同じです。 ${\displaystyle \textstyle k_{1}}$${\displaystyle \textstyle n_{1}}$${\displaystyle \textstyle k_{2}}$${\displaystyle \textstyle p}$${\displaystyle \textstyle m}$${\displaystyle \textstyle p}$${\displaystyle \textstyle m}$${\displaystyle \textstyle n_{1}+\dots +n_{p}}$

この恒等式は非整数引数にも一般化できる。この場合、これはChu-Vandermonde恒等式として知られており（Askey 1975、pp. 59-60を参照）、次の形をとる。

${\displaystyle {s+t \choose n}=\sum _{k=0}^{n}{s \choose k}{t \choose nk}}$

一般の複素数値 sおよびtと任意の非負整数nに対して成り立ちます。これは、との二項級数を掛け合わせ、 の二項級数と比較することで、上記の代数的証明に沿って証明できます。 ${\displaystyle (1+x)^{s}}$${\displaystyle (1+x)^{t}}$${\displaystyle (1+x)^{s+t}}$

この恒等式は、下降するポッホハマー記号を用いて次のよう に書き直すことができる。

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

この形式は、明らかに二項定理の暗部変種として認識できる（二項定理の暗部変種の詳細については、二項型を参照）。チュー・ヴァンデルモンド恒等式は、ガウスの超幾何定理の特別な場合であるとも見なすことができ、ガウスの超幾何定理は、

${\displaystyle \;_{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (cab)}{\Gamma (ca)\Gamma (cb)} }}$

ここで は超幾何関数、はガンマ関数である。a =  − nをとり、次の恒等式を適用すること で、Chu-Vandermonde 恒等式が再び得られる。${\displaystyle \;_{2}F_{1}}$${\displaystyle \Gamma (n+1)=n!}$

${\displaystyle {n \choose k}=(-1)^{k}{kn-1 \choose k}}$

惜しみなく。

ローテ・ハーゲン恒等式は、この恒等式をさらに一般化したものです。

両辺を左の式で割って合計が 1 になるとき、合計の項は確率として解釈できます。結果として得られる確率分布は、超幾何分布です。これは、 n 個の赤いビー玉とm 個の青いビー玉が入った壷からr回取り替えなしで引いた場合の赤いビー玉の個数の確率分布です。

• パスカルのアイデンティティ
• ホッケースティックのアイデンティティ
• ローテ・ハーゲン恒等式