组合计数学习笔记

定义

\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}$$ 2. $\binom{a}{b}=\frac{a}{b}\binom{a-1}{b-1}$，一般地，$\binom{a}{b}=\frac{a^{\underline{i}}}{b^{\underline{i}}}\binom{a-i}{b-i}$，其中， $a^{\underline{i}}$ 是下降幂， $a^{\underline{i}}=\frac{a!}{(a-i)!}$。 $$\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}$$ 3. $$\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}$$ 4. $$\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}$$ 6. 范德蒙德卷积 $$\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，根本不会生成函数。 变形： $$\begin{aligned} \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}$$ 听说好像要用生成函数证明。 7. $$\left\{\begin{array}{l}n \\k\end{array}\right\}=\frac{1}{m!} \sum_{k=0}^{m}(-1)^{k}\binom{n}{k}(m-k)^{n}$$ 第二类斯特林数通项公式。

组合计数学习笔记

文章操作

相关推荐

评论

组合计数学习笔记