一般ヴァンデルモンドの畳み込み定理
一般ヴァンデルモンドの畳み込み定理
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=0}^{n-1}C\left(2n-1,k\right)=2^{2n-2}
\]
パスカルの法則
\[
C(x+1,y+1)=C(x,y+1)+C(x,y)
\]
2項係数の2乗和
\[
\sum_{j=0}^{m}C^{2}(m,j)=C(2m,m)
\]
負の整数の2項係数
\[
C\left(-m,-n\right)=\left(-1\right)^{m-n}C\left(n-1,m-1\right)
\]