《具体数学》果真十分“具体”，远没有数学分析、高等代数那么“抽象”。这里记录了我在阅读这本书时所采撷的“心动瞬间”——这些数学公式真是令人心动——可以把这篇文章当做检索目录，遇到问题时：1、Ctrl+F；2、找到对应章节后翻书。
如何确定递归式？
记\(T_n\)表示\(n\)个圆盘的最小步数
\(T_n \le 2 T_{n-1} + 1\), 可以构造；
\(T_n \ge 2T_{n-1} + 1\)，要把最大一个拿出来至少要\(T_{n-1}+1\)，把剩下的移动正确位置，至少需要\(T_{n-1}\)。
如何求出封闭形式？
数学归纳，假设\(T_n = 2^n - 1\)。
暴力求解，记\(U_n = T_n + 1\)，则\(U_n = 2U_{n-1} = 2^n\)，从而解出\(T_n\)。
欧拉公式：F = 1 + E - V
每加入一条边，F先+1；每多出一个交点，就会多两条边，从而F又+1.
目标是最大化交点的数量。
切\(n\)刀，最多把披萨分成几块？
\(n\)条折线呢？
每一对折线可以产生\(4\)个顶点，自己本身可以产生1个，初始有1个。
\(4 \frac{n(n-1)}{2} + n + 1 = 2n^2 - n + 1\)
\(n\)个120°三叉呢？
每隔2个干掉一个？
递归，第一轮会把所有偶数位置都干掉
\(J(2n) = 2J(n) - 1\)
\(J(2n + 1) = 2 J(n) + 1\)
对递归式打表+数学归纳
用二进制形式表示？
一些性质
\(J(J(J(.....J(n))))\)最后会停在不动点——二进制下全是1的数
解\(J(n) = \frac{n}{2}\)，得\(l = \frac{1}{3} (2^m - 2)\)，m为奇数时一定有解。
拓展一下递归式？
\(f(1) = \alpha\); \(f(2n) = 2 f(n) + \beta\); \(f(2n + 1) = 2 f(n) + \gamma\).
显然\(f(n) = A(n) \alpha + B(n) \beta + C(n) \gamma\).
法一：打表、归纳
法二：带入\(f(n)=1\),\(f(n)=n\).解出对应的\(\alpha,\beta,\gamma\)，从而解出\(A(n),B(n),C(n)\).
叕拓展一下递归式？
\(f(j) = \alpha_j\); \(f(dn + j) = c f(n) + \beta_j\).
\(f((b_m b_{m-1} .... b_1 b_0)_d) = (\alpha_{b_m} \beta_{b_{m-1}} .... \beta_{b_0})_c\).
将和式转化为递归式
可得$R_n = A(n) \alpha + B(n) \beta + C(n) \gamma $。
用上一节的成套方法，即用\(R_n\)为简单函数，解出 \(\alpha,\beta,\gamma\)，从而解出\(A(n),B(n),C(n)\)
将递归式转为和式
\(a_n T_n = b_n T_{n-1} + c_n\); \(T_0\)是个常数。
令\(s_n = \frac{a_{n-1} a_{n-2} .... a_1}{b_n b_{n-1} b_2}\); 则有\(b_n s_n = a_{n-1} s_{n-1}\).
则有：\(T_n = \frac{1}{a_n s_n} (s_1 b_1 T_0 + \sum_{k=1}^{n} s_k c_k)\).
注意，要求所有\(a_n,b_n\)均不为0.
例题：计算快速排序复杂度
\(C_0 = C_1 = 0\); \(C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k\).
先转换为递归式
两边乘\(n\)：$n C_n = n(n+1) + 2\sum_{k=0}^{n-1} C_k $.
对应到\(n-1\): $(n-1) C_{n-1} = n(n-1) + 2\sum_{k=0}^{n-2} C_k $.
相减：\(n C_n = (n + 1) C_{n-1} + 2n\); \(C_2 = 3\).
应用公式
\(a_n = n\); \(b_n = n+1\); \(c_n = 2n - 2[n=1]+2[n=2]\); \(s_n = \frac{2}{n(n+1)}\)
\(C_n = 2(n+1)\sum_{k=1}^{n} \frac{1}{k+1} - \frac{2}{3}(n+1)\).
封闭形式
调和数：\(H_n = \sum_{k=1}^{n} \frac{1}{k}\).
\(C_n = 2(n+1) H_n - \frac{8}{3}n - \frac{2}{3}\).
扰动法
\(S_n = \sum_{i=0}^{n} a_n\)
\(S_n + a_{n+1} = a_0 + \sum_{i=0}^{n} a_{i+1}\)
尝试用\(S_n\)来表示右边
例题：\(S_n = \sum_{k=0}^{n} k 2^k\)
拓展：\(S_n = \sum_{k=0}^{n} k x^k\).
\(\sum_{k=0}^{n} x^k = \frac{1-x^{n+1}}{1-x}\)
求导：\(\sum_{k=0}^{n} k x^{k-1} = \frac{1-(n+1)x^n + nx^{n+1}}{(1-x)^2}\).
看起来离散和连续之间，有一种不可告人的关系
切比雪夫单调不等式
\(S = \sum_{1 \le j < k \le n} (a_k - a_j) (b_k - b_j)\)
$2S = \sum_{1 \le j,k \le n} (a_k - a_j) (b_k - b_j) = 2n \sum_{k=1}^{n} a_k b_k - 2 (\sum_{k=1}^{n} a_k) (\sum_{k=1}^{n} b_k) $
\((\sum_{k=1}^{n} a_k) (\sum_{k=1}^{n} b_k) = n \sum_{k=1}^{n} a_k b_k - \sum_{1 \le j < k \le n} (a_k - a_j) (b_k - b_j)\).
当\(a_i,b_i\)不减时，\(S \ge 0\)，上式的等号变成\(\le\)
当\(a_i\)不减，\(b_i\)不增，\(S \le 0\)，上式取\(\ge\)
连续情况下的切比雪夫不等式
例题：\(S_n = \sum_{1 \le j < k \le n} \frac{1}{k-j}\)
\(S_n = \sum_{0 \le k < n} H_k\)
\(S_n = \sum_{k=1}^{n} \frac{n-k}{k} = n H_n - n\)
从而\(\sum_{0 \le k < n} H_k = n H_n - n\). 真是神奇
讨论\(S_n = \sum_{k=1}^{n} k^2\)的解法
打表+猜测答案+数学归纳
扰动法
成套方法
\(R_n = R_{n-1} + \beta + \gamma n + \delta n^2\)
\(R_n = A(n) \alpha + B(n) \beta + C(n) \gamma + D(n) \delta\)
假定\(\delta = 0\)，\(A(n),B(n),C(n)\)和之前一样；再令\(R_n = n^3\)，解出\(D(n)\)
用积分估计，对误差递归
\(\int_0^n x^2 dx = \frac{n^3}{3}\)
令\(E_n = S_n - \frac{n^3}{3}\)
\(E_n = S_{n-1} + n^2 - \frac{n^3}{2} = E_{n-1} + \frac{(n-1)^3}{2} + n^2 - \frac{n^3}{2} = E_{n-1} + n - \frac{1}{3}\)
\(E_n\) 超级好算。
展开和放缩
\(S_n = \sum_{1 \le j \le k \le n} k = \sum_{1 \le j \le n} (j+n)(n-j+1)/2\)
拆开即可
下降幂
\(x^{\underline{m}} = x(x-1)(x-2)...(x-m+1)\)，\(m > 0\)
\(x^{\underline{-m}} = \frac{1}{(x+1)(x+2)...(x+m)}\)，\(m > 0\)
\(x^{\underline{m+n}} = x^{\underline{m}} (x - m)^{\underline{n}}\)
求解\(\sum_{a \le x < b} f(x)\)
若能找到\(f(x) = g(x+1) - g(x)\)
则答案为\(g(b) - g(a)\)
一些“原函数”
\(x^{\underline{m}} = \frac{1}{m+1}[(x+1)^{\underline{m+1}} - x^{\underline{m+1}}]\)，\(m \ne -1\)
$x^{\underline{-1}} = \frac{1}{x+1} = H(x+1) - H(x) \(，\)H(x)$是调和数
\(x = \frac{1}{2}[(x+1)x - x(x-1)]\)
\(x^n\) 要先用斯特林数化成\(x^{\underline{m}},1 \le m \le n\)的形式，然后分别找原函数
\(2^x = 2^{x+1} - 2^x\)，和连续时\(e^x\)类似
\(c^x = \frac{c^{x+1} - c^x}{c-1}\)
离散的“分部积分”
\(\sum_{a \le x < b} u(x) [v(x+1) - v(x)] = u(b) v(b) - u(a) v(a) - \sum_{a \le x < b} [u(x+1) - u(x)] v(x+1)\)
例题：\(\sum_{0 \le x < n} H_x x\)
\(x = \frac{1}{2}[(x+1)^{\underline{2}} - x^{\underline{2}}]\)，\(v(x) = \frac{1}{2} x^{\underline{2}}\)
\(H_{x+1} - H_x = x^{\underline{-1}}\)
答案为\(\frac{n^2}{2}(H_n - \frac{1}{2})\).
无限个非负数的和？
对于\(\sum_{k \in K} a_k\)，如果存在常数\(A\)，使得\(K\)的任意有限子集\(F\)都满足\(\sum_{k \in F} a_k \le A\)，则称\(A\)为一个上界；最小的\(A\)（即下确界）称为\(\sum_{k \in K} a_k\)的和。
如果不在常数\(A\)，则和为无限；可以用数分中的\(\epsilon - \delta\)语言写清楚。
如果和有限且\(K\)为自然数集，则\(\sum_{k \in K} a_k = \lim_{n->\infty} \sum_{0 \le k \le n} a_k\)。
无限和式的定义
定义\(x = x^+ - x^-\)，\(x^+ = x [x > 0]\)，\(x^- = -x[x<0]\)
\(\sum_{k \in K} a_k = \sum_{k \in K} a_k^+ - \sum_{k \in K} a_k^-\)
如果\(\sum_{k \in K} a_k^+\)和\(\sum_{k \in K} a_k^-\)都有限，则无限和式存在；如果\(\sum_{k \in K} a_k^+\)无限，另一个有限，则无限和式为\(+ \inf\). 反之亦然。如果都无限，则不予定义。
和有限的无限和式之间，满足分配率、结合律、交换律
一些反例
\(T = 1 + 2 + 4 + 8 + .....\)
\(2T = 2 + 4 + 8 + .... = T - 1\). \(T = -1\).
事实上\(T=+\infty\)
\(T = 1 - 1 + 1 - 1 + 1 .....\)
\((1 - 1) + (1 - 1) + .... = 0\)
\(1 + (-1 + 1) + (-1 +１)+.... = 1\)
事实上由等比数列可得，和为\(\frac{1}{2}\)。一群整数的和竟然是分数.....
\(...+(- \frac{1}{4}) + (- \frac{1}{3}) + (- \frac{1}{2}) + 1 + \frac{1}{2} + \frac{1}{3} + ......\)
可以等于0
可以等于\(1 + H_{2n} - H_{n+1}\)，每次右边选两个数，左边选一个数，求极限。和为\(1 + \ln(2)\)。
\(\lceil x \rceil - \lfloor x \rfloor = [x \text{不是整数}]\)
\(\lfloor \frac{n}{m} \rfloor = \lfloor \frac{cn}{cm} \rfloor\)
\(\lfloor \sqrt{\lfloor x \rfloor} \rfloor = \lfloor \sqrt{x} \rfloor\)
证明：设\(m = \lfloor \sqrt{\lfloor x \rfloor} \rfloor\)，展开得到\(x\)的范围
拓展：若\(f(x)\)是个单调递增的函数，且若\(f(x)\)是整数能推导出\(x\)是整数，则\(\lfloor f(\lfloor x \rfloor) \rfloor = \lfloor f(x) \rfloor\)
\(\lceil \sqrt{\lfloor x \rfloor} \rceil = \lceil \sqrt{x} \rceil\)？？？
在\(1 \le n \le 1000\)中，有多少整数\(n\)满足\(\lfloor n^{\frac{1}{3}} \rfloor | n\)?
设\(m = \lfloor n^{\frac{1}{3}} \rfloor\)
\(1 + \sum_{m=1}^{9} \lfloor \frac{(m+1)^3 - m^3}{m} \rfloor = 172\)
用多项式近似，可得 \(W = \frac{3}{2} N^{\frac{2}{3}} + O(N^{\frac{1}{3}})\)
谱
\(Spec(\alpha) = \{ \lfloor \alpha \rfloor , \lfloor 2 \alpha \rfloor, \lfloor 3 \alpha \rfloor, ........ \}\)
\(\sqrt{2}\)和\(2+\sqrt{2}\)的谱，构成所有正整数的划分。
\(K_0 = 1\);\(K_{n+1} = 1 + \min(2 K_{\lfloor \frac{n}{2} \rfloor}, 3 K_{\lfloor \frac{n}{3} \rfloor})\);证明\(K_n \ge n\)
约瑟夫问题新解（以 \(m = 3\) 为例）：
刚开始有\(n\)个人，每次有一个活下去就把他的标号+n。
1和2变成\(n+1\),\(n+2\)；4和5变成\(n+3\),\(n+4\)
\(3k+1,3k+2\)变成\(n+2k+1,n+2k+2\)
用代码模拟（详见课本）；还可以换成方法加速
\(D_0^{(q)} = 1\)；\(D_n^{(q)} = \lceil \frac{q}{q-1} D_{n-1}^{(q)} \rceil\)，\(n > 0\)
\(J_q(n) = qn+1 - D_k^{(q)}\)，\(k\)是最大的使得答案不是负数的值
\(x \mod{0} = x\)
\(c (x \mod{y}) = (cx) \mod{(cy)}\)
\(n = \lfloor \frac{n}{m} \rfloor + \lfloor \frac{n + 1}{m} \rfloor + ... \lfloor \frac{n + m - 1}{m} \rfloor\)
\(n = \lceil\frac{n}{m} \rceil + \lceil \frac{n - 1}{m} \rceil + ... \lceil\frac{n - m + 1}{m} \rceil\)
\(\lfloor mx \rfloor = \lfloor x \rfloor + \lfloor x + \frac{1}{m} \rfloor + ... \lfloor x + \frac{m - 1}{m} \rfloor\)
\(\sum_{0 \le k < n} \lfloor \sqrt{k} \rfloor\)
method1 : \(\sum_{m = 1}^{\sqrt{n}} ((m+1)^2 - m^2) m\)
method2 : \(\sum_{m=1}^{\sqrt{n}} n - m^2\)，线性性质
设\(\alpha\)是无理数，则\(\{n\alpha\}\)在\(n->\infty\)时在[0,1)之间是一致分布的
\(\sum_{0 \le k < m} \lfloor \frac{nk + x}{m} \rfloor\)
原式\(= \sum_{0 \le k < m} \lfloor \frac{x + nk~mod~m}{m} \rfloor + \frac{kn}{m} - \frac{kn~mod~m}{m}\).
第二部分是个等差数列，\(\frac{(m-1)n}{2}\)
令\(d = \gcd(n,m)\)，则\(kn~mod~m\)会遍历\(0,d,2d,...m-d\)。每个数出现\(d\)次。
第三部分也是等差数列，\(- \frac{m-d}{2}\)
第一部分：\(d*(\lfloor \frac{x}{m} \rfloor+ \lfloor \frac{x+d}{m} \rfloor + .... + \lfloor \frac{x+m-d}{m} \rfloor) = d \lfloor \frac{x}{d}\rfloor\)
发现将\(n,m\)意义对调，答案不变。
素数有无穷多个
\(M = 2 \times 3 \times 5 \times .... \times P_n + 1\)，与\(P_1,...,P_n\)全部互质，又多出一个“质数”（事实上不一定是质数）
\(e_n = e_1 e_2 ... e_{n-1} + 1 = e_{n-1}^2 - e_{n-1} + 1\)
梅森数
质数密度
偶数比完全平方数更“稠密”，\(1-n\)有\(\frac{n}{2}\)个偶数；有\(\sqrt{n}\)个完全平方数。
$P_n $ ~ \(n \ln n\)；\(\pi(x)\) ~ \(\frac{x}{\ln x}\)；故质数个数比偶数少，比完全平方数多。
阶乘以指数方式增长：斯特林公式
\(\epsilon_p(n!) = \sum_{k \ge 1} \lfloor \frac{n}{p^k} \rfloor \le \frac{n}{p-1}\)
素数有无穷个的另一种证明：
\(p^{\epsilon_{p}(n!)} \le p^{n/(p-1)} \le 2^n\)
一个质数只能对\(n!\)产生\(2^n\)的贡献，如果质数个数有限，取\(n\)足够大就会产生矛盾
用于构造所有\(m \perp n\)的非负分数
构造方式
第一层只有\(\frac{0}{1}\)和\(\frac{1}{0}\)
第\(k+1\)层的分数构成 为 第\(k\)层的所有分数 加上 第\(k\)层相邻两个分数，分子和分母分别相加得到
性质
每一层的每对相邻的分数都满足\(m‘n - mn‘ = 1\)
为什么\(\frac{n+n‘}{m+m‘}\)是最简分数？
是否会重复出现分数？
是否有分数遗漏？
不存在的，推导可证明：\(a+b \ge m‘+n‘+m+n\). 每一步右式都会增加，在\(a+b\)步以内就可以找到解。
该式说明：\(\frac{m‘+m‘}{m+n}\)是[\(\frac{m}{n}\),\(\frac{m‘}{n‘}\)]之间分子加分母和最小的分数？？？这可离不开第一条性质！
应用
分数定位
用\(2 \times 2\)的矩阵存下每个分数的左右祖先，构造矩阵\(L\)和\(R\)。到左儿子则右乘\(L\)，右儿子则右乘\(R\).
法一：每次右乘一个\(L,R\)，判断大小。
法二：利用左乘。如果分子大，说明左乘了\(R\)，不然左乘了\(L\)。可以用倍增定位。\(O(\log n)\).
无理数定位
用SB树逼近和二分逼近效果差不多
if a < 1 then
output(L)
a = a/(1-a)
else
output(R)
a = a - 1
拓展：Farey级数
阶为\(N\)的法里级数为\(F_N\)，它由所有分母不超过\(N\)的最简分数组成。
\(F_N\)构造：从\(F_{N-1}\)继承，在\(F_{N-1}\)中相邻\(\frac{m}{n}\)和\(\frac{m‘}{n‘}\)，满足\(n+n‘=N\)的中间，加入分母为N的数。
\(2^{2n} - 1\)是3的倍数，因为\(2^2 \pmod{3} = 1\)
$ad \equiv bd \pmod{md} $ 等价于 \(a \equiv b \pmod{m}\).
\(ad \equiv bd \pmod{m}\)等价于\(a \equiv b \pmod{\frac{m}{\gcd(m,d)}}\).因为剩下的因子可以用逆元除掉。
\(a \equiv b \pmod{m}\)且\(a \equiv b \pmod{n}\)，则\(a \equiv b \pmod{lcm(n,m)}\).因为\(a-b\)既是n的倍数也是m的倍数
剩余系\(Res(x) = (x \mod m_1, \cdots,x \mod m_r)\)，\(m_i \perp m_j\).
每个分量上可以独立地进行运算，相当于高精度
例子：计算大矩阵的行列式，选取若干质数，除法变成逆元；最后CRT合并起来！
CRT
求\(x^2 \equiv 1 \pmod{m}\)解的个数
将\(m\)分解成若干个\(p^k\)，改写成\((x-1)(x+1) \equiv 0 \pmod{p^k}\).
当\(p \ne 2\)时，只有两个解1和p-1
当\(p=2\)时，若\(k=1\)解为1；\(k=2\)时解为1,3；\(k > 2\)时，\(x-1\)和\(x+1\)可以都是2的倍数，但是不可能都是4的部分，所以其中一个要是\(2^{k-1}\)的倍数。所以有4个解。
设\(r\)为质因子个数，答案为\(2^{r - [2|m]+[4|m]+[8|m]}\).
\(0, n, 2n, 3n,....,(m-1)n \pmod{m}\)为\(0,d,2d,...,m-d\)重复d遍；\(d = \gcd(n,m)\)
费马大定理：\(a^n + b^n = c^n\)在\(n > 2\)时没有正整数解
费马小定理：\(n^{p-1} \equiv 1 \pmod{p}\),\(n \perp p\)
Miller_Rabin：验证\(2^{32}+1\)是不是质数？
威尔逊定理：\(n\)是质数时，\((n-1)! \equiv -1 \pmod{n}\)
欧拉定理：\(n^{\varphi(m)} \equiv 1 \pmod{m}\)，\(n \perp m\)
莫比乌斯反演：\(g = f * 1\)等价于\(f = g*\mu\)
积性的传递性
\(g(m) = \sum_{d|m} f(d)\)
左右任何一边是积性函数，都可以推出剩下一边是积性函数。
杜教筛：求\(\Phi(x) = \sum_{1 \le k \le x} \phi(k)\)
\(\sum_{d \ge 1} \Phi(\frac{x}{d}) = \frac{x(x+1)}{2}\)；考虑所有\(0 \le m < n \le x\)的分数，d为分子和分母的\(\gcd\).
预处理小的\(\Phi(m)\)，分块递归求解，时间复杂度\(O(n^{\frac{2}{3}})\).
Polya经典题：求解长度为\(m\)，颜色数为\(n\)的不同项链个数
定义（此定义和之前的不一样）
当整数\(k < 0\)，\(\binom{n}{m} = 0\)，否则\(\binom{n}{m} = \frac{n^{\underline{m}}}{m!}\)
当不是整数时，可以用广义阶乘，取极限；如\(\binom{\frac{1}{2}}{n}\)
性质
\(\binom{-1}{k} = (-1)^k\)
当\(n < 0\)时，\(\binom{n}{n} = 0\)
当\(n<0\)时，不满足对称性\(\binom{n}{k} = \binom{n}{n-k}\)
由加法公式，\(\binom{r}{k} = \binom{r-1}{k-1} + \binom{r-1}{k}\)；由此可以拓展出\(r<0\)的情况。
恒等式
吸收恒等式：\(\binom{r}{k} = \frac{r}{k} \binom{r-1}{k-1}\)；\(k \binom{r}{k} = r \binom{r-1}{k-1}\)
对角线求和：\(\sum_{k \le n} \binom{r+k}{k} = \binom{r+n+1}{n}\)
上指标求和：\(\sum_{0 \le k \le n} \binom{k}{m} = \binom{n+1}{m+1}\)
二项式定理：\((x+y)^r = \sum_{k} \binom{r}{k} x^k y^{r-k}\)
上指标反转：\(\binom{r}{k} = (-1)^k \binom{k-r-1}{k}\)，当\(r\)是负数时可以用这种方法快速求解！！！
同行交错和：\(\sum_{k \le m} \binom{r}{k} (-1)^k = \sum_{k \le m} \binom{k-r-1}{l} = \binom{-r}{m} = (-1)^m \binom{r-1}{m}\)
双选恒等式：\(\binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}\)
范德蒙卷积：\(\sum_{k} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}\)，表5-3有多种形式，可以查表！
\(\sum_{k} \binom{m}{k} / \binom{n}{k} = \frac{n+1}{n+1-m}\)，双选恒等式
\(\sum_{k} k \binom{m-k-1}{m-n-1}/ \binom{m}{n} = \frac{n}{m-n+1}\)，用吸收恒等式
\(Q_n = \sum_{k \le 2^n} \binom{2^n - k}{k} (-1)^k\)，递推式，找规律，有循环节
\(\sum_k k \binom{m-k-1}{m-n-1}\)，把\(k\)写成\(\binom{k}{1}\)，用范德蒙卷积
\(\sum_{k} \binom{n}{k} \binom{s}{k} k = s \binom{n+s-1}{n-1}\)，用吸收恒等式，再范德蒙卷积
\(\sum_{k} \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{k+1}\)，先用双选恒等式，把\(2k\)去掉；再用吸收恒等式， 把\(\frac{1}{k+1}\)拿掉；然后上指标翻转，最后范德蒙卷积
问题七和问题八用和式代替一个组合数，技巧性太强；不如用后面的超几何
取一半
\(r^{\underline{k}} (r - \frac{1}{2})^{\underline{k}} = (2r)^{\underline{2k}} / 2^{2k}\)
由此可以推出：\(\binom{- \frac{1}{2}}{n} = (\frac{-1}{4})^n \binom{2n}{n}\)
高阶差分
\(\Delta f(x) = f(x+1) - f(x)\)；\(\Delta^n f(x) = \sum_{k} \binom{n}{k} (-1)^{n-k} f(x+k)\)
多项式可以用斯特林数改写成下降幂多项式，稍作修改可以写成牛顿级数：
\(f(x) = \sum_d c_d \binom{x}{d}\)，牛顿级数的求导非常方便；书上还写着一种\(O(n^2)\)的求牛顿级数系数的方法。
\(\sum_k \binom{n}{k} (-1)^k (a_0 + a_1k + ... + a_n k^n) = (-1)^n n! a_n\)
反演
\(g(n) = \sum_{k} (-1)^k \binom{n}{k} f(k)\)等价于\(f(n) = \sum_{k} (-1)^k \binom{n}{k} g(k)\)
二项式反演：\(g(n) = \sum_{k} \binom{n}{k} f(k)\)等价于\(f(n) = \sum_{k} (-1)^{n-k} \binom{n}{k} g(k)\)
重排公式：\(D(n) = n! \sum_k \frac{(-1)^k}{k!}\)；\(D(n) = \lfloor \frac{n!}{e} + \frac{1}{2} \rfloor + [n == 0]\)
\((1+z)^r (1+z)^s = (1+z)^{r+s}\)，该式子可以直接证明范德蒙恒等式
\((1-z)^r (1+z)^r = (1-z^2)^r\)；\(\sum_k \binom{r}{k} \binom{r}{n-k} (-1)^k = (-1)^{n/2} \binom{r}{n/2}\)
\(\frac{1}{(1-z)^{n+1}} = \sum_{k \ge 0} \binom{n+k}{n} z^k\)；\(\frac{z^n}{(1-z)^{n+1}} = \sum_{k \ge 0} \binom{k}{n} z^k\)
乘上\(\frac{1}{1-z}\)相当于做前缀和
广义部分待补
定义：\(F(a_1...a_m;b_1...b_n;z) = \sum_{k \ge 0} \frac{\prod a_i^{\bar{k}} z^k}{\prod b_i^{\bar{k}} k!}\)
转化：\(\frac{t_{k+1}}{t_k}\)是一个关于\(k\)的有理函数，分子作为上参数，分母作为下参数
广义阶乘和\(\Gamma\)函数用于解释退化的情况
查表：\(F(a,b;c;1)\)和\(F(a,b,-n;c,a+b-c-n+1;1)\)，SAA恒等式
超几何函数通用解法就是查表，本章介绍几种技巧拓展表库
求导，移位：
\(\frac{d}{dz} F(ai;bi;z) = \frac{a_1...a_m}{b_1...b_n} F(a_i+1;b_i+1;z)\)
\((\vartheta + a_1) F(a_1,...a_m;b_1...b_n;z) = a_1 F(a1+1,a_2,...,a_m;b_1...b_n;z)\)
\((\vartheta + b_1 -1) F(a_1,...a_m;b_1...b_n;z) = (b_1 - 1) F(a1,a_2,...,a_m;b_1-1,b_2...b_n;z)\)
\(\vartheta\)为\(z \frac{d}{dz}\)操作
这个技巧可以用于解微分方程
利用差分法，试图找出函数满足\(t_k = T_{k+1} - T_{k}\)，从而可以求解\(\sum_{0 \le k \le n} t_k\)。
\(Gosper\)算法
找出\(p(k),r(k),q(k)\)，满足\(\frac{t_{k+1}}{t_k} = \frac{p(k+1)}{p(k)} \frac{q(k)}{r(k+1)}\)
求解\(s(k)\)，满足\(p(k) = q(k) s(k+1) - r(k) s(k)\)
得到\(T(k) = \frac{r(k)s(k)t(k)}{p(k)}\)
机械求和法是个非常繁琐的算法，用于求解给定n，对\(k\)从\(0\)到\(\infty\)求和。不能求\(k\)的部分和
思路是定义新的函数，应用\(Gosper\)算法，得到\(S_n\)的递推式。
详见书上的例子。
第一类斯特林数\([^n_k]\)，第二类斯特林数\(\{ ^n_k \}\).
\(\{^n_k\} = k \{^{n-1}_k\} + \{^{n-1}_{k-1}\}\)
\([^n_k] = (n-1)[^{n-1}_k] + [^{n-1}_{k-1}]\)
\([^n_k] \ge \{^n_k\}\)，等号成立，当且仅当\(k=n-1\)或\(k=n\)
\(\sum_{k=0}^n [^n_k] = n!\)
幂之间转换（均可用归纳法证明）
\(x^n = \sum_k \{^n_k\} x^{\underline{k}}\)
\(x^{\bar{n}} = \sum_k [^n_k] x^k\)
\(x^{\underline{n}} = (-1)^n (-x)^{\bar{n}}\)
\(x^n = \sum_k \{^n_k\} (-1)^{n-k} x^{\bar{k}}\)
\(x^{\underline{n}} = \sum_k [^n_k] (-1)^{n-k} x^k\)
反转公式（应用两次幂转换公式即可）
\(\sum_k [^n_k] \{^k_m\} (-1)^{n-k} = [m=n]\)
\(\sum_k \{^n_k\} [^k_m] (-1)^{n-k} = [m = n]\)
应用加法原则拓展至负数，有\([^n_k] = \{^{-k}_{-n}\}\)
书上还有一大堆用于前缀和、卷积的恒等式，可用于查表。
\(<^n_k>\)表示长度为\(n\)的排列\(\pi\)，有\(k\)个位置满足\(\pi_j < \pi_{j+1}\)，即升高位置
\(<^n_k> = <^n_{n-1-k}>\)
\(<^n_k> = (k+1) <^{n-1}_{k}> + (n-k)<^{n-1}_{k-1}>\)
\(x^n = \sum_k <^n_k> \binom{x+k}{n}\)，天呐，这个式子的组合意义是啥！！！
书上还有一些奇奇怪怪的恒等式哦！还有一个通项式
二阶欧拉数：\(2n\)个数，\(k\)个上升，且每对\(x\)之间其他数都要大于\(x\)
\(<<^n_k>> = (k+1) <<^{n-1}_{k}>> + (2n-1-k)<<^{n-1}_{k-1}>>\)
\(\sum_k <<^n_k>> = \frac{(2n)^{\underline{n}}}{2^n}\)
斯特林多项式（由书上的恒等式推出）
\(\sigma_n(x) = [^x_{x-n}] / (x(x-1) \cdots (x-n))\)，其中\(\sigma_n(x)\)的次数为\(n-1\)
斯特林多项式可以由二阶欧拉数给出，于是可以处理系数为斯特林数的的生成函数的卷积。
\(H_n = \sum_{k=1}^n \frac{1}{k}\)
例题：
\([^{n+1}_2] = n[^n_2]+[^n_1] = n[^n_2]+(n-1)!\)
两边除以\(n!\)，求递归式：\([^{n+1}_2] = n! H_n\)
\(r\)次调和数：\(H^{(r)}_n = \sum_{k=1}^n \frac{1}{k^r}\)
\(\ln(\frac{k}{k-1}) = - ln(\frac{k-1}{k}) = \frac{1}{k} + \frac{1}{2k^2} + \frac{1}{3k^3}+ \cdots\)
对\(k\)从2-n求和：\(\ln n -\ln 1 = (H_n - 1) + \frac{1}{2} (H^{(2)}_n - 1) - .....\)
移项后，可以估计\(H_n - \ln n\)的值，记为欧拉常数\(\gamma\)
\(\sum_{0 \le k < n} \binom{k}{m} H_k\)
利用分部求和法，\(u(k) = H_k\)，\(\Delta v(k) = \binom{k+1}{m+1} - \binom{k}{m+1} = \binom{k}{m}\)
利用吸入恒等式
\(S_n = \sum_{1 \le k \le n} \frac{H_k}{k}\)
\(S_n = \sum_{1 \le j \le k \le n} \frac{1}{j*k} = \frac{1}{2} ( (\sum_{1 \le k \le n} \frac{1}{k})^2 + \sum_{1 \le k \le } \frac{1}{k^2} )\)
第二章的技巧
\(U_n = \sum_{k \ge 1} \binom{n}{k} \frac{(-1)^{k-1}}{k} (n-k)^n\)
求解幂和数
\(S_m(n) = \sum_{k=0}^{n-1} k^m = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k} B_k n^{m+1-k}\)
\(\sum_{j=0}^m \binom{m+1}{j} B_j = [m = 0]\)
可以用扰动法+归纳法证明
生成函数的定义：\(\frac{z}{e^z-1} = \sum_{n \ge 0} B_n \frac{z^n}{n!}\)
用伯努利数为系数表示三角函数
伯努利数和斯特林数的关系
\(S_m(n) = \sum_{j \ge 0} \{^m_j\} \frac{1}{j+1} \sum_{k \ge 0} (-1)^{j+1-k} [^{j+1}_k] n^k\)
由此建立恒等式
恒等式
\(F_{n+k} = F_k F_{n+1} + F_{k-1} F_n\)；考虑走楼梯
\(F_{2n} = F_n F_{n+1} F_n F_{n-1}\)；从而\(F_{2n}\)是\(F_n\)的倍数，归纳可得\(F_{kn}\) 是\(F_n\)的倍数
\(\gcd(F_m,F_n) = F_{\gcd(m,n)}\)；由上式推出
\(\sum_{k=0}^n F_k = F_{n+2} - 1\)；归纳即可
\(\sum_{k=1}^n F_k^2 = \sum_k F_k (F_{k+1} - F_{k-1}) = F_{n+1} F_n\)；裂项相消
\(F_n = \frac{1}{\sqrt{5}}(\phi^n - \hat{\phi^n})\)；其中\(\phi = \frac{\sqrt{5} + 1}{2}\)，为黄金分割
\(F_{n+1} = \sum_{k=0}^n \binom{n-k}{k}\)
斐波那契数系
\(j >> k\) 等价于\(j \ge k +２\)
每个整数都有唯一的表示：\(n = F_{k_1} + F_{k_2} + ..... + F_{k_r}\)
\(n = (b_mb_{m-1}\cdots b_2)_F\)，因为\(b_1=b_2=1\)，从2开始表示唯一
能表示的最大值为\(F_{m+2} - 2\)
斐波那契奇数是指表示中，最后一位是1的数；偶数类似。
定义
\(K() = 1\)
\(K(x_1) = x_1\)
$K_n(x_1,\cdots,x_n) = K_{n-1}(x_1,\cdots, x_{n-1}) x_n + K_{n-2}(x_1,\cdots,x_{n-2}) $
性质
\(K_n(1,1,...,1) = F_{n+1}\)
摩尔斯码：相当于可以放一些长度为2的多米诺骨牌；如果\(x_i\)不在，必然有相邻的\(x_{i+1}\)或者\(x_{i-1}\)与之对应
\(K_n(z,z, \cdots, z) = \sum_{k=0}^{n} \binom{n-k}{k} z^{n-2k}\)
\(K_n(x_n,...,x_1) = K_n(x_1,...,x_n)\)
\(K (x_1,...x_m,x_{m+1},...x_{m+n})= K(x_1,...x_m) K(x_{m+1},...,x_{m+n}) + K(x_1,...,x_{m-1}) K(x_{m+2},...x_{m+n})\)
连项式与连分数
\(a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a3}}} = \frac{K(a_0,a_1,a_2,..,a_3)}{K(a_1,a_2,a_3,)}\)；归纳之
\(\frac{K(a_0,a_1,a_2,a_3+1/a_4)}{K(a_1,a_2,a_3+1/a_4)} = \frac{K(a_0,a_1,a_2,a_3,a_4)}{K(a_1,a_2,a_3,a_4)}\)；将连分数最后一位变化
连项式与Stern-Brocot树
假设一个分数为\(R^{a_0},L^{a_1},R^{a_2},L^{a_3} ... R^{a_{n-2}}L^{a_{n-1}}\)
则\(F(R^{a_0}L^{a_1}R^{a_2}L^{a_3} ... R^{a_{n-2}}L^{a_{n-1}}) = \frac{K(a_0,a_1,...a_{n-1},1)}{K(a+1....a_{n-1},1)}\)
由此可以在连分数和SB树之间快速转换
用多米诺骨牌铺3*n矩形
\(U_n\)表示\(3 \times n\)的方案，\(V_n\)表示\(3 \times n\)缺一角的方案
\(U_n = 2 V_{n-1} + U_{n-2} + [n == 0]\)
\(V_n = U_{n-1} + V_{n-2}\)
写成生成函数
\(U(x) = 2x V(x) + x^2 U(x) + 1\)
\(V(x) = x U(x) + x^2 V(x)\)
求解
\(V(x) = \frac{x}{1-x^2} U(x)\)
$U(x) = 1 + \frac{2x^2}{1-x^2} U(x) + x^2 U(x) $
若将\(U(x)\)的封闭形式展开，可以得到\(U_n\)的封闭形式；最后通过组合式的恒等式还可以化简
换零钱
和OI经典题“食物”类似
有无限个价值为\(m\)的硬币，其生成函数为\(1+x^m+x^{2m}+.....=\frac{1}{1-x^m}\)
划分数
运算
收敛性不作要求，因为变量\(z\)仅仅表示一个特征，我们只在乎\(z^n\)前的系数
左移时，要把低位“减掉”，再除以\(z^m\)
\(G(cz) = \sum_n g_n c^n z^n\)；\(G(z^m) = \sum_n g_n z^{nm}\)
求导；求导+右移（每一位乘上\(n\)）；积分；左移+积分（每一位除以n）
卷积
前缀和：乘上\(\frac{1}{1-z}\)
常见生成函数
<1,-1,1,-1,1,-1,1,-1,......>；\(\frac{1}{1+z}\)
<1,0,1,0,1,0,1,0,.......>; \(\frac{1}{1-z^2}\)
<1,2,4,8,16,....>;\(\frac{1}{1-2z}\)
<1,4,6,4,1,0,0,...>; \((1+z)^4\)
<1,c,\(\binom{c+1}{2}\),\(\binom{c+2}{3}\),.....>；\(\frac{1}{(1-z)^c}\)
<0,1,1/2,1/3,1/4,.....>；\(\ln \frac{1}{1-z}\)；积分
<0,1,-1/2,1/3,-1/4,....>; \(\ln(1+z)\)；积分
<1,1,1/2,1/6,1/24,.....>;\(e^z\)
提取
用\(\frac{G(z) + G(-z)}{2}\)提取偶数项
用\(\frac{G(z) - G(-z)}{2}\)提取奇数项
再探斐波那契数
\(g_n = g_{n-1} + g_{n-2}+[n=1]\)；写递归式时要注意写出边界项
\(G(z) = z G(z) + z^2 G(z) + z\) ；可推出\(G(z) = \frac{z}{1-z-z^2}\)
求解部分分式：\(R(z) = \frac{P(z)}{Q(z)}\)
\(\frac{a}{(1-pz)^{m+1}} = \sum_{n \ge 0} \binom{m+n}{m} a p^n z^n\)
目标将\(R(z)\)转化成：\(\sum_i \frac{a_i}{(1-p_i z)^{m_i + 1}}\)；就可以得到\(g_n\)的封闭形式
假设\(Q(z) = q_0 + q_1 z + .... + q_m z^m\)，则令\(Q^R(z) = q_0 z^m + q_1 z^{m-1} + .... q_m\)
求解\(Q^R\)的根，即\(Q^R(z) = q_0 (z-p_1)...(z-p_m)\)，则\(Q(z) = q_0 (1-p_1 z)...(1-p_mz)\)
既然求出分母的根，然后将其拆成\(\frac{..}{1-p_1z}+....\frac{..}{1-p_mz}\)
当根互不相同时，可以用高斯消元？或者用书上的定理。
事实上，求解部分分式的过程就是解特征方程。
带几分随机的递归式
\(g_n = g_{n-1} + 2g_{n-2}+(-1)^n[n \ge 0] + [n=1]\)
解得\(G(z)=\frac{1+z+z^2}{(1-2z)(1+z)^2}\)；用书上另一个公式来对有重根的分母进行部分分式。
互相递归的数列（和解方程类似）
换零钱封闭形式（用于OI题，类似于Code Chef的CHANGE）
发散级数（超几何解微分方程）
完全返回的递归式
求解扇形的生成树数量
分析最后一个顶点的连边，可得
前缀和用乘上\(\frac{1}{1-z}\)表示：
求部分分式，得\(f_n = F_{2n}\)，即偶数位斐波那契数列
表7-3给出各种系数为特殊数的生成函数，包括斯特林数、欧拉数、伯努利数
\(\frac{1}{(1-z)^{m+1}} \ln \frac{1}{1-z} = \sum_{n \ge 0} (H_{m+n}- H_m) \binom{m+n}{n} z^n\)
\(\frac{1}{(1-z)^{x+1} } = \sum_n \binom{x+n}{n} z^n\)
左边：\((1-z)^{-x-1}=e^{(x+1)\ln(1/(1-z))}\)，微分后，为\(\frac{1}{(1-z)^{m+1}} \ln \frac{1}{1-z}\)
右边：\(\binom{x+n}{n}\)微分后，为\((\frac{1}{x+1} + \frac{1}{x+2} .... \frac{1}{x+n})\),等于\(H_{x+n} - H_x\)
对复杂的乘积求微分，通常将原式保留，并提取出系数，比直接写成和式方便。
特殊情况：\(\frac{1}{1-z} \ln \frac{1}{1-z} = \sum_n H_n z^n\)
斐波那契卷积
调和卷积
\(T_{m,n} = \sum_{0 \le k < n} \binom{k}{m} \frac{1}{n-k}\)
因\(\sum_{n \ge 0} \binom{n}{m} z^n = \frac{z^m}{(1-z)^{m+1}}\)，且\(\sum_{n > 0} \frac{z^n}{n} = \ln \frac{1}{1-z}\)
\(T_{m,n} = [z^n]\frac{z^m}{(1-z)^{m+1}} \ln \frac{1}{1-z} = (H_n - H_m) \binom{n}{n-m}\)
卷积的卷积
之前的扇形生成树个数，可以认为有一些链，需要从根向他们连边。
\(f_n = \sum_{m > 0} \sum_{k_1+...+k_m=n} k_1k_2...k_m\)
即\(F(z) = G(z) + G(z)^2 + G(z)^3 + .... = \frac{G(z)}{1-G(z)}\)
卷积的递归式
卡特兰数的括号解释：\(C_n = \sum_k C_k C_{n-1-k} + [n = 0]\)
\(C(z) = z C^2(z) + 1\)，解得\(C(z) = \frac{1 (+/-) \sqrt{1-4z}}{2z}\)；加或减
当取+号时，\(C(0)\)是无穷，与事实不符；所以为减
用广义二项式展开\(\sqrt{1-4z}\)，可以得到卡特兰数公式：\(C_n = \binom{2n}{n} \frac{1}{n+1}\)
拓展内容
\(\hat{G}(z) = \sum_{n \ge 0} g_n \frac{z^n}{n!}\)
\(e^z\)是<1,1,1,1,1.....>的EGF
\(e^{kz}\)是<1,k,\(k^2\),.....>的EGF
运算
求导、积分即为左移和右移
乘上\(z\)，则右移后每一位乘上\(n\)
二项卷积：\(\hat{F} (z) \hat{G} (z)\)等价于\(F(z) G(z)\)时乘上组合数系数
应用：用伯努利数表示\(\sum_{k = 0}^n k^m\)
应用：完全图的生成树个数为\(n^{n-2}\)
考虑\(n-1\)个点的图，选出一个生成森林，令\(n\)号点向所有联通块连一条边；一个大小为\(k\)的连通块有\(k\)种连边方式。
\(t_n = \sum_{m> 0} \frac{1}{m!} \sum_{k_1+k_2+...k_m = n-1} \binom{n-1}{k_1,k_2,...,k_m} k_1k_2...k_m t_{k_1} t_{k_2}....t_{k_m}\)
令\(u_n = n t_n\)
\(\frac{u_n}{n!} = \sum_{m > 0} \frac{1}{m!} \sum_{k_1+k_2+...k_m = n-1} \frac{u_{k_1}}{k_1!}...\frac{u_{k_m}}{k_m!}\)
用广义指数函数，\(\hat{U}(z) = z e^{\hat{U}(z)}\)
\(\bar{G} (z) = \sum_{n \ge 1} \frac{g_n}{n^z}\)
乘积：\(h_n = \sum_{d | n} f_d g_{n/d}\)
当数列\(<g_1,g_2,....>\)是积性函数时：
\(\bar{G}(z) = \prod_{\text{p是质数}} (1+\frac{g_p}{p^z} + \frac{g_{p^2}}{p^{2z}}+......)\)
书上有一些例子
第八章在《概率统计》一书中有详细介绍；第九章在数学分析或高等数学中有详细介绍。
原文：https://www.cnblogs.com/sunyaofeng/p/10048859.html