组合计数 学习笔记
RichardCgy
·
·
算法·理论
定义 \binom{n}{m}=\frac{n!}{m!(n-m)!} 。
所以说 C(n,m)=\binom{n}{m} 。
-
\binom{a}{b}=\binom{a-1}{b}+\binom{a-1}{b-1}
证明：
\end{align}
-
\begin{align}\sum^{n}_{i=0}\binom{n}{i} \times i \times 2^i&=\sum{i=0}^{n}i \times \frac{n}{i}\binom{n-i}{i-1}\times 2^i\\&=n \times \sum{i=0}^{n}\binom{n-1}{i-1}\times2^i\\&=2n\times3^{n-1}\end{align}
-
\sum_{i=0}^n\binom{i}{m} = \binom{n+1}{m+1}
\begin{align}\binom{n+1}{m+1}&=\binom{n}{m+1}+\binom{n}{m}\\&=\binom{n-1}{m+1}+\binom{n}{m+1}+\binom{n}{m}\\&=\dots\end{align}
-
\sum_{k=0}^{n}\binom{r+k}{k}=\binom{r+n+1}{n}
\begin{align}\notag\sum_{k=0}^n\binom{r+k}{k} &= \sum_{k=0}^{n}\binom{r+k}{r}\\&=\notag\sum_{j=r}^{r+n}\binom{j}{r}\\&=\notag\binom{r+n+1}{r+1}\\&=\notag\binom{r+n+1}{n}\end{align}
5.
\begin{align}\sum_{k \leq n}k\binom{r+k}{k}&=\sum_{k=0}^n(r+k)\binom{r+k-1}{k-1}\\&=(r+1)\sum_{k=0}^{n}\binom{r+k-1}{k-1}+\sum_{k \leq n-1}k\binom{r+k}{k}\\&=(r+1)\binom{r+n}{n-1} + \sum_{k \leq n-1}k\binom{r+k}{k}\\&=\dots\\&=(r+1)\binom{n+r+1}{n-1}\end{align}
- 范德蒙德卷积
\begin{align}\sum_{k}^{n}\binom{r}{k}\binom{s}{n-k}&=\binom{r+s}{n}\end{align}
组合意义显然。
\begin{align}\sum_{k}^{n}\binom{r}{k}\binom{s}{n-k}&=\sum_k^n\binom{r}{r-k}\binom{s}{n-k}\\&=\sum_k^n\frac{r!}{(r-k)!k!}\frac{s!}{(n-k)!(s-n+k)!}\end{align}
在不使用组合意义和数学归纳法的情况下，可以利用生成函数的方法进行证明。
考虑生成函数 ((1 + x)^r 和 (1 + x)^s。它们的二项式展开分别为：
(1 + x)^r = \sum_{k=0}^{\infty} \binom{r}{k} x^k, \quad (1 + x)^s = \sum_{m=0}^{\infty} \binom{s}{m} x^m.
将两个生成函数相乘：
(1 + x)^r (1 + x)^s = (1 + x)^{r+s}.
等式左边为：
(1 + x)^r (1 + x)^s = \left( \sum_{k=0}^{\infty} \binom{r}{k} x^k \right) \left( \sum_{m=0}^{\infty} \binom{s}{m} x^m \right).
在乘积中，x^n 的系数由所有满足 k + m = n 的项 \binom{r}{k} \binom{s}{m} x^{k+m} 给出，即 m = n - k。因此，x^n 的系数为：
\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k}.
等式右边为：
(1 + x)^{r+s} = \sum_{n=0}^{\infty} \binom{r+s}{n} x^n,
其中 x^n 的系数为 \binom{r+s}{n}。比较等式两边 x^n 的系数，得到：
\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}.
当 k > r 或 n - k > s 时，二项式系数 \binom{r}{k} 或 \binom{s}{n-k} 为零，因此求和范围隐含地仅对有效项进行，且等式成立。
\boxed{\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}}
好吧其实我是粘的 deepseek，根本不会生成函数。
变形：
\sum_{k=-q}^{l}\binom{l-k}{m}\binom{q+k}{n} & =\binom{l+q+1}{m+n+1} \\
\sum_{k}\binom{l}{m+k}\binom{s}{n+k} & =\binom{l+s}{l-m+n} \\
\sum_{k}\binom{l}{m+k}\binom{s+k}{n}(-1)^{k} & =(-1)^{l+m}\binom{s-m}{n-l}
\end{aligned}
听说好像要用生成函数证明。
-
\left\{\begin{array}{l}n \\k\end{array}\right\}=\frac{1}{m!} \sum_{k=0}^{m}(-1)^{k}\binom{n}{k}(m-k)^{n}
第二类斯特林数通项公式。