一般ヴァンデルモンドの畳み込み定理
一般ヴァンデルモンドの畳み込み定理
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項係数の関係その他
\[
C\left(\alpha,\beta\right)C\left(\beta,\gamma\right)=C\left(\alpha,\gamma\right)C\left(\alpha-\gamma,\beta-\gamma\right)
\]
2項係数が0になるとき
\[
\forall m,n\in\mathbb{Z},\left(0\leq m<n\right)\lor\left(n<0\leq m\right)\lor\left(m<n<0\right)\Leftrightarrow C\left(m,n\right)=0
\]
パスカルの法則の一般形
\[
C\left(x+n,y+n\right)=\sum_{k=0}^{n}C\left(n,k\right)C\left(x,y+k\right)
\]
2項係数の飛び飛びの総和
\[
\sum_{k=-\infty}^{\infty}C\left(mn,mk+l\right)=\frac{1}{m}\sum_{j=0}^{m-1}\left(1+\omega_{m}^{j}\right)^{mn}\left(\omega_{m}^{j}\right)^{-l}
\]