一般ヴァンデルモンドの畳み込み定理
一般ヴァンデルモンドの畳み込み定理
2項係数\(C\left(n,k\right)\)は次の一般ヴァンデルモンドの畳み込み定理が成り立つ。
\[ \sum_{k_{1}+\cdots+k_{p}=m}\prod_{j=1}^{p}C\left(n_{j},k_{j}\right)=C\left(\sum_{j=1}^{p}n_{j},m\right) \]
2項係数\(C\left(n,k\right)\)は次の一般ヴァンデルモンドの畳み込み定理が成り立つ。
\[ \sum_{k_{1}+\cdots+k_{p}=m}\prod_{j=1}^{p}C\left(n_{j},k_{j}\right)=C\left(\sum_{j=1}^{p}n_{j},m\right) \]
\(p=2\)のとき、
\[ \sum_{k_{1}+k_{2}=m}C\left(n_{1},k_{1}\right)C\left(n_{2},k_{2}\right)=C\left(n_{1}+n_{2},m\right) \] \(p=3\)のとき、
\[ \sum_{k_{1}+k_{2}+k_{3}=m}C\left(n_{1},k_{1}\right)C\left(n_{2},k_{2}\right)C\left(n_{3},k_{3}\right)=C\left(n_{1}+n_{2}+n_{3},m\right) \] となる。
\[ \sum_{k_{1}+k_{2}=m}C\left(n_{1},k_{1}\right)C\left(n_{2},k_{2}\right)=C\left(n_{1}+n_{2},m\right) \] \(p=3\)のとき、
\[ \sum_{k_{1}+k_{2}+k_{3}=m}C\left(n_{1},k_{1}\right)C\left(n_{2},k_{2}\right)C\left(n_{3},k_{3}\right)=C\left(n_{1}+n_{2}+n_{3},m\right) \] となる。
\(p=2\)のとき通常のヴァンデルモンドの畳み込み定理なので成り立つ。
\(p=q\)のとき成り立つと仮定すると、
\begin{align*} \sum_{k_{1}+\cdots+k_{q+1}=m}\prod_{j=1}^{q+1}C\left(n_{j},k_{j}\right) & =\sum_{k_{q+1}=0}^{m}\sum_{k_{1}+\cdots+k_{q}=m-k_{q+1}}\prod_{j=1}^{q+1}C\left(n_{j},k_{j}\right)\\ & =\sum_{k_{q+1}=0}^{m}C\left(n_{q+1},k_{q+1}\right)\sum_{k_{1}+\cdots+k_{q}=m-k_{q+1}}\prod_{j=1}^{q}C\left(n_{j},k_{j}\right)\\ & =\sum_{k_{q+1}=0}^{m}C\left(n_{q+1},k_{q+1}\right)C\left(\sum_{j=1}^{p}n_{j},m-k_{q+1}\right)\\ & =C\left(\sum_{j=1}^{q+1}n_{j},m\right) \end{align*} となるので\(p=q+1\)で成り立つ。
従って数学的帰納法より与式は成り立つ。
\(p=q\)のとき成り立つと仮定すると、
\begin{align*} \sum_{k_{1}+\cdots+k_{q+1}=m}\prod_{j=1}^{q+1}C\left(n_{j},k_{j}\right) & =\sum_{k_{q+1}=0}^{m}\sum_{k_{1}+\cdots+k_{q}=m-k_{q+1}}\prod_{j=1}^{q+1}C\left(n_{j},k_{j}\right)\\ & =\sum_{k_{q+1}=0}^{m}C\left(n_{q+1},k_{q+1}\right)\sum_{k_{1}+\cdots+k_{q}=m-k_{q+1}}\prod_{j=1}^{q}C\left(n_{j},k_{j}\right)\\ & =\sum_{k_{q+1}=0}^{m}C\left(n_{q+1},k_{q+1}\right)C\left(\sum_{j=1}^{p}n_{j},m-k_{q+1}\right)\\ & =C\left(\sum_{j=1}^{q+1}n_{j},m\right) \end{align*} となるので\(p=q+1\)で成り立つ。
従って数学的帰納法より与式は成り立つ。
ページ情報
| タイトル | 一般ヴァンデルモンドの畳み込み定理 |
| URL | https://www.nomuramath.com/oru3xm8z/ |
| SNSボタン |
2項係数の総和その他
\[
\sum_{k=1}^{n-1}\frac{C\left(k-n,k\right)}{k}=-H_{n-1}
\]
2項係数の関係その他
\[
C\left(\alpha,\beta\right)C\left(\beta,\gamma\right)=C\left(\alpha,\gamma\right)C\left(\alpha-\gamma,\beta-\gamma\right)
\]
2項係数の第1引数と第2引数同士の総和
\[
\sum_{j=0}^{k-a}\left(-1\right)^{j}C\left(k,j+a\right)C\left(j+b,c\right)=\begin{cases}
\left(-1\right)^{k-a}C\left(b-a,c-k\right) & a-b+c\leq k\\
0 & k<a-b+c
\end{cases}
\]
2項変換と交代2項変換の母関数
\[
\sum_{k=0}^{\infty}b_{k}x^{k}=\frac{1}{1-x}\sum_{k=0}^{\infty}a_{k}\left(\frac{x}{1-x}\right)^{k}
\]