一些数学定理
_abcd_
·
·
算法·理论
组合数学
二项式定理
(x+y)^n = \sum\limits_{i=0}^n \binom{n}{i} x^i y^{n-i} \tag{1}
范德蒙德卷积
\binom{x+y}{n} = \sum\limits_{i=0}^n \binom{x}{i} \binom{y}{n-i} \tag{2}
-
令 x=y=n，则
\sum\limits_{i=0}^n \binom{n}{i}^2 = \sum\limits_{i=0}^n \binom{n}{i} \binom{n}{n-i} = \binom{2n}{n} \tag{3}
将 (1) 的两侧同时乘上 n!，则有
(x+y)^{\underline{n}} = \sum\limits_{i=0}^n x^{\underline{i}} y^{\underline{n-i}} \tag{4}
由于 (-x)^{\underline{n}} = (-1)^n x^{\overline{n}}，因此
(x+y)^{\overline{n}} = \sum\limits_{i=0}^n x^{\overline{i}} y^{\overline{n-i}} \tag{5}
多项式定理
将 (1) 进行扩展，有
(x_1 + x_2 + \dots + x_m)^n = \sum\limits_{(k_1, k_2, \dots, k_3)} \frac{n!}{k_1! k_2! \dots k_m!} x_1^{k_1} x_2^{k_2} \dots x_m^{k_m} \tag{6}
网格路径
在一个网格上，每次只能向上或向右走，设 L(n,m) 表示从 (0,0) 走到 (n,m) 的路径数，则
L(n,m) = \binom{n+m}{n}
枚举在第 k 行最大走到第几列，能得到
\binom{n+m}{n} = \sum\limits_{i=0}^m L(k,i) \times L(n-k-1,m-i) = \sum\limits_{i=0}^m \binom{k+i}{k} \binom{n-k-1+m-i}{n-k-1}
即
\sum\limits_{i=0} \binom{i}{a} \binom{n-i}{b} = \binom{n+1}{a+b+1} \tag{7}
斯特林数
有
x^n = \sum\limits_{i=0}^n {n \brace i} x^{\underline{i}} \tag{8}
x^{\overline{n}} = \sum\limits_{i=0}^n {n \brack i} x^i \tag{9}
将 (8) 和 (9) 结合，就有
x^{\underline{n}} = (-1)^n x^{\overline{n}} = (-1)^n \sum\limits_{i=0}^n {n \brack i} x^i = \sum\limits_{i=0}^n (-1)^{n-i} {n \brack i} x^i \tag{10}
二项式反演
f_n = \sum\limits_{i=0}^n \binom{n}{i} g_i \Rightarrow g_n = \sum\limits_{i=0}^n (-1)^{n-i} \binom{n}{i} f_i \tag{11}
类似的
f_n = \sum\limits_{i \ge n} \binom{i}{n} g_i \Rightarrow g_n = \sum\limits_{i \ge n} (-1)^{i-n} \binom{i}{n} f_i \tag{12}
\textbf{Example}
n^k = \sum\limits_{i=0}^k {k \brace i} \binom{n}{i} i!
令 k \ge n，则
n^k = \sum\limits_{i=0}^n {k \brace i} \binom{n}{i} i! \Rightarrow {k \brace n} n! = \sum\limits_{i=0}^n (-1)^{n-i} \binom{n}{i} i^k
即
{n \brace k} = \frac{1}{k!} \sum\limits_{i=0}^k (-1)^{k-i} \binom{k}{i} i^n \tag{13}
这就是第二类斯特林数的通项公式。
容斥原理
对于统计满足一些条件的情况数，设 S 为条件集合，f_T 表示不满足 T 的情况数
ans = \sum\limits_{T \subset S} (-1)^{|S|} f_T \tag{14}
如果有 \forall |T_1| = |T_2|, f_{T_1} = f_{T_2}，那么设 n = |S|, g_i = f_{T}(|T| = i)，则
ans = \sum\limits_{i=0}^n (-1)^i \binom{n}{i} g_i \tag{15}
\textbf{Example}
求 \varphi(n) 的通项公式，只需要对 n 的每个质因子进行容斥，设 P = \{ p \mid n \}，则
\varphi(n) = \sum\limits_{S \subset P} (-1)^{|S|} \sum\limits_{i=1}^n [\forall p \in S, p \mid i]
= \sum\limits_{S \subset P} (-1)^{|S|} \frac{n}{\prod\limits_{p \in S} p}
= n \sum\limits_{S \subset P} \prod\limits_{p \in S} - \frac{1}{p}
= n \prod\limits_{p \in P} 1 - \frac{1}{p} \tag{16}
\textbf{Example}
对不定方程 x_1 + x_2 + \dots + x_m = n 的非负整数解的个数，通过插板法可以得到答案为 \binom{n+m-1}{m-1}。而所有满足 \forall 1 \le i \le m, 0 \le x_i < a_i，则只需要枚举不满足条件的集合，就有
|\{ (x_1, x_2, \dots, x_m) \mid \sum\limits_{i=1}^m x_i = n, \forall 1 \le i \le m, x_i \in [0,a_i) \cap \mathbb{Z} \}|
= \sum\limits_{S \subset \{ 1,2,\dots, m \}} (-1)^{|S|} \binom{n - \sum\limits_{i \in S} a_i + m - 1}{m-1} \tag{17}
若 \forall 1 \le i \le m, a_i = k，则
|\{ (x_1, x_2, \dots, x_m) \mid \sum\limits_{i=1}^m x_i = n, \forall 1 \le i \le m, x_i \in [0,a_i) \cap \mathbb{Z} \}|
= \sum\limits_{i=0}^m (-1)^i \binom{m}{i} \binom{n-ik+m-1}{m-1} \tag{18}
令 k=1，则有 \forall 1 \le i \le m, x_i = 0，就能得到
\sum\limits_{i=0}^m (-1)^i \binom{m}{i} \binom{n+m-i-1}{m-1} = [n = 0] \tag{19}
类似的，考虑一个问题：给定 n 个数，从中选 k 个数，其中 m 个数必须选，则枚举有多少个数没选，就有
\sum\limits_{i=0}^m (-1)^i \binom{m}{i} \binom{n-i}{k} = \binom{n-m}{k-m} \tag{20}
\textbf{Example}
考虑一个有 2n 个座位的圆桌，其中有 n 对夫妻入座，问有多少种入座方式使得每一对夫妻都不相邻，则枚举有多少对夫妻相邻，就有
ans = \sum\limits_{i=0}^n (-1)^i \binom{n}{i} \binom{2n-i}{i} i! 2^i (2n-2i)!
= \sum\limits_{i=0}^n (-2)^i \binom{n}{i} (2n-i)! \tag{21}
子集反演
对 (11) 进行推广，能得到
f_S = \sum\limits_{S \subset T} g_T \Rightarrow g_S = \sum\limits_{S \subset T} (-1)^{|T| - |S|} f_T \tag{22}
类似的，有
f_S = \sum\limits_{T \subset S} g_T \Rightarrow g_S = \sum\limits_{T \subset S} (-1)^{|S| - |T|} f_T \tag{23}
\text{LGV} 引理
对于一张图 G=(V,E)，设起点集合 A 和终点集合 B，其中 |A| = |B| = n，设 \operatorname{Path}(u,v) 为从 u 到 v 的路径集合，则有
\sum\limits_{P \in S_n} (\operatorname{sign} P) \sum\limits_{\forall 1 \le i \le n, p_i \in \operatorname{Path}(A_i,B_{P_i})} [\forall 1 \le i,j \le n, i \ne j, p_i \cap p_j = \emptyset]
= \sum\limits_{P \in S_n} (\operatorname{sign} P) \prod\limits_{i=1}^n |\operatorname{Path}(A_i,B_{P_i})| \tag{24}
\text{Burnside} 引理
令群 G 作用于 X，而 M 为所有等价类，设 X_g 为 X 中所有在 g 的作用下不变的元素，则有
|M| = \frac{1}{|G|} \sum\limits_{g \in G} |X_g| \tag{25}
\textbf{Example}
有一个有 p 个珠子的项链，其中 p 为质数，现在将每个珠子都染上 n 种颜色，那么所有本质不同的染色方案数为
\frac{1}{p} \sum\limits_{i=1}^p n^{\gcd(i,p)} = \frac{(p-1)n + n^p}{p}
显然方案数是一个整数，因此
(p-1)n + n^p \equiv 0 \pmod{p}
即
n^p \equiv n \pmod{p} \tag{26}
也就是费马小定理。
\text{Polya} 定理
令群 G 作用于 S，设 M(N,S) 为所有用 N 中的颜色给 S 中的每个元素染色的方案中所有等价类，设 c(g) 为 S 在 g 的作用下的轮换个数，设 n = |N|，则有
|M(N,S)| = \frac{1}{|G|} \sum\limits_{g \in G} n^{c(g)}
\textbf{Example}
令 S = \{ 0, 1, \dots, m-1 \}, g^k : i \to i+k \bmod m，则
|M(N,S)| = \frac{1}{m} \sum\limits_{i=0}^{m-1} |N|^{\gcd(m,i)}
= \frac{1}{m} \sum\limits_{d \mid m} \varphi(\frac{m}{d}) n^d \tag{27}
\textbf{Example}
给定一个正方体，问有多少种染色方案。考虑分类讨论所有翻转方法和方案数以及其对应的轮换个数。
- 不变，1 \times 1，6。
- 以面为轴转 90 \degree，3 \times 2，3。
- 以面为轴转 180 \degree，3 \times 1，4。
- 以边为轴转 180 \degree，6 \times 1，3。
- 以点为轴转 120 \degree，4 \times 2，2
因此方案数为
n^6 + 6 n^3 + 3 n^4 + 6 n^3 + 8 n^2 = n^6 + 3 n^4 + 12 n^3 + 8 n^2
生成函数
一般性生成函数 (\text{OGF})
对于数列 \{ f_n \}，定义其 \text{OGF} 为 F(x) = \sum\limits_{i \ge 0} f_i x^i，并对 n \notin \mathbb{N}，定义 f_n = 0。
对于两个生成函数 F 和 G，有
F+G = \sum\limits_{n \ge 0} (f_n + g_n) x^n
FG = \sum\limits_{n \ge 0} \left( \sum\limits_{i=0}^n f_i g_{n-i}\right) x^n
乘法逆
定义 F 的乘法逆（简称逆） F^{-1} 为唯一的函数使得 F F^{-1} = 1，那么有 F 存在逆当且仅当 f_0 \ne 0，证明如下：
若 f_0 = 0，则对任意 G，有 (fg)_0 = 0，因此 F^{-1} 不存在。
否则，考虑函数 G，令 g_0 = f_0^{-1}，那么对于 n \ge 1，有
\sum\limits_{i=0}^n f_i g_{n-i}
即
g_n = f_0^{-1} \sum\limits_{i=1}^n f_i g_{n-i}
因此可以递推出 G。
\textbf{Example}
因为 (1-x) \sum\limits_{n \ge 0} x^n = 1，因此有 \sum\limits_{n \ge 0} x^n = \frac{1}{1-x}，因此有
\frac{F(x)}{1-x} = \sum\limits_{n \ge 0} \left( \sum\limits_{k=0}^n f_k \right) x^n
令 F(x) = \frac{1}{1-x}，则有
\frac{1}{(1-x)^2} = \sum\limits_{n \ge 0} (n+1) x^n
注意到
x^m F(x) = \sum\limits_{n \ge 0} f_n x^{n+m} = \sum\limits_{n \ge 0} f_{n-m} x^n
因此将 F 乘上 x^m 就相当于将 f 左移 m 位。
例如
\frac{x}{(1-x)^2} = \sum\limits_{n \ge 0} n x^n
复合
对于两个函数 F 和 G，定义 F \circ G = F(G(x))，其中
F(G(x)) = \sum\limits_{n \ge 0} f_n G^n(x)
若 $F(G(x)) = x$，则成 $G$ 为 $F$ 的复合逆，定义 $G = F^{<-1>}$，显然若复合逆存在，则复合逆唯一且可逆。若 $f_0 = 0$，$F^{<-1>}$ 存在当且仅当 $f_1 \ne 0$。
复合具有一下性质：
$$ C = F + G \Rightarrow C(A(x)) = F(A(x)) + G(A(x)) $$
$$ C = FG \Rightarrow C(A(x)) = F(A(x)) \cdot B(A(x)) $$
$$ \exists F^{<-1>}, F(A(x)) = F(B(x)) \Rightarrow A(x) = B(x) $$
$$ \exists F^{<-1>} \Rightarrow F(G(x))^{-1} = F^{-1}(G(x)) $$
---
$\textbf{Example}
根据二项式定理，(1+x)^n = \sum\limits_{k=0}^m \binom{n}{k} x^k，又 (1+x)^a (1+x)^b = (1+x)^{a+b}，因此
\binom{a+b}{n} = \sum\limits_{k=0}^n \binom{a}{k} \binom{b}{n-k}
求导
定义 F 的导函数 F' = \sum\limits_{n \ge 1} n f_n x^{n-1} = \sum\limits_{n \ge 0} (n+1) f_{n+1} x^n，则有
(F+G)' = F' + G'
(FG)' = F'G + FG'
(F^{-1})' = - \frac{F'}{F^2}
F(G(x))' = F'(G(x)) \cdot G'(x)
进一步的
x F' = \sum\limits_{n \ge 0} n f_n x^n
(xF)' = \sum\limits_{n \ge 1} n a_{n-1} x^{n-1}
(e^x)' = e^x, \ln'(1+x) = \sum\limits_{n \ge 1} (-1)^{n-1} x^[n-1] = \frac{1}{1+x}
\ln' F = \frac{F'}{F}
\int F = \sum\limits_{n \ge 1} \frac{f_{n-1}}{n} x^n + C
\textbf{Example}
令 f_n = \binom{2n}{n}，则 f_n = \frac{2n(2n-1)}{n^2} f_{n-1}，因此 n f_n = 4n f_{n-1} - 2 f_{n-1}，考虑 x^{n-1} 的系数，有
F' = 4(xF)' - 2F
F' = 4F + 4xF' - 2F = 4xF' + 2F
因此
\ln' F = \frac{F'}{F} = \frac{2}{1-4x} = - \frac{1}{2} \ln'(1-4x)
F = \frac{1}{\sqrt{1-4x}}
或者，注意到
(-1)^n = \binom{-1}{n} = \sum\limits_{k=0}^n \binom{- \frac{1}{2}}{k} \binom{- \frac{1}{2}}{n-k}
= \left( - \frac{1}{4} \right)^n \sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k}
即
\sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n
也就是 F^2 = \frac{1}{1-4x}，即 F = \frac{1}{\sqrt{1-4x}}
指数型生成函数 (\text{EGF})
对于数列 \{ f_n \}，定义其 \text{EGF} 为 F(x) = \sum\limits_{i \ge 0} f_i \frac{x^i}{i!}，并对 n \notin \mathbb{N}，定义 f_n = 0。
\textbf{Example}
设 G = F e^x，则有
g_n = \sum\limits_{k=0}^n \binom{n}{k} f_k
同时 F = G e^{-x}，即
f_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} g_k
则就是二项式反演
g_n = \sum\limits_{k=0}^n \binom{n}{k} f_k \Leftrightarrow f_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} f_k
\textbf{Example}
对错排的 \text{EGF} D，注意到对于 n 的每个排列 P，枚举 \sum\limits_{i=1}^n [P_i = i]，就有
\sum\limits_{k=0}^n \binom{n}{k} d_{n-k} = n!
D e^x = \sum\limits_{n \ge 0} \frac{n!}{n!} x^n = \sum\limits_{n \ge 0} x^n = \frac{1}{1-x}
D = \frac{e^{-x}}{1-x}
即
d_n = n! \sum\limits_{k=0}^n \frac{(-1)^k}{k!}
矩阵和反演
给定两个 n \times n 的下三角矩阵 A 和 B，以及 n 维多项式向量 P 和 Q，其中满足
P = AQ, Q = BP
即
p_n(x) = \sum\limits_{k=0}^n a_{n,k} q_k(x), q_n(x) = \sum\limits_{k=0}^n b_{n,k} p_k(x)
例如
x^n = \sum\limits_{k=0}^n \binom{n}{k} (x-1)^k, (x-1)^n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} x^k \tag{1}
和
x^n = \sum\limits_{k=0}^n {n \brace k} x^{\underline{k}}, x^{\underline{n}} = \sum\limits_{k=0}^n (-1)^{n-k} {n \brack k} x^k \tag{2}
若 P 和 Q 都是向量空间 \mathbb{C}[x] 的基，那么就有 AB = I
那么令 f 和 g 是两个数列，则有
f = Ag \Leftrightarrow g = Bf
即
\forall n \in \mathbb{N}, f_n = \sum\limits_{k=0}^n a_{n,k} g_k \Leftrightarrow \forall n \in \mathbb{N}, g_n = \sum\limits_{k=0}^n b_{n,k} f_k
二项式反演
根据 (1)，能得到二项式反演
f_n = \sum\limits_{k=0}^n \binom{n}{k} g_k \Leftrightarrow g_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} f_k
或者可以表示成
f_n = \sum\limits_{k=0}^n (-1)^k \binom{n}{k} g_k \Leftrightarrow g_n = \sum\limits_{k=0}^n (-1)^k \binom{n}{k} f_k
\textbf{Example}
由于
k^n = \sum\limits_{i=0}^k {n \brace i} \binom{k}{i} i!
有
k! {n \brace k} = \sum\limits_{i=0}^n (-1)^{k-i} \binom{k}{i} i^n
{n \brace k} = \frac{1}{k!} \sum\limits_{i=0}^n (-1)^{k-i} \binom{k}{i} i^n
\textbf{Example}
设
f(x) = \sum\limits_{k \ge 0} a_k x^{\underline{k}} = \sum\limits_{k \ge 0} \binom{x}{k} k! a_k
有
f(n) = \sum\limits_{k=0}^n \binom{n}{k} k! a_k
n! a_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} f(k)
当 \deg f < n 时，有
\sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} f(k) = 0
例如
\sum\limits_{k=0}^n (-1)^k \binom{n}{k} \binom{n+k}{k} = \sum\limits_{k=0}^n \binom{n}{n-k} \binom{-n-1}{k} = \binom{-1}{n} = (-1)^n
或者令
f(x) = \binom{x+n}{n} = \sum\limits_{k=0}^n \binom{x}{k} \binom{n}{k} = \frac{x^{\underline{n}}}{n!} + \cdots
那么有 a_n = \frac{1}{n!}，因此
\sum\limits_{k=0}^n (-1)^k \binom{n}{k} f(k) = (-1)^n n! a_n = (-1)^n
斯特林反演
根据 (2)，有
f_n = \sum\limits_{k=0}^n {n \brace k} g_k \Leftrightarrow g_n = \sum\limits_{k=0}^n (-1)^{n-k} {n \brack k} f_k
并且有
\sum\limits_{k \ge 0} (-1)^{k-m} {n \brace k} {k \brack m} = [n = m]
概率生成函数 (\text{PGF})
给定随机变量 X:\Omega \to \mathbb{N}，设 p_n = \operatorname{Prob}(X = n)，那么 X 的 \text{PGF} 为
P_X = \sum\limits_{n \ge 0} p_n x^n
这个函数的所有系数都非负，且 P_X(1)=1。
定义 X 的期望值为
\mathbb{E} X = \sum\limits_{n \ge 0} n p_n = P'_X(1)
定义 X 的方差为
\operatorname{Var} X = \mathbb{E} X^2 - \mathbb{E}^2 X
注意到
P''_X = \sum\limits_{n \ge 2} n(n-1) p_n x^{n-2} = \sum\limits_{n \ge 2} n^2 p_n x^{n-2} - \sum\limits_{n \ge 2} n p_n x^{n-2} = \mathbb{E} X^2 - \mathbb{E} X
因此
\operatorname{Var} X = P''_X(1) + P'_X(1) - P'^2_X(1)
\textbf{Example}
令 \Omega = S(n), X_n(\pi) = \operatorname{inv}(\pi)，设 I_{n,k} = \sum\limits_{P \in S(n)} [\operatorname{inv} P = k]，则有
P_{X_n} = \sum\limits_{k \ge 0} \frac{I_{n,k}}{n!} x^k
又因为
I_{n,k} = \sum\limits_{i=0}^{n-1} I_{n-1,k-i}
因此
P_{X_n} = \frac{1 - x^n}{(1-x)n} P_{X_{n-1}}
又有 P_{X_1} = 1，因此
P_{X_n} = \prod\limits_{i=1}^n \frac{1 + x + x^2 + \cdots + x^{i-1}}{i}
P'_{X_n} = \sum\limits_{i=1}^n \left( \prod\limits_{1 \le j \le n, j \ne i} \frac{1 + x + \cdots x^{j-1}}{j} \right) \frac{1 + 2x + 3x^2 + \cdots + (i-1) x^{i-2}}{i}
\mathbb{E} X_n = P'_{X_n}(1) = \sum\limits_{i=1}^n \frac{i-1}{2} = \frac{n(n-1)}{4}
\operatorname{Var} X_n = \frac{n(n-1)(2n+5)}{72}
随机游走
给定一个数轴，一个点一开始在 0，每次会等概率的选择向左或右有一步，对于一个 m \in \mathbb{N_+}，问到达 m 或 -m 的概率，以及期望多少步才能到。
令 g_{m,n} 表示有多少个路线使得在第 n 步第一次到达 m 或 -m，那么有
P_X = G_m(\frac{x}{2})
\mathbb{E} X = \frac{1}{2} G'_m (\frac{1}{2})
定义正游走表示走过的所有坐标都非负，令 e_{m,n} 表示在第 n 步时第一次到达 0，且从未到过 m 的正游走数，\dot e_{m,n} 则不需要保证是第一次到达 0。有 e_{m,0} = 0, \dot e_{m,0} = 1，而
\dot e_{m,n} = \sum\limits_{k=1}^n e_{m,k} \dot e_{m,n-k}
\dot E_m = E_m \dot E_m + 1
\dot E_m = \frac{1}{1 - E_m}
同时，去掉第一步和第 n 步，就有
e_{m,n} = \dot e_{m-1,n-2}
E_m = x^2 \dot E_{m-1} = \frac{x^2}{1 - E_{m-1}}
而 E_1 = 0，那么设 A_m = E_m(\frac{1}{2})，就有
A_m = \frac{1}{4(1 - A_{m-1})}
A_m = \frac{m-1}{2m}
并设 B_m = E'_m(\frac{1}{2})，有
B_m = \frac{2(m^2-1)}{3m}
现在设 f_{m,n} 表示在第 n 步第一次到 m 的正游走数，枚举最后一次到达 0 的时间，有
f_{m,n} = \sum\limits_{k=1}^n e_{m,k} f_{m,n-k} + f_{m-1,n-1}
F_m = E_m F_m + x F_{m-1}
其中
F_1 = x
设 U_m = F_m(\frac{1}{2}), V_m = F'_m(\frac{1}{2})，能得到
U_m = \frac{1}{m+1}, V_m = \frac{2m(m+2)}{3(m+1)}
最后考虑计算 G，枚举最后一次回到 0 的时间，就有
g_{m,n} = 2 \left( \sum\limits_{k=1}^n e_{m,k} g_{m,n-k} + f_{m-1,n-1} \right)
G_m = 2(E_m G_m + x F_{m-1})
因此
G_m = \frac{2x F_{m-1}}{1 - 2 E_m}
P_X(1) = G_m(\frac{1}{2}) = \frac{U_{m-1}}{1 - 2 A_m} = \frac{1}{m \left( 1 - \frac{m-1}{m} \right)} = 1
\mathbb{E} X = \frac{1}{2} G'_m(\frac{1}{2}) = \frac{(U_{m-1} + \frac{1}{2} V_{m-1})(1 - 2 A_m) + U_{m-1} B_m}{(1 - 2 A_m)^2} = m^2
斐波那契游走
现在考虑一个新的随机游走，从 1 开始，每次会等概率选择向左走 1 步或向右走两步，问到 0 的概率。
令 f_{m,n} 表示从 m 开始，走 n 步第一次到 0 的游走数，那么从 m+1 开始，显然要先到 m，枚举第一次到 m 的时间，有
f_{m+1,n} = \sum\limits_{k=0}^n f_{1,k} f_{m,n-k}
F_{m+1} = F \cdot F_m
因此
F_m = F^m
考虑第一次是向左还是向右，就有
F = x + x F^3
而答案为 p = F(\frac{1}{2})，所以
p = \frac{1}{2} + \frac{1}{2} p^3
p^3 - 2p + 1 = (p-1)(p^2+p-1) = 0
因此 p=1 或 p = \frac{\sqrt{5} - 1}{2} 或 p = \frac{- \sqrt{5} - 1}{2}。显然 p \ge 0，因此 p \ne \frac{- \sqrt{5} - 1}{2}，又有 F 在区间 [0, \frac{1}{2}] 单调递增（因为 x < \frac{1}{2} 相当于有概率原地暴毙），因此 F'(\frac{1}{2}) \ge 0，而
F' = 1 + F^3 + 3x F^2 F'
F' = \frac{1 + F^3}{1 - 3x F^2}
如果 F(\frac{1}{2})=1，有
F'(\frac{1}{2}) = \frac{2}{1 - \frac{3}{2}} = -4 < 0
因此 p = \frac{\sqrt{5} - 1}{2}，而 p_m = \left( \frac{\sqrt{5} - 1}{2} \right)^m。
数论函数
对一个定义域为 \mathbb{N_+}，值域为 \mathbb{C} 的函数，我们称其为数论函数。
若无特殊定义，默认所有变量都为正整数，p 为质数，k 为 n 的不同质因数的个数，p_i 为 n 第 i 大的质因数，n = \prod\limits_{i=1}^k p_i^{c_i}。
莫比乌斯函数
定义莫比乌斯函数 \mu(n) 满足：\mu(1) = 1，对 n>1 ，若 \forall 1 \le i \le k, a_i = 1，则 \mu(n) = (-1)^k，否则 \mu(n) = 0。也就是说 \mu(n) = 0 当且仅当 n 有一个 >1 的平方因子。
\text{Theorem.1}
\sum\limits_{d \mid n} \mu(d) = [n=1]
\textbf{Proof:}
令 n > 1，显然 \mu(d) \ne 0 当且仅当 d 可以表示成 \prod\limits_{i=1}^{k'} p_{a_i}，其中 \forall 1 \le i < k', a_i < a_{i+1}，因此
\sum\limits_{d \mid n} \mu(d) = 1 + \mu(p_1) + \mu(p_2) + \cdots + \mu(p_1 p_2) + \cdots + \mu(p_1 p_2 \cdots p_k)
= \sum\limits_{i=0}^k \binom{k}{i} (-1)^i = 0
欧拉函数
定义欧拉函数 \varphi(n) 为有多少个不超过 n 的正整数和 n 互质，即
\varphi(n) = \sum\limits_{k=1}^n [\gcd(k,n) = 1]
\text{Theorem.2}
\sum\limits_{d \mid n} \varphi(d) = n
\textbf{Proof:}
设
A(d) = \{ k \mid \gcd(k,n) = d, 1 \le k \le n \}
显然对 n 的所有因数 d，A(d) 恰好遍历了所有不超过 n 的正整数，因此
\sum\limits_{d \mid n} |A(d)| = n
\sum\limits_{d \mid n} \varphi(\frac{n}{d}) = n
\sum\limits_{d \mid n} \varphi(d) = n
\text{Theorem.3}
\varphi(n) = \sum\limits_{d \mid n} \mu(d) \frac{n}{d}
\textbf{Proof:}
\varphi(n) = \sum\limits_{k=1}^n [\gcd(n,k) = 1] = \sum\limits_{k=1}^n \sum\limits_{d \mid \gcd(n,k)} \mu(d) = \sum\limits_{k=1}^n \sum\limits_{d \mid n, d \mid k} \mu(d)
= \sum\limits_{d \mid n} \sum\limits_{k=1}^{n/d} \mu(d) = \sum\limits_{d \mid n} \mu(d) \frac{n}{d}
\text{Theorem.4}
\varphi(n) = n \prod\limits_{p \mid n} (1 - \frac{1}{p})
\textbf{Proof:}
\prod\limits_{p \mid n} (1 - \frac{1}{p}) = 1 - \frac{1}{p_1} - \frac{1}{p_2} - \cdots + \frac{1}{p_1 p_2} + \cdots + \frac{(-1)^k}{p_1 p_2 \cdots p_k} = \sum\limits_{d \mid n} \frac{\mu(d)}{d} = \frac{1}{n} \varphi(n)
\text{Theorem.5}
\varphi(p^c) = p^c - p^{c-1} \tag{1}
\textbf{Proof:}
根据定义或公式即可证明。
\varphi(nm) = \varphi(n) \varphi(m) \frac{\gcd(n,m)}{\varphi(\gcd(n,m))} \tag{2}
\textbf{Proof:}
\frac{\varphi(nm)}{nm} = \prod\limits_{p \mid nm} (1 - \frac{1}{p}) = \frac{\prod\limits_{p \mid n} \left( 1 - \frac{1}{p} \right) \prod\limits_{p \mid m} \left( 1 - \frac{1}{p} \right)}{\prod\limits_{p \mid \gcd(n,m)} \left( 1 - \frac{1}{p} \right)} = \frac{\frac{\varphi(n)}{n} \frac{\varphi(m)}{m}}{\frac{\varphi(d)}{d}}
即
\varphi(nm) = \frac{\varphi(n) \varphi(m) \gcd(n,m)}{\varphi(\gcd(n,m))}
若 \gcd(n,m) = 1，则
\varphi(nm) = \varphi(n) \varphi(m) \tag{3}
\textbf{Proof:}
根据 (2) 即可证明。
n \mid m \Rightarrow \varphi(n) \mid \varphi(m) \tag{4}
\textbf{Proof:}
显然当 n=1 时结论成立，否则对 m 归纳，设 k = \frac{m}{n}，则
\varphi(m) = \varphi(nk) = \varphi(n) \varphi(k) \frac{\gcd(n,m)}{\varphi(\gcd(n,k))} = \gcd(n,k) \varphi(n) \frac{\varphi(k)}{\varphi(\gcd(n,k))}
因为 k<m，因此 \varphi(\gcd(n,k)) \mid \varphi(k)，所以 \varphi(n) \mid \varphi(m)。
若 n \ge 3，则 2 \mid \varphi(n)，且若 n 有 k 个奇质因数，则
2^k \mid \varphi(n) \tag{5}
\textbf{Proof:}
\varphi(n) = n \prod\limits_{p \mid n} \frac{p-1}{p} = \frac{n}{\prod\limits_{p \mid n} p} \prod\limits_{p \mid n} (p-1)
当 n \ge 3 时，若 4 \mid n，则 2 \mid \frac{n}{\prod\limits_{p \mid n} p}，否则 n 有一个奇的质因数，因此 2 \mid \prod\limits_{p \mid n} (p-1)，进一步的，2^k \mid \prod\limits_{p \mid n} (p-1)，即 2^k \mid \varphi(n)。
迪利克雷卷积
定义两个数论函数 f 和 g 的迪利克雷卷积为
(f*g)(n) = \sum\limits_{d \mid n} f(d) g(\frac{n}{d})
例如 \text{Theorem.1} 可以表示为
\varepsilon = \mu * I
$$ \varphi = \mu * \text{id} $$
---
### $\text{Theorem.6}
f*g = g*f \tag{1}
\textbf{Proof:}
(f*g)(n) = \sum\limits_{d \mid n} f(d) g(\frac{n}{d}) = (g*f)(n)
f*(g*h) = (f*g)*h \tag{2}
\textbf{Proof:}
f*(g*h) = \sum\limits_{abc=n} f(a) g(b) h(c) = (f*g)*h
\text{Theorem.7}
f * \varepsilon = \varepsilon * f = f
\textbf{Proof:}
(f * \varepsilon)(n) = \sum\limits_{d \mid n} f(d) \varepsilon(\frac{n}{d}) = \sum\limits_{d \mid n} f(d) [n=d] = f(n)
反之同理。
\text{Theorem.8}
对 f(1) \ne 0，存在 f^{-1} 使得
f * f^{-1} = f^{-1} * f = \varepsilon
\textbf{Proof:}
由于 (f * f^{-1})(1) = \varepsilon(1)，因此 f(1) f^{-1}(1) = 1，而对 n>1，有
\sum\limits_{d \mid n} f(\frac{n}{d}) f^{-1}(d) = 0
f(1) f^{-1}(n) + \sum\limits_{d \mid n, d < n} f(\frac{n}{d}) f^{-1}(d) = 0
即
f^{-1}(n) = - f(1)^{-1} \sum\limits_{d \mid n, d < n} f(\frac{n}{d}) f^{-1}(d)
同时有
(f*g)^{-1} = f^{-1} * g^{-1}
证明不难。
\text{Theorem.9}
有莫比乌斯反演
f(n) = \sum\limits_{d \mid n} g(d) \Rightarrow g(n) = \sum\limits_{d \mid n} f(d) \mu(\frac{n}{d})
\textbf{Proof:}
f = g * I \Rightarrow f * \mu = (g * I) * \mu = g * (I * \mu) = g * \varepsilon = g
同时可以借此由 \text{Theorem.2} 推导出 \text{Theorem.3}：
n = \sum\limits_{d \mid n} \varphi(d) \Rightarrow \varphi(n) = \sum\limits_{d \mid n} \mu(d) \frac{n}{d}
曼戈尔特函数
定义曼戈尔特函数 \Lambda(n) 满足：若 k=1，则 \Lambda(n) = c_1，否则 \Lambda(n) = 0。
\text{Theorem.10}
\log n = \sum\limits_{d \mid n} \Lambda(d)
\textbf{Proof:}
\sum\limits_{d \mid n} \Lambda(d) = \sum\limits_{i=1}^k \sum\limits_{j=1}^{c_i} \Lambda(p^j_i) = \sum\limits_{i=1}^k \sum\limits_{j=1}^{c_i} \log p_i = \sum\limits_{k=1}^k c_i \log p_i = \log n
\text{Theorem.11}
\Lambda(n) = \sum\limits_{d \mid n} \mu(d) \log \frac{n}{d} = - \sum\limits_{d \mid n} \mu(d) \log(d)
\textbf{Proof:}
对 \text{Theorem.10} 莫比乌斯反演，有
\Lambda(n) = \sum\limits_{d \mid n} \mu(d) \log \frac{n}{d} = \log n \sum\limits_{d \mid n} \mu(d) - \sum\limits_{d \mid n} \mu(d) \log d = \varepsilon(n) \log n - \sum\limits_{d \mid n} \mu(d) \log d
显然 \varepsilon(n) 和 \log n 不同时非 0，因此可以证明。
积性函数
称 f 为积性函数当且仅当
\forall \gcd(n,m) = 1, f(nm) = f(n) f(m)
称积性函数 f 为完全积性函数当且仅当
\forall n,m, f(nm) = f(n) f(m)
例如 \text{id}_a 和 \varepsilon 就是完全积性函数，而 \mu 和 \varphi 则是积性函数。
对积性函数 f 和 g，有 f g 和 \frac{f}{g} 都是积性函数。
\text{Theorem.12}
**$\textbf{Proof:}$**
因为 $\gcd(1,n) = 1$，因此 $f(n) = f(1) f(n)$，而 $f$ 不全为 $0$，因此 $f(1) = 1$。
---
### $\text{Theorem.13}
令 f(1) = 1，则
$$ f(n) = \prod\limits_{i=1}^k f(p_i^{c_i}) $$
积性函数 $f$ 是完全积性函数当且仅当
$$ f(p^c) = f(p)^c $$
---
### $\text{Theorem.14}
对积性函数 f 和 g，有 f*g 也是积性函数。
\textbf{Proof:}
设 h=f*g，则
h(nm) = \sum\limits_{c \mid nm} f(c) g(\frac{nm}{c})
显然对每个 c 都能将其分解称 ab 使得
a \mid n, b \mid m, \gcd(a,b) = 1, \gcd(\frac{n}{a}, \frac{m}{b}) = 1
因此
h(nm) = \sum\limits_{a \mid n, b \mid m} f(ab) g(\frac{nm}{ab}) = \sum\limits_{a \mid n, b \mid m} f(a) f(b) g(\frac{n}{a}) g(\frac{m}{b})
= \left( \sum\limits_{a \mid n} f(a) g(\frac{n}{a}) \right) \left( \sum\limits_{b \mid m} f(b) g(\frac{m}{b}) \right) = h(n) h(m)
\text{Theorem.15}
若 g 和 f*g 都是积性函数，则 f 也是。
\textbf{Proof:}
假设 f 不为积性函数，那么
\exists \gcd(n,m) = 1
若 n=m=1，则 f(1) \ne f(1) f(1)，因此 f(1) \ne 1，因此 h(1) = f(1) g(1) \ne 1
否则有
\forall \gcd(a,b) = 1, ab < nm, f(ab) = f(a) f(b)
那么
h(nm) = \sum\limits_{a \mid n, b \mid m, ab < nm} f(ab) g(\frac{nm}{ab}) + f(nm) g(1)
= \sum\limits_{a \mid n, b \mid m, ab < nm} f(a) f(b) g(\frac{n}{a}) g(\frac{m}{b}) + f(nm)
= \left( \sum\limits_{a \mid n} f(a) g(\frac{n}{a}) \right) \left( \sum\limits_{b \mid m} f(b) g(\frac{m}{b}) \right) - f(n) f(m) + f(nm)
= h(n) h(m) - f(n) f(m) + f(nm)
又因为 f(nm) \ne f(n) f(m)，因此 h(nm) \ne h(n) h(m)，因此 h 不是积性函数，与原命题相悖。
\text{Theorem.16}
若 f 是积性函数，那么 f^{-1} 也是。
\textbf{Proof:}
由于 g * g^{-1} = \varepsilon 为积性函数，那么根据 \text{Theorem.15} 即可证明。
\text{Theorem.17}
若 f 是积性函数，那么 f 是完全积性函数当且仅当
f^{-1} = \mu f
\textbf{Proof:}
令 g = f \mu，若 f 为完全积性函数，那么有
(f*g)(n) = \sum\limits_{d \mid n} \mu(d) f(d) f(\frac{n}{d}) = f(n) \sum\limits_{d \mid n} = (f \varepsilon)(n) = \varepsilon(n)
相反的，假设 f^{-1} = \mu f，那么有
\forall n > 1, \sum\limits_{d \mid n} \mu(d) f(d) f(\frac{n}{d}) = 0
令 n = p^c，则有
\mu(1) f(1) f(p)^c + \mu(p) f(p) f(p^{c-1}) = 0
f(p^c) = f(p) f(p^{c-1})
f(p^c) = f(p)^c
因此 f 为完全积性函数。
\textbf{Example}
因为 \varphi = \mu * \text{id}，而 \text{id} 是完全积性函数，因此
\varphi^{-1} = \mu^{-1} * id^{-1} = \mu^{-1} * \mu id = I * \mu \text{id}
即
\varphi^{-1}(n) = \sum\limits_{d \mid n} d \mu(d)
\text{Theorem.18}
令 f 为积性函数，有
\sum\limits_{d \mid n} \mu(d) f(d) = \prod\limits_{p \mid n} (1 - f(p))
\textbf{Proof:}
设 g = \mu f，则
g(p^c) = \sum\limits_{d \mid p^c} \mu(d) f(d) = \mu(1) f(1) + \mu(p) f(p) = 1 - f(p)
而 g 是积性函数，因此
g(n) = \prod\limits_{p \mid n} g(p^c) = \prod\limits_{p \mid n} (1 - f(p))
刘维尔函数
定义刘维尔函数 \lambda(n) 满足
\lambda(n) = (-1)^{\sum\limits_{i=1}^k c_i}
\text{Theorem.19}
\sum\limits_{d \mid n} \lambda(d) = [n \text{ is a square}]
同时有
\lambda^{-1} = |\mu|
\textbf{Proof:}
设 f = 1 * \lambda，那么
g(p^c) = \sum\limits_{d \mid p^c} \lambda(d) = \sum\limits_{i=0}^c (-1)^i = [2 \mid c]
而 f 是积性函数，因此
g(n) = \prod\limits_{i=1}^k g(p^c) = [\forall 1 \le i \le k, 2 \mid i] = [n \text{ is a square}]
同时 \lambda^{-1} = \mu \lambda = \mu^2 = |\mu|。
因数函数
对复数 \alpha，设
\sigma_{\alpha}(n) = \sum\limits_{d \mid n} d^{\alpha}
而
\sigma_{\alpha}(p^c) = \sum\limits_{i=0}^c p^{i \alpha} = \frac{p^{\alpha (c+1)} - 1}{p^{\alpha} - 1}
\text{Theorem.20}
\sigma_{\alpha}^{-1}(n) = \sum\limits_{d \mid n} d^{\alpha} \mu(d) \mu(\frac{n}{d})
\textbf{Proof:}
由于 \sigma_{\alpha} = \text{id}_{\alpha} * 1 且 \text{id}_{\alpha} 是完全积性函数，因此
\sigma_{\alpha}^{-1} = \mu \text{id}_{\alpha} * I^{-1} = \mu \text{id}_{\alpha} * \mu
广义卷积
对定义在正实数域上的函数 F 满足 \forall 0 < x < 1, F(x) = 0，和数论函数 f，定义他们的广义卷积为
(f \circ F)(x) = \sum\limits_{n \le x} f(n) F(\frac{x}{n})
\text{Theorem.21}
f \circ (g \circ F) = (f * g) \circ F
\textbf{Proof:}
(f \circ (g \circ F))(x) = \sum\limits_{n \le x} f(n) \sum\limits_{m \le \frac{x}{n}} g(m) F(\frac{x}{nm}) = \sum\limits_{nm \le x} f(n) g(m) F(\frac{x}{nm})
= \sum\limits_{n \le x} \left( \sum\limits_{k \mid n} f(k) g(\frac{n}{k}) \right) F(\frac{x}{n}) = \sum\limits_{n \le x} (f*g)(n) F(\frac{x}{n}) = ((f*g) \circ F)(x)
那么有
(\varepsilon \circ F)(x) = \sum\limits_{n \le x} [n = 1] F(\frac{x}{n}) = F(x)
即 \varepsilon 也是 \circ 的单位元。
\text{Theorem.22}
G = f \circ F \Leftrightarrow F = f^{-1} \circ G
\textbf{Proof:}
证明不难。
\text{Theorem.23}
若 f 为完全积性函数，则
G = f \circ F \Leftrightarrow F = (\mu f) \circ G
\textbf{Proof:}
f^{-1} = \mu f
未完待续（但是应该不会更新了）。
一些习题
习题（带答案），如果有错误的地方欢迎指正。