【学习笔记】组合数杂项笔记

\(\binom{n}{m} = \frac{n}{m} \binom{n-1}{m-1}\) \(\to\) 可以用来消去一些神秘的系数。

二项式定理： \((x+y)^n = \sum \limits_{i=1}^n \binom{n}{i} x^i y^{n-i}\)

帕斯卡三角递推：\(\binom{n}{m}=\binom{n-1}{m} + \binom{n-1}{m-1}\)

平行求和技巧：\(\sum\limits_{i=0}^{n} \binom{r+i}{i} = \binom{r+n+1}{n}\)。
证明：\(\binom{r}{0}+\binom{r+1}{1}=\binom{r+1}{0}+\binom{r+1}{1}=\binom{r+2}{1}\)，数学归纳法得到:\(\binom{r+i}{i-1}+\binom{r+i}{i}=\binom{r+i+1}{i}\)（可从组合意义理解为钦定其中一个选没选），项前后相加得到答案。

上指标求和：\(\sum\limits_{i=0}^{n} \binom{i}{m}=\binom{n+1}{m+1}\)
证明：\(\binom{m+1}{m}+\binom{m+1}{m+1}=\binom{m+2}{m+1}\)，可同上式合并。
组合意义是枚举最后一个数出现的位置。

范德蒙德卷积：\(\binom{n+m}{k}=\sum\limits_{i=0}^k \binom{n}{i}\binom{m}{k-i}\)
证明： \((x+y)^{n+m}=(x+y)^n\times (x+y)^m\)，或组合意义为从前 n 个中选 i 个，后 m 个中选 k-i 个。

广义二项式系数：不会，先咕咕咕

杨辉三角与生成函数
杨辉三角可以写成二元生成函数，即：\(G(x,y)=\frac{1}{1-x-xy}\)。
将x或y用对方替换，可以做奇怪的二项式求和。
如将 \(y=x^k\),则\([x^n]G(x,x^k)=[x^n]\sum\limits\binom{i}{j}x^i x^{jk}=\sum\limits_{i+j\times k =n}\binom{i}{j}\)
此式可以用作\(\sum\limits_{i=0}^m\binom{m}{i}\)的求和，即令\(y=x^0\)得到\(G(x,1)=\frac{1}{1-2x}\)。而后系数提取。