具体数学(Concrete Math) 读书笔记

大家好，欢迎来到IT知识分享网。

《具体数学》果真十分“具体”，远没有数学分析、高等代数那么“抽象”。这里记录了我在阅读这本书时所采撷的“心动瞬间”——这些数学公式真是令人心动——可以把这篇文章当做检索目录，遇到问题时：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\)刀，最多把披萨分成几块？

  • 只要所有直线都不平行，第\(i\)条直线可以和之前\(i-1\)条直线相交，从而F加\(i\).

• \(n\)条折线呢？

  • 每一对折线可以产生\(4\)个顶点，自己本身可以产生1个，初始有1个。

  • \(4 \frac{n(n-1)}{2} + n + 1 = 2n^2 – n + 1\)

• \(n\)个120°三叉呢？

  • 每对可以产生3个，自己本身可以多2个，初始有1个。

约瑟夫问题

• 每隔2个干掉一个？

  • 递归，第一轮会把所有偶数位置都干掉

    • \(J(2n) = 2J(n) – 1\)

    • \(J(2n + 1) = 2 J(n) + 1\)

  • 对递归式打表+数学归纳

    • \(J(2^m + l) = 2l + 1\)，\(0 \le l < 2^m\)

  • 用二进制形式表示？

    • \(J(n)\)相当于把\(n\)在二进制下循环左移了一位。

  • 一些性质

    • \(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 + (n+1)2^{n+1} = \sum_{k=0}^{n} (k+1) 2^{k+1} = 2S_n + (2^{n+2} – 2)\)；化简即可

• 拓展：\(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\)

• 连续情况下的切比雪夫不等式

  • \((\int_a^b f(x) dx) (\int_a^b g(x) dx) \le (b-a) (\int_a^b f(x)g(x)dx)\); 若\(f(x),g(x)\)不减

• 例题：\(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\)的解法

• 打表+猜测答案+数学归纳

• 扰动法

  • 需要用\(\sum_{k=1}^{n} k^3\)来扰动.

• 成套方法

  • \(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\)？？？

  • 否；当\(m^2 < x < m^2 + 1\)时，即\(x\)不是整数，且\(\sqrt{\lfloor x \rfloor}\)是整数时，为反例

• 在\(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\)

  • 归纳法，需要证明\(K_n \ge n + 1\)

• 约瑟夫问题新解（以 \(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\)是最大的使得答案不是负数的值

mod：二元运算

• \(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\)意义对调，答案不变。

    • 本质上这是在数坐标轴在一条直线下方有多少点，\(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\)

    • 封闭形式：\(e_n = \lfloor E^{2^n} + \frac{1}{2} \rfloor\),\(E = 1.264\)

• 梅森数

  • \(2^p – 1\)，\(p\)是质数。但并不是所有梅森数都是素数。

• 质数密度

  • 偶数比完全平方数更“稠密”，\(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=2\)时，\(\epsilon_2(n!) = n – v_2(n)\)，\(v_2(n)\)为二进制上1的个数

• 素数有无穷个的另一种证明：

  • \(p^{\epsilon_{p}(n!)} \le p^{n/(p-1)} \le 2^n\)

  • 一个质数只能对\(n!\)产生\(2^n\)的贡献，如果质数个数有限，取\(n\)足够大就会产生矛盾

互素（Stern-Brocot树）

• 用于构造所有\(m \perp n\)的非负分数

• 构造方式

  • 第一层只有\(\frac{0}{1}\)和\(\frac{1}{0}\)

  • 第\(k+1\)层的分数构成 为 第\(k\)层的所有分数 加上 第\(k\)层相邻两个分数，分子和分母分别相加得到

    • \(\frac{m}{n},\frac{m’}{n’} -> \frac{m+m’}{n+n’}\)

