範德蒙德卷積
引入
範德蒙德卷積是一種合併組合數的式子，主要應用於組合數學的公式推導。
範德蒙德卷積公式
\[
\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}
\]
證明
考慮用二項式定理證明：
\[
\begin{aligned}
\sum_{k=0}^{n+m}\binom{n+m}{k}x^k&=(x+1)^{n+m}\\
&=(x+1)^n(x+1)^m\\
&=\sum_{r=0}^n\binom{n}{r}x^r\sum_{s=0}^m\binom{m}{s}x^s\\
&=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}x^k\\
\end{aligned}
\]
即有：
\[
\binom{n+m}{k}=\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}
\]
若考慮其組合意義證明：
在一個大小為 \(n+m\) 的集合中取出 \(k\) 個數，可以等於把大小為 \(n+m\) 的集合拆成兩個集合，大小分別為 \(n\) 與 \(m\)，然後從 \(n\) 中取出 \(i\) 個數，從 \(m\) 中取出 \(k-i\) 個數的方案數。由於我們有了對於 \(i\) 的枚舉，於是只需要考慮一種拆法，因為不同的拆法之間是等價的。
推論
推論 1 及證明
\[
\sum_{i=-r}^{s}\binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s}
\]
證明與原公式證明相似。
推論 2 及證明
\[
\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}
\]
根據基礎的組合數學知識推導，有：
\[
\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\sum_{i=0}^{n-1}\binom{n}{i+1}\binom{n}{i}=\sum_{i=0}^{n-1}\binom{n}{n-1-i}\binom{n}{i}=\binom{2n}{n-1}
\]
推論 3 及證明
\[
\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}
\]
根據基礎的組合數學知識推導，有：
\[
\sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n}
\]
推論 4 及證明
\[
\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m}
\]
根據基礎的組合數學知識推導，有：
\[
\sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\sum_{i=0}^m\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}
\]
其中 \(\binom{n+m}{m}\) 是我們較為熟悉的網格圖路徑計數的方案數。所以我們可以考慮其組合意義的證明。
在一張網格圖中，從 \((0,0)\) 走到 \((n,m)\) 共走 \(n+m\) 步。規定 \((0,0)\) 位於網格圖左上角，其中向下走了 \(n\) 步，向右走了 \(m\) 步，方案數為 \(\binom{n+m}{m}\)。
換個視角，我們將 \(n+m\) 步拆成兩部分走，先走 \(n\) 步，再走 \(m\) 步，那麼 \(n\) 步中若有 \(i\) 步向右，則 \(m\) 步中就有 \(m-i\) 步向右，故得證。
習題
參考資料與註釋
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用