《具体数学》第五章：二项式系数
KAMIYA_KINA
·
2021-09-14 08:29:52
·
个人记录
前言
Q：nmd第三到四章呢？
A：咕了。/cy
正文
5.1 基本恒等式
对于 \dbinom{n}{k} 这个符号大家肯定不陌生，这个符号表示二项式系数，当然它也具有着组合意义，一般我们叫他 n 选取 k。
对于这个符号，我们有一些规定。
在组合意义下，这个式子肯定是要求所有 OI 选手全文背诵的了。
\dbinom{n}{k}=\dfrac{n!}{(n-k)!k!}
在二项式意义下，这个式子有不同的表示方式。
\dbinom{n}{k}=\dfrac{n^{\underline{k}}}{k!}
我们称这里的 n 为上指标，k 为下指标。同时的，我们可以把这个式子 \dbinom{r}{k} 当做是一个有关于 r 的 k 次多项式，对于解题略有帮助。
根据这两个基础的式子，我们就可以推导出一系列式子了。
长公式警告！
\begin{aligned}
\dbinom{r-1}{k}+\dbinom{r-1}{k-1}&=\dfrac{(r-1)^{\underline{k}}}{k!}+\dfrac{(r-1)^{\underline{k-1}}}{(k-1)!}\\
&=\dfrac{(r-1)^{\underline{k-1}}(r-k)}{k!}+\dfrac{(r-1)^{\underline{k-1}}k}{k!}\\
&=\dfrac{(r-1)^{\underline{k-1}}r}{k!}=\dfrac{r^{\underline{k}}}{k!}=\dbinom{r}{k}
\end{aligned}
这个式子是十分重要的，他在 k 为整数时成立，因为是通过二项式系数的下降幂形式得到的。我们称之为加法公式。
根据加法公式可以推理出更多的公式。
\begin{aligned}
\sum_{k \leq n}\dbinom{r+k}{k}&=\dbinom{r}{0}+\dbinom{r+1}{1}+\cdots+\dbinom{r+n}{n}\\
&= \dbinom{r+n+1}{n}
\end{aligned}
这个式子也是需要反复背诵的……
\begin{aligned}
\sum_{0\leq k \leq n} \dbinom{k}{m}&=\dbinom{0}{m}+\dbinom{1}{m}+\cdots+\dbinom{n}{m}\\
&=\dbinom{n+1}{m+1}
\end{aligned}
当整数 m,n \geq 0 时成立。
这个式子叫做关于上指标求和。
二项式定理也是二项式系数得名的原因。
(x+y)^r = \sum_{k=0}^{r}\dbinom{r}{k}x^ky^{r-k}
这个式子是需要反复反复背诵的……
拓展吸收恒等式
我比较喜欢这么叫他。
\dbinom{r}{m}\dbinom{m}{k}=\dbinom{r}{k}\dbinom{r-k}{m-k}
当 k=1 的时候就是吸收恒等式了。
三项式定理（？）
\begin{aligned}
(x+y+z)^n&=\sum_{0\leq a,b,c\leq n}\dfrac{(a+b+c)!}{a!b!c!}x^ay^bz^c[a+b+c=n]\\
&= \sum_{0\le a,b,c \le n}\dbinom{a+b+c}{b+c}\dbinom{b+c}{c}x^ay^bz^c[a+b+c=n]
\end{aligned}
多项式系数
\begin{aligned}
\dbinom{a_1+a_2+\cdots+a_n}{a_1,a_2,\cdots,a_n}&=\dfrac{(a_1+a_2+\cdots+a_n)!}{a_1!a_2!\cdots a_n!}\\
&=\dbinom{a_1+a_2+\cdots+a_n}{a_2+\cdots+a_m}\cdots\dbinom{a_{m-1}+a_m}{a_m}
\end{aligned}
范德蒙德卷积
\sum_{k}\dbinom{r}{m+k}\dbinom{s}{n-k}=\dbinom{r+s}{n+m}
同时你也可以写成这样：
\sum_{k}\dbinom{r}{k}\dbinom{s}{n-k}=\dbinom{r+s}{n}
然后就是一些感觉没什么鸟用的式子了。
上指标反转
\dbinom{r}{k}=(-1)^k\dbinom{k-r-1}{k}
5.2 基本练习
请自己买书练习……
反正我是已经做完了。
5.3 处理技巧
只讲一个吧。
我们讲反演！
很难想象反演这东西会在这里出现。
对于二项式我们有一个非常漂亮的反演公式：
g(n)=\sum_k\dbinom{n}{k}(-1)^kf(k)\iff f(n)=\sum_k\dbinom{n}{k}(-1)^kg(k)
这是完全对称的！
我们试着证明一下？
\begin{aligned}
\sum_k\binom{n}{k}(-1)^kg(k)&=\sum_k\dbinom{n}{k}(-1)^k\sum_j\dbinom{k}{j}(-1)^jf(j)\\
&=\sum_jf(j)\sum_k\dbinom{n}{k}(-1)^{k+j}\dbinom{k}{j}\\
&=\sum_jf(j)\sum_k\dbinom{n}{j}(-1)^{k+j}\dbinom{n-j}{k-j}\\
&=\sum_jf(j)\dbinom{n}{j}\sum_k(-1)^k\dbinom{n-j}{k}\\
&=\sum_jf(j)\dbinom{n}{j}[n-j=0]= f(n)
\end{aligned}
啊哈！伪证完了。
5.4 生成函数
爷不咕了，爷要开始写了。
我们希望用某种方法来处理一个无限序列 \left
那么对于这样一个序列就可以转化为一个生成函数。
A(z)=a_0+a_1z+a_2z^2+\cdots=\sum_{k\geq 0}a_kz^k
那么几点比较基础的知识就需要引出了：
[z^n]A(z)=a_n
如果我们有两个序列 \left
A(x)=a_0+a_1x+a_2x^2+\cdots
B(x)=b_0+b_1x+b_2x^2+\cdots
那么他们的乘积就是幂级数：
\begin{aligned}
A(x)B(x)&=(a_0+a_1x+a_2x^2+\cdots)(b_0+b_1x+b_2x^2+\cdots)\\
&=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\cdots
\end{aligned}
那么这个乘积中 x^n 的系数就是
a_0b_n+a_1b_{n-1}+\cdots+a_nb_0=\sum_{k=0}^na_kb_{n-k}
如果我们想知道这样一个式子的答案：
c_n=\sum_{k=0}^na_kb_{n-k}
那么实际上
c_n=[x^n]A(x)B(x)
我们定义 \left
这个东西有什么用呢？可以让你变得很卷。
事实上他可以帮助我们研究一些恒等式，然后在 OI 中这种卷积也可以用 NTT 或者 FFT 等算法进行一定的优化从而达到解题的目的。
举个例子，比如说二项式定理所生成的序列为 \left<\dbinom r0 ,\dbinom r1,\dbinom r2,\cdots\right>.
那么写成生成函数就是：
(1+x)^r=\sum_{k\geq 0} \dbinom rk z^k
我们知道二项式定理有一个经典的恒等式：
\sum_{k=0}^n\dbinom rk\dbinom s{n-k}=\dbinom{r+s}n
这就是著名的范德蒙德卷积了，用生成函数解释起来非常的简单。
我们设 G(x)=(1+x)^r,F(x)=(1+x)^s.
那么显然有 H(x)=G(x)F(x)=(1+x)^{s+r}
[x^n]H(x)=[x^n]G(x)F(x)=\sum_{k=0}^n\dbinom rk\dbinom s{n-k}=\dbinom {r+s}n
那么接下来就要介绍一些经典的生成函数了：
\dfrac{1}{1-x}=1+x+x^2+x^3+\cdots=\sum_k x^k
这个生成函数叫做几何级数。
他有一个非常文明的应用，如果跟另一个序列卷起来，那么就可以得到之前那个序列的前缀和，比如说例题：差分与前缀和。
这个问题是可以直接用多项式快速幂解决的，虽然不如题解区的分治大爷们常数小，但是这玩意思想简单，代码直接粘板子无脑直接打。
一般的，我们思考生成函数的定义的时候，应该首先思考其系数的意义，然后思考其指数幂的意义，这是在 OI 中常用的一些 trick。
由于后面的广义二项级数和广义指数级数本人实在是没有什么实力去讲的很清楚，但是感觉单纯照抄也不太好，并且也没有什么例题可以很好地解释这一方面的问题，所以等什么时候我实力到了估计肯定会出这方面的题目的，希望这是一个可以实现的 flag。
5.5-5.7 超几何函数
这玩意，存在的意义就是让那些伟人来装 x 的，对于实际应用我觉得半毛钱用都没有，因为他并没有很好的运算规则，而且大多数的东西都是纯定义的，并没有实际应用的价值，如果有的话，请立马打我脸，我立马去学然后补这里的坑。
5.8 机械求和法
咕了。