• 性质

  • 每一层的每对相邻的分数都满足\(m’n – mn’ = 1\)

    • 归纳法，第一层是对的；每次\(\frac{m}{n},\frac{m’}{n’}\)会新建\(\frac{m+m’}{n+n’}\)，分别验证。

  • 为什么\(\frac{n+n’}{m+m’}\)是最简分数？

    • 利用拓展欧几里得，因为\(m’n – mn’ = 1\)，说明\(ax+by=1\)成立，所以\(\gcd=1\).

  • 是否会重复出现分数？

    • 不存在的，这是一棵严格的二叉搜索树。因为$ \frac{m}{n} < \frac{m+m’}{n+n’} < \frac{m’}{n}$.

  • 是否有分数遗漏？

    • 不存在的，推导可证明：\(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

  • 相当于要找到(1,0,0),(0,1,0),(0,0,1)这些分量对应的数；用拓展欧几里得求出逆元。

• 求\(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\)

  • 证明：\(n*2n*…..*(p-1)n \equiv (p-1)!\)

• Miller_Rabin：验证\(2^{32}+1\)是不是质数？

  • 若是质数，应用费马小定理：$3^{2{32}} \equiv 1 \pmod{2^{32}+1} $.矛盾

• 威尔逊定理：\(n\)是质数时，\((n-1)! \equiv -1 \pmod{n}\)

  • 除了1和\(n-1\)，其他数的逆元两两匹配，所以\((n-1)! \equiv n-1 \mod{n}\)

\(\varphi\)函数和\(\mu\)函数

• 欧拉定理：\(n^{\varphi(m)} \equiv 1 \pmod{m}\)，\(n \perp m\)

  • 拓展欧拉定理，处理\(n\)和\(m\)不互质的情况。

• 莫比乌斯反演：\(g = f * 1\)等价于\(f = g*\mu\)

  • 广义莫比乌斯反演：\(g(x) = \sum_{d \ge 1} f(x / d)\)等价于\(f(x) = \sum_{d \ge 1} \mu(d) g(x / d)\)

• 积性的传递性

  • \(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\)的不同项链个数

  • 考虑一种项链会被计算多次：\(\frac{1}{m} \sum_{d | m} \phi(d) n^{\frac{m}{d}}\)

二项式系数

基本恒等式

• 定义（此定义和之前的不一样）

  • 当整数\(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)\)

    • 本质就是令\(f'(n) = (-1)^n f(n)\)

  • 重排公式：\(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恒等式

超几何变换

• 超几何函数通用解法就是查表，本章介绍几种技巧拓展表库

  • 反射定律；习题25、26

• 求导，移位：

  • \(\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}\)

  • 发散，且\(\ln_n < H_n < \ln n+1\)

• 例题：

  • \([^{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\)

  • 将\((n-k)^n\)二项式展开，交换顺序，转化为高阶差分，利用恒等式；得\(U_n = n^n (H_n – 1)\)

伯努利数

• 求解幂和数

  • \(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!}\)

• 用伯努利数为系数表示三角函数

  • \(\tan z = \sum_{n \ge 0} (-1)^{n-1} 4^n (4^n – 1) B_{2n} \frac{z^{2n-1}}{(2n)!}\)

• 伯努利数和斯特林数的关系

  • \(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-x2} U(x) + x^2 U(x) $

  • 若将\(U(x)\)的封闭形式展开，可以得到\(U_n\)的封闭形式；最后通过组合式的恒等式还可以化简

• 换零钱

  • 和OI经典题“食物”类似

  • 有无限个价值为\(m\)的硬币，其生成函数为\(1+x^m+x^{2m}+…..=\frac{1}{1-x^m}\)

• 划分数

  • \(\frac{1}{(1-z)(1-z^2)(1-z^3)…..}\)的\(z^n\)前系数为\(n\)的划分数，意义为用无穷个1-n凑成\(n\)的方案数

基本策略

• 运算

  • 收敛性不作要求，因为变量\(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）

• 发散级数（超几何解微分方程）

• 完全返回的递归式

  • 求解扇形的生成树数量

  • 分析最后一个顶点的连边，可得

    • \(f_n = f_{n-1} + \sum_{k < n} f_k + [n > 0]\)

  • 前缀和用乘上\(\frac{1}{1-z}\)表示：

    • \(F(z) = z F(z) + F(z) \frac{z}{1-z} + \frac{z}{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\)

卷积

• 斐波那契卷积

  • \(\sum_{k=0}^n F_k F_{n-k}\)等价于\(F^2(x)[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}\)

• 拓展内容

  • RANEY公式、m-RANEY公式；非常美妙，可用于简化计数；

指数生成函数

• \(\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}\)

  • 黎曼函数\(\sum_{n \ge 1} \frac{1}{n^z}\) 就是<1,1,1,1….>的DGF

• 乘积：\(h_n = \sum_{d | n} f_d g_{n/d}\)

  • 因为莫比乌斯函数与<1,1,1,1,1>的狄里克雷卷积为1，所以它们互为逆

• 当数列\(<g_1,g_2,….>\)是积性函数时：

  • \(\bar{G}(z) = \prod_{\text{p是质数}} (1+\frac{g_p}{p^z} + \frac{g_{p^2}}{p^{2z}}+……)\)

  • 书上有一些例子

第八章在《概率统计》一书中有详细介绍；第九章在数学分析或高等数学中有详细介绍。