《具体数学》读书笔记
lao_li
·
·
个人记录
“计算机科学基础”
《具体数学》上的知识都应该是基础。——某队爷
随缘更新。
到达OI数学最高层——《具体数学》（大嘘
还是看看远方的生成函数吧。
哎呀，这不生成函数对应表吗？太美丽了家人们。
2022.10.13
用生成函数爆切MO题
具体的，求 6^{-2021}\sum_{i=2021}^{+\infty}\binom{i}{2021}(\frac{6}{7})^i
虽然不是很明白qt把这种题放到模拟题里的意义
听说当初给他们讲解时用的是二项式定理乱搞？
这就是具体数学之力/se
我只是个OIer，没有他们那样的力量
有限微积分
你说的对，但是【有限微积分】是由《具体数学》自主研发的一款全新【数列积分】游戏。游戏发生在一个被称作【整数集】的幻想世界，在这里，被【高德纳】选中的人将被授予【差分算子】，导引【移位算子】。你将扮演一位名为【微积分基本原理】的神秘角色，在自由的解题中邂逅性格各异、能力独特的【分部求和法则】们，和他们一起击败邪恶【奇技淫巧求和】势力，找回失散的【真正的数学】——同时，逐步发掘【计算机科学基础】的真相。
如果有微积分的基础，很容易上手。我一个早读就看完了这部分。
我们先仿照无限微积分的微分算子，也就是微分，定义所需的差分算子
\Delta f(x)=f(x+1)-f(x)
相应地，分母是离散的dx也就是1。
差分算子是微分算子的有限近似。
算子是一个很好的词，她用来表示一个函数生成出的另一个函数。
先从最常用、简单的函数入手。
无限微积分用x^a入门，有限微积分也可以用类似的方法。
但普通幂在有限微积分中难以处理，我们也想不到包含一堆组合数的又臭又长的式子有什么好性质。
考虑老朋友下降幂。
再说一遍，x^{\underline m}=x(x-1)(x-2)...(x-m+1)，值得注意的是，这个式子之所以是降m次幂是因为她有m个因式。
不难发现引入下降幂后
\Delta(x^{\underline m})=mx^{{\underline {m-1}}}
和无限微积分中微分的结论是相似的。
我们考虑无限微积分中的积分怎么拓展。
我们先想一下\int的意义是什么？
可不就是\sum嘛，只是\int连续，\sum离散。
如果是无限微积分，我们知道有微积分基本原理，也就是牛顿-莱布尼茨公式
\int_{a}^bf'(x)dx=f(b)-f(a)
如果你没有学过微积分，不妨这么理解这个式子
f'(x)=\frac{f(x+dx)-f(x)}{dx}
f'(x)dx=f(x+dx)-f(x)
那么我们把[a,b]的所有左右式子分别相加，右边的前后两项分别抵消，就可以得到微积分基本原理。
当然，严谨的证明还要用拉格朗日中值定理。看起来我们失去了一些严谨性？
但回到本节内容，有限微积分。我们怎么把具有优秀性质的积分拓展到离散的整数上？
因为有限微积分的离散性，这种在连续的实数中不那么严谨的方法特别适合，也就是
g(x)=\Delta f(x)$当且仅当$\sum g(x)\delta x=f(x)+C
画风不对，这是类似不定积分的，比较“有用”的是定积分，也就是
若g(x)=\Delta f(x)，那么\sum_{x=a}^{b-1} g(x)=f(b)-f(a)
简洁起见，我们将上述式子记为\sum_{a}^{b} g(x)=f(b)-f(a)
记得这个b-1
类似\int_{a}^{b}+\int_{b}^{c}=\int_{a}^{c}
我们有\sum_{a}^{b}+\sum_{b}^{c}=\sum_{a}^{c}
有了上面的东西，我们就可以解决一些问题了。
\sum_{0}^nk^{\underline m}=\frac{n^{\underline{m+1}}}{m+1}
这启示我们，对于从1开始的求和问题，转化为从0开始可能会更简便。
\sum_{0}^nk=\frac{n(n-1)}{2}
啊哈，对于更高的自然数次幂是否也可如此？
当然，用第二类斯特林数对普通幂进行拆分再分别求和即可。
那么我们顺道证明了\sum_{i=1}^ni^k是关于n的k+1次多项式的结论，意外之喜。
为了继续推进，我们要对之前的定义进行扩充。
定义
m>0,x^{\underline{-m}}=\frac{1}{(x+1)(x+2)(x+3)...(x+m)}
有了这个定义可以发现
x^{\underline{m+n}}=x^{\underline m}(x-m)^{\underline n}
这样以后，可以发现之前的差分算子在下降幂上的结论对于Z都是成立的。
所以
m\neq -1,\sum_{a}^b x^{\underline m}=\frac{x^{\underline{m+1}}}{m+1}\bigg|_{a}^{b}
m= -1,\sum_{a}^b x^{\underline m}=H_x\bigg|_{a}^{b}
其中H_x为调和级数。
所以算法复杂度中有很多H_x（大雾）。
导都导了，有没有类似e^x求导不变的优秀函数？
发现
\Delta(c^x)=(c-1)c^x
所以e^x在有限微积分中的完美替代品就是2^x。
我们又能从另一个角度得出几何级数求和公式
\sum_a^b c^x=\frac{c^x}{c-1}\bigg|_{a}^{b}=\frac{c^b-c^a}{c-1}
定义移位算子
Ef(x)=f(x+1)
虽然很可惜，有限微积分没有求导链式法则，但乘法的规则还是成立的
\Delta (uv)=u\Delta v+Ev\Delta u
顺道给出前面证过的一些原函数和导数的关系
\Delta x^{\underline m}=mx^{\underline{m-1}}
\Delta cu=c\Delta u
\Delta \frac{x^{\underline {m+1}}}{m+1}=x^{\underline{m}}
\Delta H_x=(x+1)^{\underline{-1}}=\frac{1}{x+1}
\Delta c^x=(c-1)c^x
\Delta \frac{c^x}{c-1}=c^x
\Delta (u+v)=\Delta u+\Delta v
\Delta (uv)=u\Delta v+Ev\Delta u
回到
\Delta (uv)=u\Delta v+Ev\Delta u
两边取不定和，得到著名的分部求和法则，同样在无限微积分中也有类似结论，也就是阿贝尔变换
\sum u\Delta v=uv-\sum Ev\Delta u
举个例子
\sum_{i=0}^n i2^i=\sum_{0}^{n+1}x2^x=x2^x-2^{x+1}\bigg|_{0}^{n+1}=(n-1)2^{n+1}+2
大概是得到了比较机械的求和法？
总结一下，有了有限微积分，我们可以将求和问题转化为
-
微分和积分的互逆运算
-
运用分部求和法则求和
但是对于调和级数和非整数幂，好像没有什么有用的结论。
非要求一个范围，可以考虑放缩或调整法。
放一个例题
~~好像不是很OI~~
## 生成函数
我们可以把一个数列作为一个多项式的系数，就得到了生成函数。
若无特殊说明，下标从$0$开始。
一般而言有三种生成函数
1. 普通生成函数
$$<a_0,a_1,a_2...>F(z)=\sum_{n\geq 0}a_nz^n$$
2. 指数生成函数
$$<a_0,a_1,a_2...>F(z)=\sum_{n\geq 0}\frac{a_n}{n!}z^n$$
一般用于某些可重的东西，内部无差别，要除掉一个阶乘。
3. 狄利克雷生成函数
$$<a_0,a_1,a_2...>F(z)=\sum_{n\geq 0}\frac{a_n}{n^z}z^n$$
和狄利克雷卷积和积性函数什么的密切相关。
可以拿来推导筛法什么的，但有了筛法好像就没啥用了。
先放上生成函数表
| 数列| 生成函数| 封闭形式|
| :----------- | :----------- | :----------- |
| $<1,0,0,...>$| $\sum_{n\geq0}[n=0]z^n$| $1$|
| $<0,...0,1,0,...>$| $\sum_{n\geq0}[n=m]z^n$| $z^m$|
| $<1,1,1,...>$| $\sum_{n\geq0}z^n$| $\frac{1}{1-z}$|
| $<1,-1,1,...>$| $\sum_{n\geq0}(-1)^nz^n$| $\frac{1}{1+z}$|
| $<1,0,1,0,...>$| $\sum_{n\geq 0 } [2\|n] z^n$| $\frac{1}{1-z^2}$|
| $<1,0,...,0,1,0,...,0,1,0,...>$| $\sum_{n\geq 0 } [m\|n] z^n$| $\frac{1}{1-z^m}$|
| $<1,2,3,4,...>$| $\sum_{n\geq 0 } (n+1) z^n$| $\frac{1}{(1-z)^2}$|
| $<1,c,c^2,c^3,...>$| $\sum_{n\geq 0 } c^n z^n$| $\frac{1}{1-cz}$|
| $<1,2,3,4,...>$| $\sum_{n\geq 0 } (n+1) z^n$| $\frac{1}{(1-z)^2}$|
| $<\binom{c}{0},\binom{c}{1},\binom{c}{2},\binom{c}{3},...>$| $\sum_{n\geq 0 } \binom{c}{n} z^n$| $(1+z)^c$|
| $<\binom{m}{m},\binom{m+1}{m},\binom{m+2}{m},\binom{m+3}{m},...>$| $\sum_{n\geq 0 } \binom{m+n}{m} z^n$| $\frac{1}{(1-z)^{m+1}}$|
| $<1,\binom{c+0}{1},\binom{c+1}{2},\binom{c+2}{3},...>$| $\sum_{n\geq 0 } \binom{c+n-1}{n} z^n$| $\frac{1}{(1-z)^{c}}$|
| $<0,1,\frac 1 2,\frac 1 3,\frac 1 4,...>$| $\sum_{n\geq 1 } \frac 1 {n} z^n$| $\ln\frac 1 {1-z}$|
| $<0,1,-\frac 1 2,\frac 1 3,-\frac 1 4,...>$| $\sum_{n\geq 1 } \frac {(-1)^{n+1}} {n} z^n$| $\ln (1+z)$|
| $<1,1,\frac 1 2,\frac 1 6,\frac 1 {24},\frac 1 {120},...>$| $\sum_{n\geq 0 } \frac 1 {n!} z^n$| $e^z$|
涉及阶乘啥的指数生成函数，可以考虑$e^z$的拼凑。
利用这些基本生成函数，我们可以拼凑出其他函数，下面是生成函数的一些运算
$$aF(z)+bG(z)=\sum_{n}(af_n+bg_n)z^n$$
$$z^mF(z)=\sum_{n}f_{n-m}z^n,m\geq 0$$
$$\frac{F(z)-f_0-f_1-...-f_{m-1}z^{m-1}}{z^m}=\sum_{n}f_{n+m}z^n,m\geq 0$$
$$F(cz)=\sum_{n}c^nf_nz^n$$
$$F'(z)=\sum_{n}(n+1)f_{n+1}z^n$$
$$zF'(z)=\sum_{n}nf_{n}z^n$$
$$\int_{0}^{z}F(t)dt=\sum_{n\geq 1}\frac 1 n f_{n-1}z^n$$
$$F(z)G(z)=\sum_{n}(\sum_k f_kg_{n-k})z^n$$
$$\frac 1 {1-z}F(z)=\sum_{n}(\sum_{k\leq n}f_k)z^n$$
很显然吧，没必要解释了。
大部分组合恒等式都可以借助生成函数证明，就在下面。
在OI中还有什么用呢？
有时我们可以把答案表达成生成函数的某个系数的形式，然后可以用多项式科技算出来。
还可以用来求解数列通项公式，最经典的例子是斐波那契数列和卡特兰数列。
之前看到个CMO题，差不多一个思路。
$a_0=-1,a_1=1,a_{n}=2a_{n-1}+3a_{n-2}+3^n(n\geq 2)$，求$a_n$通项。
还是留做习题。
## 二项式系数
有关二项式系数的一切。
虽然 OI 中严重依赖推式子的题实在不多，但遇到了推不出来就死了。
只记一些常用的式子就够了，二项式系数的式子太多了。
我们可以把我们熟知的组合数拓展一下
$$\binom n m=\frac {n^{\underline m}}{m!}(m\geq 0) $$
$$\binom n m=0(m< 0) $$
这样我们把$m$拓展到了$Z$，$n$拓展到了$R$，我们就有了奇奇怪怪的东西比如上指标反转。
无特殊说明，下面的组合数使用此定义。
首先是“最重要的10个恒等式”
$$\binom n m=\frac{n!}{m!(n-m)!},n\geq m \geq 0$$
$$\binom n m=\binom n{n-m},n\geq 0$$
$$\binom r k=\frac r k \binom{r-1}{k-1},k\neq 0$$
$$\binom r k=\binom{r-1}{k-1}+\binom{r-1}{k}$$
$$\binom r k=(-1)^k\binom{k-r-1}{k}$$
$$\binom r m \binom m k=\binom{r}{k}\binom {r-k}{m-k}$$
$$\sum_k \binom r k x^ky^{r-k}=(x+y)^r,r\geq 0$$
$$\sum_{k\leq n} \binom {r+k} k =\binom{r+n+1}{n}$$
$$\sum_{0\leq k\leq n} \binom {k} m =\binom{n+1}{m+1},n,m\geq 0$$
$$\sum_{k} \binom r k \binom s{n-k}=\binom{r+s}{n}$$