专栏文章

一些数学定理

__abcd_
算法·理论参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mkhmasow
此快照首次捕获于
2026/01/17 09:17
2 个月前
此快照最后确认于
2026/01/17 09:17
2 个月前
查看原文

组合数学

二项式定理

(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=nx=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)(1) 的两侧同时乘上 n!n!，则有 (x+y)^{\underline{n}} = \sum\limits_{i=0}^n x^{\underline{i}} y^{\underline{n-i}} \tag{4}
由于 (−x)n‾=(−1)nxn‾(-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)(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)L(n,m) 表示从 (0,0)(0,0) 走到 (n,m)(n,m) 的路径数，则 L(n,m)=(n+mn)L(n,m) = \binom{n+m}{n}
枚举在第 kk 行最大走到第几列，能得到 (n+mn)=∑i=0mL(k,i)×L(n−k−1,m−i)=∑i=0m(k+ik)(n−k−1+m−in−k−1)\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)(8) 和 (9)(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}
Example\textbf{Example}
nk=∑i=0k{ki}(ni)i!n^k = \sum\limits_{i=0}^k {k \brace i} \binom{n}{i} i!
令 k≥nk \ge n，则 nk=∑i=0n{ki}(ni)i!⇒{kn}n!=∑i=0n(−1)n−i(ni)ikn^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}
这就是第二类斯特林数的通项公式。

容斥原理

对于统计满足一些条件的情况数，设 SS 为条件集合，fTf_T 表示不满足 TT 的情况数 ans = \sum\limits_{T \subset S} (-1)^{|S|} f_T \tag{14}
如果有 ∀∣T1∣=∣T2∣,fT1=fT2\forall |T_1| = |T_2|, f_{T_1} = f_{T_2}，那么设 n=∣S∣,gi=fT(∣T∣=i)n = |S|, g_i = f_{T}(|T| = i)，则 ans = \sum\limits_{i=0}^n (-1)^i \binom{n}{i} g_i \tag{15}
Example\textbf{Example}
求 φ(n)\varphi(n) 的通项公式，只需要对 nn 的每个质因子进行容斥，设 P={p∣n}P = \{ p \mid n \}，则 φ(n)=∑S⊂P(−1)∣S∣∑i=1n[∀p∈S,p∣i]\varphi(n) = \sum\limits_{S \subset P} (-1)^{|S|} \sum\limits_{i=1}^n [\forall p \in S, p \mid i] =∑S⊂P(−1)∣S∣n∏p∈Sp= \sum\limits_{S \subset P} (-1)^{|S|} \frac{n}{\prod\limits_{p \in S} p} =n∑S⊂P∏p∈S−1p= 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}
Example\textbf{Example}
对不定方程 x1+x2+⋯+xm=nx_1 + x_2 + \dots + x_m = n 的非负整数解的个数，通过插板法可以得到答案为 (n+m−1m−1)\binom{n+m-1}{m-1}。而所有满足 ∀1≤i≤m,0≤xi<ai\forall 1 \le i \le m, 0 \le x_i < a_i，则只需要枚举不满足条件的集合，就有 ∣{(x1,x2,…,xm)∣∑i=1mxi=n,∀1≤i≤m,xi∈[0,ai)∩Z}∣|\{ (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}
若 ∀1≤i≤m,ai=k\forall 1 \le i \le m, a_i = k，则 ∣{(x1,x2,…,xm)∣∑i=1mxi=n,∀1≤i≤m,xi∈[0,ai)∩Z}∣|\{ (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=1k=1，则有 ∀1≤i≤m,xi=0\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}
类似的，考虑一个问题：给定 nn 个数，从中选 kk 个数，其中 mm 个数必须选，则枚举有多少个数没选，就有 \sum\limits_{i=0}^m (-1)^i \binom{m}{i} \binom{n-i}{k} = \binom{n-m}{k-m} \tag{20}
Example\textbf{Example}
考虑一个有 2n2n 个座位的圆桌，其中有 nn 对夫妻入座，问有多少种入座方式使得每一对夫妻都不相邻，则枚举有多少对夫妻相邻，就有 ans=∑i=0n(−1)i(ni)(2n−ii)i!2i(2n−2i)!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)(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}

LGV\text{LGV} 引理

对于一张图 G=(V,E)G=(V,E)，设起点集合 AA 和终点集合 BB，其中 ∣A∣=∣B∣=n|A| = |B| = n，设 Path⁡(u,v)\operatorname{Path}(u,v) 为从 uu 到 vv 的路径集合，则有 ∑P∈Sn(sign⁡P)∑∀1≤i≤n,pi∈Path⁡(Ai,BPi)[∀1≤i,j≤n,i≠j,pi∩pj=∅]\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}

Burnside\text{Burnside} 引理

令群 GG 作用于 XX，而 MM 为所有等价类，设 XgX_g 为 XX 中所有在 gg 的作用下不变的元素，则有 |M| = \frac{1}{|G|} \sum\limits_{g \in G} |X_g| \tag{25}
Example\textbf{Example}
有一个有 pp 个珠子的项链，其中 pp 为质数，现在将每个珠子都染上 nn 种颜色，那么所有本质不同的染色方案数为 1p∑i=1pngcd⁡(i,p)=(p−1)n+npp\frac{1}{p} \sum\limits_{i=1}^p n^{\gcd(i,p)} = \frac{(p-1)n + n^p}{p}
显然方案数是一个整数，因此 (p−1)n+np≡0(modp)(p-1)n + n^p \equiv 0 \pmod{p}
即 n^p \equiv n \pmod{p} \tag{26}
也就是费马小定理。

Polya\text{Polya} 定理

令群 GG 作用于 SS，设 M(N,S)M(N,S) 为所有用 NN 中的颜色给 SS 中的每个元素染色的方案中所有等价类，设 c(g)c(g) 为 SS 在 gg 的作用下的轮换个数，设 n=∣N∣n = |N|，则有 ∣M(N,S)∣=1∣G∣∑g∈Gnc(g)|M(N,S)| = \frac{1}{|G|} \sum\limits_{g \in G} n^{c(g)}
Example\textbf{Example}
令 S={0,1,…,m−1},gk:i→i+k mod mS = \{ 0, 1, \dots, m-1 \}, g^k : i \to i+k \bmod m，则 ∣M(N,S)∣=1m∑i=0m−1∣N∣gcd⁡(m,i)|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}
Example\textbf{Example}
给定一个正方体，问有多少种染色方案。考虑分类讨论所有翻转方法和方案数以及其对应的轮换个数。
  • 不变，1×11 \times 1，66。
  • 以面为轴转 90°90 \degree，3×23 \times 2，33。
  • 以面为轴转 180°180 \degree，3×13 \times 1，44。
  • 以边为轴转 180°180 \degree，6×16 \times 1，33。
  • 以点为轴转 120°120 \degree，4×24 \times 2，22
因此方案数为 n6+6n3+3n4+6n3+8n2=n6+3n4+12n3+8n2n^6 + 6 n^3 + 3 n^4 + 6 n^3 + 8 n^2 = n^6 + 3 n^4 + 12 n^3 + 8 n^2

生成函数

一般性生成函数 (OGF)(\text{OGF})

对于数列 {fn}\{ f_n \}，定义其 OGF\text{OGF} 为 F(x)=∑i≥0fixiF(x) = \sum\limits_{i \ge 0} f_i x^i，并对 n∉Nn \notin \mathbb{N}，定义 fn=0f_n = 0。
对于两个生成函数 FF 和 GG，有 F+G=∑n≥0(fn+gn)xnF+G = \sum\limits_{n \ge 0} (f_n + g_n) x^n FG=∑n≥0(∑i=0nfign−i)xnFG = \sum\limits_{n \ge 0} \left( \sum\limits_{i=0}^n f_i g_{n-i}\right) x^n

乘法逆

定义 FF 的乘法逆（简称逆） F−1F^{-1} 为唯一的函数使得 FF−1=1F F^{-1} = 1，那么有 FF 存在逆当且仅当 f0≠0f_0 \ne 0，证明如下：
若 f0=0f_0 = 0，则对任意 GG，有 (fg)0=0(fg)_0 = 0，因此 F−1F^{-1} 不存在。
否则，考虑函数 GG，令 g0=f0−1g_0 = f_0^{-1}，那么对于 n≥1n \ge 1，有 ∑i=0nfign−i\sum\limits_{i=0}^n f_i g_{n-i}
即 gn=f0−1∑i=1nfign−ig_n = f_0^{-1} \sum\limits_{i=1}^n f_i g_{n-i}
因此可以递推出 GG。
Example\textbf{Example}
因为 (1−x)∑n≥0xn=1(1-x) \sum\limits_{n \ge 0} x^n = 1，因此有 ∑n≥0xn=11−x\sum\limits_{n \ge 0} x^n = \frac{1}{1-x}，因此有 F(x)1−x=∑n≥0(∑k=0nfk)xn\frac{F(x)}{1-x} = \sum\limits_{n \ge 0} \left( \sum\limits_{k=0}^n f_k \right) x^n
令 F(x)=11−xF(x) = \frac{1}{1-x}，则有 1(1−x)2=∑n≥0(n+1)xn\frac{1}{(1-x)^2} = \sum\limits_{n \ge 0} (n+1) x^n
注意到 xmF(x)=∑n≥0fnxn+m=∑n≥0fn−mxnx^m F(x) = \sum\limits_{n \ge 0} f_n x^{n+m} = \sum\limits_{n \ge 0} f_{n-m} x^n
因此将 FF 乘上 xmx^m 就相当于将 ff 左移 mm 位。
例如 x(1−x)2=∑n≥0nxn\frac{x}{(1-x)^2} = \sum\limits_{n \ge 0} n x^n

复合

对于两个函数 FF 和 GG，定义 F∘G=F(G(x))F \circ G = F(G(x))，其中 F(G(x))=∑n≥0fnGn(x)F(G(x)) = \sum\limits_{n \ge 0} f_n G^n(x)
F(G(x))F(G(x)) 是良定义的当且仅当 FF 的项数有限或 g0=0g_0 = 0，否则 F(G(x))F(G(x)) 不收敛。
若 F(G(x))=xF(G(x)) = x，则成 GG 为 FF 的复合逆，定义 G=F<−1>G = F^{<-1>}，显然若复合逆存在，则复合逆唯一且可逆。若 f0=0f_0 = 0，F<−1>F^{<-1>} 存在当且仅当 f1≠0f_1 \ne 0。
复合具有一下性质： C=F+G⇒C(A(x))=F(A(x))+G(A(x))C = F + G \Rightarrow C(A(x)) = F(A(x)) + G(A(x)) C=FG⇒C(A(x))=F(A(x))⋅B(A(x))C = FG \Rightarrow C(A(x)) = F(A(x)) \cdot B(A(x)) ∃F<−1>,F(A(x))=F(B(x))⇒A(x)=B(x)\exists F^{<-1>}, F(A(x)) = F(B(x)) \Rightarrow A(x) = B(x) ∃F<−1>⇒F(G(x))−1=F−1(G(x))\exists F^{<-1>} \Rightarrow F(G(x))^{-1} = F^{-1}(G(x))
Example\textbf{Example}
根据二项式定理，(1+x)n=∑k=0m(nk)xk(1+x)^n = \sum\limits_{k=0}^m \binom{n}{k} x^k，又 (1+x)a(1+x)b=(1+x)a+b(1+x)^a (1+x)^b = (1+x)^{a+b}，因此 (a+bn)=∑k=0n(ak)(bn−k)\binom{a+b}{n} = \sum\limits_{k=0}^n \binom{a}{k} \binom{b}{n-k}

求导

定义 FF 的导函数 F′=∑n≥1nfnxn−1=∑n≥0(n+1)fn+1xnF' = \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′(F+G)' = F' + G' (FG)′=F′G+FG′(FG)' = F'G + FG' (F−1)′=−F′F2(F^{-1})' = - \frac{F'}{F^2} F(G(x))′=F′(G(x))⋅G′(x)F(G(x))' = F'(G(x)) \cdot G'(x)
进一步的 xF′=∑n≥0nfnxnx F' = \sum\limits_{n \ge 0} n f_n x^n (xF)′=∑n≥1nan−1xn−1(xF)' = \sum\limits_{n \ge 1} n a_{n-1} x^{n-1} (ex)′=ex,ln⁡′(1+x)=∑n≥1(−1)n−1x[n−1]=11+x(e^x)' = e^x, \ln'(1+x) = \sum\limits_{n \ge 1} (-1)^{n-1} x^[n-1] = \frac{1}{1+x} ln⁡′F=F′F\ln' F = \frac{F'}{F} ∫F=∑n≥1fn−1nxn+C\int F = \sum\limits_{n \ge 1} \frac{f_{n-1}}{n} x^n + C
Example\textbf{Example}
令 fn=(2nn)f_n = \binom{2n}{n}，则 fn=2n(2n−1)n2fn−1f_n = \frac{2n(2n-1)}{n^2} f_{n-1}，因此 nfn=4nfn−1−2fn−1n f_n = 4n f_{n-1} - 2 f_{n-1}，考虑 xn−1x^{n-1} 的系数，有 F′=4(xF)′−2FF' = 4(xF)' - 2F F′=4F+4xF′−2F=4xF′+2FF' = 4F + 4xF' - 2F = 4xF' + 2F
因此 ln⁡′F=F′F=21−4x=−12ln⁡′(1−4x)\ln' F = \frac{F'}{F} = \frac{2}{1-4x} = - \frac{1}{2} \ln'(1-4x) F=11−4xF = \frac{1}{\sqrt{1-4x}}
或者，注意到 (−1)n=(−1n)=∑k=0n(−12k)(−12n−k)(-1)^n = \binom{-1}{n} = \sum\limits_{k=0}^n \binom{- \frac{1}{2}}{k} \binom{- \frac{1}{2}}{n-k} =(−14)n∑k=0n(2kk)(2(n−k)n−k)= \left( - \frac{1}{4} \right)^n \sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k}
即 ∑k=0n(2kk)(2(n−k)n−k)=4n\sum\limits_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} = 4^n
也就是 F2=11−4xF^2 = \frac{1}{1-4x}，即 F=11−4xF = \frac{1}{\sqrt{1-4x}}

指数型生成函数 (EGF)(\text{EGF})

对于数列 {fn}\{ f_n \}，定义其 EGF\text{EGF} 为 F(x)=∑i≥0fixii!F(x) = \sum\limits_{i \ge 0} f_i \frac{x^i}{i!}，并对 n∉Nn \notin \mathbb{N}，定义 fn=0f_n = 0。
Example\textbf{Example}
设 G=FexG = F e^x，则有 gn=∑k=0n(nk)fkg_n = \sum\limits_{k=0}^n \binom{n}{k} f_k
同时 F=Ge−xF = G e^{-x}，即 fn=∑k=0n(−1)n−k(nk)gkf_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} g_k
则就是二项式反演
gn=∑k=0n(nk)fk⇔fn=∑k=0n(−1)n−k(nk)fkg_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
Example\textbf{Example}
对错排的 EGF\text{EGF} DD，注意到对于 nn 的每个排列 PP，枚举 ∑i=1n[Pi=i]\sum\limits_{i=1}^n [P_i = i]，就有 ∑k=0n(nk)dn−k=n!\sum\limits_{k=0}^n \binom{n}{k} d_{n-k} = n! Dex=∑n≥0n!n!xn=∑n≥0xn=11−xD e^x = \sum\limits_{n \ge 0} \frac{n!}{n!} x^n = \sum\limits_{n \ge 0} x^n = \frac{1}{1-x} D=e−x1−xD = \frac{e^{-x}}{1-x}
即 dn=n!∑k=0n(−1)kk!d_n = n! \sum\limits_{k=0}^n \frac{(-1)^k}{k!}

矩阵和反演

给定两个 n×nn \times n 的下三角矩阵 AA 和 BB，以及 nn 维多项式向量 PP 和 QQ，其中满足 P=AQ,Q=BPP = AQ, Q = BP
即 pn(x)=∑k=0nan,kqk(x),qn(x)=∑k=0nbn,kpk(x)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}
若 PP 和 QQ 都是向量空间 C[x]\mathbb{C}[x] 的基，那么就有 AB=IAB = I
那么令 ff 和 gg 是两个数列，则有 f=Ag⇔g=Bff = Ag \Leftrightarrow g = Bf
即 ∀n∈N,fn=∑k=0nan,kgk⇔∀n∈N,gn=∑k=0nbn,kfk\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)(1)，能得到二项式反演 fn=∑k=0n(nk)gk⇔gn=∑k=0n(−1)n−k(nk)fkf_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
或者可以表示成 fn=∑k=0n(−1)k(nk)gk⇔gn=∑k=0n(−1)k(nk)fkf_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
Example\textbf{Example}
由于 kn=∑i=0k{ni}(ki)i!k^n = \sum\limits_{i=0}^k {n \brace i} \binom{k}{i} i!
有 k!{nk}=∑i=0n(−1)k−i(ki)ink! {n \brace k} = \sum\limits_{i=0}^n (-1)^{k-i} \binom{k}{i} i^n {nk}=1k!∑i=0n(−1)k−i(ki)in{n \brace k} = \frac{1}{k!} \sum\limits_{i=0}^n (-1)^{k-i} \binom{k}{i} i^n
Example\textbf{Example}
设 f(x)=∑k≥0akxk‾=∑k≥0(xk)k!akf(x) = \sum\limits_{k \ge 0} a_k x^{\underline{k}} = \sum\limits_{k \ge 0} \binom{x}{k} k! a_k
有 f(n)=∑k=0n(nk)k!akf(n) = \sum\limits_{k=0}^n \binom{n}{k} k! a_k n!an=∑k=0n(−1)n−k(nk)f(k)n! a_n = \sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} f(k)
当 deg⁡f<n\deg f < n 时，有 ∑k=0n(−1)n−k(nk)f(k)=0\sum\limits_{k=0}^n (-1)^{n-k} \binom{n}{k} f(k) = 0
例如 ∑k=0n(−1)k(nk)(n+kk)=∑k=0n(nn−k)(−n−1k)=(−1n)=(−1)n\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)=(x+nn)=∑k=0n(xk)(nk)=xn‾n!+⋯f(x) = \binom{x+n}{n} = \sum\limits_{k=0}^n \binom{x}{k} \binom{n}{k} = \frac{x^{\underline{n}}}{n!} + \cdots
那么有 an=1n!a_n = \frac{1}{n!}，因此 ∑k=0n(−1)k(nk)f(k)=(−1)nn!an=(−1)n\sum\limits_{k=0}^n (-1)^k \binom{n}{k} f(k) = (-1)^n n! a_n = (-1)^n

斯特林反演

根据 (2)(2)，有 fn=∑k=0n{nk}gk⇔gn=∑k=0n(−1)n−k[nk]fkf_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
并且有 ∑k≥0(−1)k−m{nk}[km]=[n=m]\sum\limits_{k \ge 0} (-1)^{k-m} {n \brace k} {k \brack m} = [n = m]

概率生成函数 (PGF)(\text{PGF})

给定随机变量 X:Ω→NX:\Omega \to \mathbb{N}，设 pn=Prob⁡(X=n)p_n = \operatorname{Prob}(X = n)，那么 XX 的 PGF\text{PGF} 为 PX=∑n≥0pnxnP_X = \sum\limits_{n \ge 0} p_n x^n
这个函数的所有系数都非负，且 PX(1)=1P_X(1)=1。
定义 XX 的期望值为 EX=∑n≥0npn=PX′(1)\mathbb{E} X = \sum\limits_{n \ge 0} n p_n = P'_X(1)
定义 XX 的方差为 Var⁡X=EX2−E2X\operatorname{Var} X = \mathbb{E} X^2 - \mathbb{E}^2 X
注意到 PX′′=∑n≥2n(n−1)pnxn−2=∑n≥2n2pnxn−2−∑n≥2npnxn−2=EX2−EXP''_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
因此 Var⁡X=PX′′(1)+PX′(1)−PX′2(1)\operatorname{Var} X = P''_X(1) + P'_X(1) - P'^2_X(1)
Example\textbf{Example}
令 Ω=S(n),Xn(π)=inv⁡(π)\Omega = S(n), X_n(\pi) = \operatorname{inv}(\pi)，设 In,k=∑P∈S(n)[inv⁡P=k]I_{n,k} = \sum\limits_{P \in S(n)} [\operatorname{inv} P = k]，则有 PXn=∑k≥0In,kn!xkP_{X_n} = \sum\limits_{k \ge 0} \frac{I_{n,k}}{n!} x^k
又因为 In,k=∑i=0n−1In−1,k−iI_{n,k} = \sum\limits_{i=0}^{n-1} I_{n-1,k-i}
因此 PXn=1−xn(1−x)nPXn−1P_{X_n} = \frac{1 - x^n}{(1-x)n} P_{X_{n-1}}
又有 PX1=1P_{X_1} = 1，因此 PXn=∏i=1n1+x+x2+⋯+xi−1iP_{X_n} = \prod\limits_{i=1}^n \frac{1 + x + x^2 + \cdots + x^{i-1}}{i} PXn′=∑i=1n(∏1≤j≤n,j≠i1+x+⋯xj−1j)1+2x+3x2+⋯+(i−1)xi−2iP'_{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} EXn=PXn′(1)=∑i=1ni−12=n(n−1)4\mathbb{E} X_n = P'_{X_n}(1) = \sum\limits_{i=1}^n \frac{i-1}{2} = \frac{n(n-1)}{4} Var⁡Xn=n(n−1)(2n+5)72\operatorname{Var} X_n = \frac{n(n-1)(2n+5)}{72}

随机游走

给定一个数轴，一个点一开始在 00，每次会等概率的选择向左或右有一步，对于一个 m∈N+m \in \mathbb{N_+}，问到达 mm 或 −m-m 的概率，以及期望多少步才能到。
令 gm,ng_{m,n} 表示有多少个路线使得在第 nn 步第一次到达 mm 或 −m-m，那么有 PX=Gm(x2)P_X = G_m(\frac{x}{2}) EX=12Gm′(12)\mathbb{E} X = \frac{1}{2} G'_m (\frac{1}{2})
定义正游走表示走过的所有坐标都非负，令 em,ne_{m,n} 表示在第 nn 步时第一次到达 00，且从未到过 mm 的正游走数，e˙m,n\dot e_{m,n} 则不需要保证是第一次到达 00。有 em,0=0,e˙m,0=1e_{m,0} = 0, \dot e_{m,0} = 1，而 e˙m,n=∑k=1nem,ke˙m,n−k\dot e_{m,n} = \sum\limits_{k=1}^n e_{m,k} \dot e_{m,n-k} E˙m=EmE˙m+1\dot E_m = E_m \dot E_m + 1
E˙m=11−Em\dot E_m = \frac{1}{1 - E_m}
同时，去掉第一步和第 nn 步，就有 em,n=e˙m−1,n−2e_{m,n} = \dot e_{m-1,n-2} Em=x2E˙m−1=x21−Em−1E_m = x^2 \dot E_{m-1} = \frac{x^2}{1 - E_{m-1}}
而 E1=0E_1 = 0，那么设 Am=Em(12)A_m = E_m(\frac{1}{2})，就有 Am=14(1−Am−1)A_m = \frac{1}{4(1 - A_{m-1})} Am=m−12mA_m = \frac{m-1}{2m}
并设 Bm=Em′(12)B_m = E'_m(\frac{1}{2})，有 Bm=2(m2−1)3mB_m = \frac{2(m^2-1)}{3m}
现在设 fm,nf_{m,n} 表示在第 nn 步第一次到 mm 的正游走数，枚举最后一次到达 00 的时间，有 fm,n=∑k=1nem,kfm,n−k+fm−1,n−1f_{m,n} = \sum\limits_{k=1}^n e_{m,k} f_{m,n-k} + f_{m-1,n-1} Fm=EmFm+xFm−1F_m = E_m F_m + x F_{m-1}
其中 F1=xF_1 = x
设 Um=Fm(12),Vm=Fm′(12)U_m = F_m(\frac{1}{2}), V_m = F'_m(\frac{1}{2})，能得到 Um=1m+1,Vm=2m(m+2)3(m+1)U_m = \frac{1}{m+1}, V_m = \frac{2m(m+2)}{3(m+1)}
最后考虑计算 GG，枚举最后一次回到 00 的时间，就有 gm,n=2(∑k=1nem,kgm,n−k+fm−1,n−1)g_{m,n} = 2 \left( \sum\limits_{k=1}^n e_{m,k} g_{m,n-k} + f_{m-1,n-1} \right) Gm=2(EmGm+xFm−1)G_m = 2(E_m G_m + x F_{m-1})
因此 Gm=2xFm−11−2EmG_m = \frac{2x F_{m-1}}{1 - 2 E_m} PX(1)=Gm(12)=Um−11−2Am=1m(1−m−1m)=1P_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 EX=12Gm′(12)=(Um−1+12Vm−1)(1−2Am)+Um−1Bm(1−2Am)2=m2\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

斐波那契游走

现在考虑一个新的随机游走，从 11 开始，每次会等概率选择向左走 11 步或向右走两步，问到 00 的概率。
令 fm,nf_{m,n} 表示从 mm 开始，走 nn 步第一次到 00 的游走数，那么从 m+1m+1 开始，显然要先到 mm，枚举第一次到 mm 的时间，有 fm+1,n=∑k=0nf1,kfm,n−kf_{m+1,n} = \sum\limits_{k=0}^n f_{1,k} f_{m,n-k} Fm+1=F⋅FmF_{m+1} = F \cdot F_m
因此 Fm=FmF_m = F^m
考虑第一次是向左还是向右，就有 F=x+xF3F = x + x F^3
而答案为 p=F(12)p = F(\frac{1}{2})，所以 p=12+12p3p = \frac{1}{2} + \frac{1}{2} p^3 p3−2p+1=(p−1)(p2+p−1)=0p^3 - 2p + 1 = (p-1)(p^2+p-1) = 0
因此 p=1p=1 或 p=5−12p = \frac{\sqrt{5} - 1}{2} 或 p=−5−12p = \frac{- \sqrt{5} - 1}{2}。显然 p≥0p \ge 0，因此 p≠−5−12p \ne \frac{- \sqrt{5} - 1}{2}，又有 FF 在区间 [0,12][0, \frac{1}{2}] 单调递增（因为 x<12x < \frac{1}{2} 相当于有概率原地暴毙），因此 F′(12)≥0F'(\frac{1}{2}) \ge 0，而 F′=1+F3+3xF2F′F' = 1 + F^3 + 3x F^2 F' F′=1+F31−3xF2F' = \frac{1 + F^3}{1 - 3x F^2}
如果 F(12)=1F(\frac{1}{2})=1，有 F′(12)=21−32=−4<0F'(\frac{1}{2}) = \frac{2}{1 - \frac{3}{2}} = -4 < 0
因此 p=5−12p = \frac{\sqrt{5} - 1}{2}，而 pm=(5−12)mp_m = \left( \frac{\sqrt{5} - 1}{2} \right)^m。

数论函数

对一个定义域为 N+\mathbb{N_+}，值域为 C\mathbb{C} 的函数，我们称其为数论函数。
若无特殊定义，默认所有变量都为正整数，pp 为质数，kk 为 nn 的不同质因数的个数，pip_i 为 nn 第 ii 大的质因数，n=∏i=1kpicin = \prod\limits_{i=1}^k p_i^{c_i}。

莫比乌斯函数

定义莫比乌斯函数 μ(n)\mu(n) 满足：μ(1)=1\mu(1) = 1，对 n>1n>1 ，若 ∀1≤i≤k,ai=1\forall 1 \le i \le k, a_i = 1，则 μ(n)=(−1)k\mu(n) = (-1)^k，否则 μ(n)=0\mu(n) = 0。也就是说 μ(n)=0\mu(n) = 0 当且仅当 nn 有一个 >1>1 的平方因子。

Theorem.1\text{Theorem.1}

∑d∣nμ(d)=[n=1]\sum\limits_{d \mid n} \mu(d) = [n=1]
Proof:\textbf{Proof:}
令 n>1n > 1，显然 μ(d)≠0\mu(d) \ne 0 当且仅当 dd 可以表示成 ∏i=1k′pai\prod\limits_{i=1}^{k'} p_{a_i}，其中 ∀1≤i<k′,ai<ai+1\forall 1 \le i < k', a_i < a_{i+1}，因此 ∑d∣nμ(d)=1+μ(p1)+μ(p2)+⋯+μ(p1p2)+⋯+μ(p1p2⋯pk)\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) =∑i=0k(ki)(−1)i=0= \sum\limits_{i=0}^k \binom{k}{i} (-1)^i = 0

欧拉函数

定义欧拉函数 φ(n)\varphi(n) 为有多少个不超过 nn 的正整数和 nn 互质，即 φ(n)=∑k=1n[gcd⁡(k,n)=1]\varphi(n) = \sum\limits_{k=1}^n [\gcd(k,n) = 1]

Theorem.2\text{Theorem.2}

∑d∣nφ(d)=n\sum\limits_{d \mid n} \varphi(d) = n
Proof:\textbf{Proof:}
设 A(d)={k∣gcd⁡(k,n)=d,1≤k≤n}A(d) = \{ k \mid \gcd(k,n) = d, 1 \le k \le n \}
显然对 nn 的所有因数 dd，A(d)A(d) 恰好遍历了所有不超过 nn 的正整数，因此 ∑d∣n∣A(d)∣=n\sum\limits_{d \mid n} |A(d)| = n ∑d∣nφ(nd)=n\sum\limits_{d \mid n} \varphi(\frac{n}{d}) = n ∑d∣nφ(d)=n\sum\limits_{d \mid n} \varphi(d) = n

Theorem.3\text{Theorem.3}

φ(n)=∑d∣nμ(d)nd\varphi(n) = \sum\limits_{d \mid n} \mu(d) \frac{n}{d}
Proof:\textbf{Proof:}
φ(n)=∑k=1n[gcd⁡(n,k)=1]=∑k=1n∑d∣gcd⁡(n,k)μ(d)=∑k=1n∑d∣n,d∣kμ(d)\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) =∑d∣n∑k=1n/dμ(d)=∑d∣nμ(d)nd= \sum\limits_{d \mid n} \sum\limits_{k=1}^{n/d} \mu(d) = \sum\limits_{d \mid n} \mu(d) \frac{n}{d}

Theorem.4\text{Theorem.4}

φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod\limits_{p \mid n} (1 - \frac{1}{p})
Proof:\textbf{Proof:}
∏p∣n(1−1p)=1−1p1−1p2−⋯+1p1p2+⋯+(−1)kp1p2⋯pk=∑d∣nμ(d)d=1nφ(n)\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)

Theorem.5\text{Theorem.5}

\varphi(p^c) = p^c - p^{c-1} \tag{1}
Proof:\textbf{Proof:}
根据定义或公式即可证明。
\varphi(nm) = \varphi(n) \varphi(m) \frac{\gcd(n,m)}{\varphi(\gcd(n,m))} \tag{2}
Proof:\textbf{Proof:}
φ(nm)nm=∏p∣nm(1−1p)=∏p∣n(1−1p)∏p∣m(1−1p)∏p∣gcd⁡(n,m)(1−1p)=φ(n)nφ(m)mφ(d)d\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}}
即 φ(nm)=φ(n)φ(m)gcd⁡(n,m)φ(gcd⁡(n,m))\varphi(nm) = \frac{\varphi(n) \varphi(m) \gcd(n,m)}{\varphi(\gcd(n,m))}
若 gcd⁡(n,m)=1\gcd(n,m) = 1，则 \varphi(nm) = \varphi(n) \varphi(m) \tag{3}
Proof:\textbf{Proof:}
根据 (2)(2) 即可证明。
n \mid m \Rightarrow \varphi(n) \mid \varphi(m) \tag{4}
Proof:\textbf{Proof:}
显然当 n=1n=1 时结论成立，否则对 mm 归纳，设 k=mnk = \frac{m}{n}，则 φ(m)=φ(nk)=φ(n)φ(k)gcd⁡(n,m)φ(gcd⁡(n,k))=gcd⁡(n,k)φ(n)φ(k)φ(gcd⁡(n,k))\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<mk<m，因此 φ(gcd⁡(n,k))∣φ(k)\varphi(\gcd(n,k)) \mid \varphi(k)，所以 φ(n)∣φ(m)\varphi(n) \mid \varphi(m)。
若 n≥3n \ge 3，则 2∣φ(n)2 \mid \varphi(n)，且若 nn 有 kk 个奇质因数，则 2^k \mid \varphi(n) \tag{5}
Proof:\textbf{Proof:}
φ(n)=n∏p∣np−1p=n∏p∣np∏p∣n(p−1)\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≥3n \ge 3 时，若 4∣n4 \mid n，则 2∣n∏p∣np2 \mid \frac{n}{\prod\limits_{p \mid n} p}，否则 nn 有一个奇的质因数，因此 2∣∏p∣n(p−1)2 \mid \prod\limits_{p \mid n} (p-1)，进一步的，2k∣∏p∣n(p−1)2^k \mid \prod\limits_{p \mid n} (p-1)，即 2k∣φ(n)2^k \mid \varphi(n)。

迪利克雷卷积

定义两个数论函数 ff 和 gg 的迪利克雷卷积为 (f∗g)(n)=∑d∣nf(d)g(nd)(f*g)(n) = \sum\limits_{d \mid n} f(d) g(\frac{n}{d})
例如 Theorem.1\text{Theorem.1} 可以表示为 ε=μ∗I\varepsilon = \mu * I
Theorem.3\text{Theorem.3} 可以表示为 φ=μ∗id\varphi = \mu * \text{id}

Theorem.6\text{Theorem.6}

f*g = g*f \tag{1}
Proof:\textbf{Proof:}
(f∗g)(n)=∑d∣nf(d)g(nd)=(g∗f)(n)(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}
Proof:\textbf{Proof:}
f∗(g∗h)=∑abc=nf(a)g(b)h(c)=(f∗g)∗hf*(g*h) = \sum\limits_{abc=n} f(a) g(b) h(c) = (f*g)*h

Theorem.7\text{Theorem.7}

f∗ε=ε∗f=ff * \varepsilon = \varepsilon * f = f
Proof:\textbf{Proof:}
(f∗ε)(n)=∑d∣nf(d)ε(nd)=∑d∣nf(d)[n=d]=f(n)(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)
反之同理。

Theorem.8\text{Theorem.8}

对 f(1)≠0f(1) \ne 0，存在 f−1f^{-1} 使得 f∗f−1=f−1∗f=εf * f^{-1} = f^{-1} * f = \varepsilon
Proof:\textbf{Proof:}
由于 (f∗f−1)(1)=ε(1)(f * f^{-1})(1) = \varepsilon(1)，因此 f(1)f−1(1)=1f(1) f^{-1}(1) = 1，而对 n>1n>1，有 ∑d∣nf(nd)f−1(d)=0\sum\limits_{d \mid n} f(\frac{n}{d}) f^{-1}(d) = 0 f(1)f−1(n)+∑d∣n,d<nf(nd)f−1(d)=0f(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∑d∣n,d<nf(nd)f−1(d)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(f*g)^{-1} = f^{-1} * g^{-1}
证明不难。

Theorem.9\text{Theorem.9}

有莫比乌斯反演 f(n)=∑d∣ng(d)⇒g(n)=∑d∣nf(d)μ(nd)f(n) = \sum\limits_{d \mid n} g(d) \Rightarrow g(n) = \sum\limits_{d \mid n} f(d) \mu(\frac{n}{d})
Proof:\textbf{Proof:}
f=g∗I⇒f∗μ=(g∗I)∗μ=g∗(I∗μ)=g∗ε=gf = g * I \Rightarrow f * \mu = (g * I) * \mu = g * (I * \mu) = g * \varepsilon = g
同时可以借此由 Theorem.2\text{Theorem.2} 推导出 Theorem.3\text{Theorem.3}： n=∑d∣nφ(d)⇒φ(n)=∑d∣nμ(d)ndn = \sum\limits_{d \mid n} \varphi(d) \Rightarrow \varphi(n) = \sum\limits_{d \mid n} \mu(d) \frac{n}{d}

曼戈尔特函数

定义曼戈尔特函数 Λ(n)\Lambda(n) 满足：若 k=1k=1，则 Λ(n)=c1\Lambda(n) = c_1，否则 Λ(n)=0\Lambda(n) = 0。

Theorem.10\text{Theorem.10}

log⁡n=∑d∣nΛ(d)\log n = \sum\limits_{d \mid n} \Lambda(d)
Proof:\textbf{Proof:}
∑d∣nΛ(d)=∑i=1k∑j=1ciΛ(pij)=∑i=1k∑j=1cilog⁡pi=∑k=1kcilog⁡pi=log⁡n\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

Theorem.11\text{Theorem.11}

Λ(n)=∑d∣nμ(d)log⁡nd=−∑d∣nμ(d)log⁡(d)\Lambda(n) = \sum\limits_{d \mid n} \mu(d) \log \frac{n}{d} = - \sum\limits_{d \mid n} \mu(d) \log(d)
Proof:\textbf{Proof:}
对 Theorem.10\text{Theorem.10} 莫比乌斯反演，有 Λ(n)=∑d∣nμ(d)log⁡nd=log⁡n∑d∣nμ(d)−∑d∣nμ(d)log⁡d=ε(n)log⁡n−∑d∣nμ(d)log⁡d\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
显然 ε(n)\varepsilon(n) 和 log⁡n\log n 不同时非 00，因此可以证明。

积性函数

称 ff 为积性函数当且仅当 ∀gcd⁡(n,m)=1,f(nm)=f(n)f(m)\forall \gcd(n,m) = 1, f(nm) = f(n) f(m)
称积性函数 ff 为完全积性函数当且仅当 ∀n,m,f(nm)=f(n)f(m)\forall n,m, f(nm) = f(n) f(m)
例如 ida\text{id}_a 和 ε\varepsilon 就是完全积性函数，而 μ\mu 和 φ\varphi 则是积性函数。
对积性函数 ff 和 gg，有 fgf g 和 fg\frac{f}{g} 都是积性函数。

Theorem.12\text{Theorem.12}

ff 是积性函数仅当 f(1)=1f(1) = 1。
Proof:\textbf{Proof:}
因为 gcd⁡(1,n)=1\gcd(1,n) = 1，因此 f(n)=f(1)f(n)f(n) = f(1) f(n)，而 ff 不全为 00，因此 f(1)=1f(1) = 1。

Theorem.13\text{Theorem.13}

令 f(1)=1f(1) = 1，则
ff 是积性函数当且仅当 f(n)=∏i=1kf(pici)f(n) = \prod\limits_{i=1}^k f(p_i^{c_i})
积性函数 ff 是完全积性函数当且仅当 f(pc)=f(p)cf(p^c) = f(p)^c

Theorem.14\text{Theorem.14}

对积性函数 ff 和 gg，有 f∗gf*g 也是积性函数。
Proof:\textbf{Proof:}
设 h=f∗gh=f*g，则 h(nm)=∑c∣nmf(c)g(nmc)h(nm) = \sum\limits_{c \mid nm} f(c) g(\frac{nm}{c})
显然对每个 cc 都能将其分解称 abab 使得 a∣n,b∣m,gcd⁡(a,b)=1,gcd⁡(na,mb)=1a \mid n, b \mid m, \gcd(a,b) = 1, \gcd(\frac{n}{a}, \frac{m}{b}) = 1
因此 h(nm)=∑a∣n,b∣mf(ab)g(nmab)=∑a∣n,b∣mf(a)f(b)g(na)g(mb)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}) =(∑a∣nf(a)g(na))(∑b∣mf(b)g(mb))=h(n)h(m)= \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)

Theorem.15\text{Theorem.15}

若 gg 和 f∗gf*g 都是积性函数，则 ff 也是。
Proof:\textbf{Proof:}
假设 ff 不为积性函数，那么 ∃gcd⁡(n,m)=1\exists \gcd(n,m) = 1
若 n=m=1n=m=1，则 f(1)≠f(1)f(1)f(1) \ne f(1) f(1)，因此 f(1)≠1f(1) \ne 1，因此 h(1)=f(1)g(1)≠1h(1) = f(1) g(1) \ne 1
否则有 ∀gcd⁡(a,b)=1,ab<nm,f(ab)=f(a)f(b)\forall \gcd(a,b) = 1, ab < nm, f(ab) = f(a) f(b)
那么 h(nm)=∑a∣n,b∣m,ab<nmf(ab)g(nmab)+f(nm)g(1)h(nm) = \sum\limits_{a \mid n, b \mid m, ab < nm} f(ab) g(\frac{nm}{ab}) + f(nm) g(1) =∑a∣n,b∣m,ab<nmf(a)f(b)g(na)g(mb)+f(nm)= \sum\limits_{a \mid n, b \mid m, ab < nm} f(a) f(b) g(\frac{n}{a}) g(\frac{m}{b}) + f(nm) =(∑a∣nf(a)g(na))(∑b∣mf(b)g(mb))−f(n)f(m)+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)= h(n) h(m) - f(n) f(m) + f(nm)
又因为 f(nm)≠f(n)f(m)f(nm) \ne f(n) f(m)，因此 h(nm)≠h(n)h(m)h(nm) \ne h(n) h(m)，因此 hh 不是积性函数，与原命题相悖。

Theorem.16\text{Theorem.16}

若 ff 是积性函数，那么 f−1f^{-1} 也是。
Proof:\textbf{Proof:}
由于 g∗g−1=εg * g^{-1} = \varepsilon 为积性函数，那么根据 Theorem.15\text{Theorem.15} 即可证明。

Theorem.17\text{Theorem.17}

若 ff 是积性函数，那么 ff 是完全积性函数当且仅当 f−1=μff^{-1} = \mu f
Proof:\textbf{Proof:}
令 g=fμg = f \mu，若 ff 为完全积性函数，那么有 (f∗g)(n)=∑d∣nμ(d)f(d)f(nd)=f(n)∑d∣n=(fε)(n)=ε(n)(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=μff^{-1} = \mu f，那么有 ∀n>1,∑d∣nμ(d)f(d)f(nd)=0\forall n > 1, \sum\limits_{d \mid n} \mu(d) f(d) f(\frac{n}{d}) = 0
令 n=pcn = p^c，则有 μ(1)f(1)f(p)c+μ(p)f(p)f(pc−1)=0\mu(1) f(1) f(p)^c + \mu(p) f(p) f(p^{c-1}) = 0 f(pc)=f(p)f(pc−1)f(p^c) = f(p) f(p^{c-1}) f(pc)=f(p)cf(p^c) = f(p)^c
因此 ff 为完全积性函数。
Example\textbf{Example}
因为 φ=μ∗id\varphi = \mu * \text{id}，而 id\text{id} 是完全积性函数，因此 φ−1=μ−1∗id−1=μ−1∗μid=I∗μid\varphi^{-1} = \mu^{-1} * id^{-1} = \mu^{-1} * \mu id = I * \mu \text{id}
即 φ−1(n)=∑d∣ndμ(d)\varphi^{-1}(n) = \sum\limits_{d \mid n} d \mu(d)

Theorem.18\text{Theorem.18}

令 ff 为积性函数，有 ∑d∣nμ(d)f(d)=∏p∣n(1−f(p))\sum\limits_{d \mid n} \mu(d) f(d) = \prod\limits_{p \mid n} (1 - f(p))
Proof:\textbf{Proof:}
设 g=μfg = \mu f，则 g(pc)=∑d∣pcμ(d)f(d)=μ(1)f(1)+μ(p)f(p)=1−f(p)g(p^c) = \sum\limits_{d \mid p^c} \mu(d) f(d) = \mu(1) f(1) + \mu(p) f(p) = 1 - f(p)
而 gg 是积性函数，因此 g(n)=∏p∣ng(pc)=∏p∣n(1−f(p))g(n) = \prod\limits_{p \mid n} g(p^c) = \prod\limits_{p \mid n} (1 - f(p))

刘维尔函数

定义刘维尔函数 λ(n)\lambda(n) 满足 λ(n)=(−1)∑i=1kci\lambda(n) = (-1)^{\sum\limits_{i=1}^k c_i}

Theorem.19\text{Theorem.19}

∑d∣nλ(d)=[n is a square]\sum\limits_{d \mid n} \lambda(d) = [n \text{ is a square}]
同时有 λ−1=∣μ∣\lambda^{-1} = |\mu|
Proof:\textbf{Proof:}
设 f=1∗λf = 1 * \lambda，那么 g(pc)=∑d∣pcλ(d)=∑i=0c(−1)i=[2∣c]g(p^c) = \sum\limits_{d \mid p^c} \lambda(d) = \sum\limits_{i=0}^c (-1)^i = [2 \mid c]
而 ff 是积性函数，因此 g(n)=∏i=1kg(pc)=[∀1≤i≤k,2∣i]=[n is a square]g(n) = \prod\limits_{i=1}^k g(p^c) = [\forall 1 \le i \le k, 2 \mid i] = [n \text{ is a square}]
同时 λ−1=μλ=μ2=∣μ∣\lambda^{-1} = \mu \lambda = \mu^2 = |\mu|。

因数函数

对复数 α\alpha，设 σα(n)=∑d∣ndα\sigma_{\alpha}(n) = \sum\limits_{d \mid n} d^{\alpha}
而 σα(pc)=∑i=0cpiα=pα(c+1)−1pα−1\sigma_{\alpha}(p^c) = \sum\limits_{i=0}^c p^{i \alpha} = \frac{p^{\alpha (c+1)} - 1}{p^{\alpha} - 1}

Theorem.20\text{Theorem.20}

σα−1(n)=∑d∣ndαμ(d)μ(nd)\sigma_{\alpha}^{-1}(n) = \sum\limits_{d \mid n} d^{\alpha} \mu(d) \mu(\frac{n}{d})
Proof:\textbf{Proof:}
由于 σα=idα∗1\sigma_{\alpha} = \text{id}_{\alpha} * 1 且 idα\text{id}_{\alpha} 是完全积性函数，因此 σα−1=μidα∗I−1=μidα∗μ\sigma_{\alpha}^{-1} = \mu \text{id}_{\alpha} * I^{-1} = \mu \text{id}_{\alpha} * \mu

广义卷积

对定义在正实数域上的函数 FF 满足 ∀0<x<1,F(x)=0\forall 0 < x < 1, F(x) = 0，和数论函数 ff，定义他们的广义卷积为 (f∘F)(x)=∑n≤xf(n)F(xn)(f \circ F)(x) = \sum\limits_{n \le x} f(n) F(\frac{x}{n})

Theorem.21\text{Theorem.21}

f∘(g∘F)=(f∗g)∘Ff \circ (g \circ F) = (f * g) \circ F
Proof:\textbf{Proof:} (f∘(g∘F))(x)=∑n≤xf(n)∑m≤xng(m)F(xnm)=∑nm≤xf(n)g(m)F(xnm)(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}) =∑n≤x(∑k∣nf(k)g(nk))F(xn)=∑n≤x(f∗g)(n)F(xn)=((f∗g)∘F)(x)= \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)
那么有 (ε∘F)(x)=∑n≤x[n=1]F(xn)=F(x)(\varepsilon \circ F)(x) = \sum\limits_{n \le x} [n = 1] F(\frac{x}{n}) = F(x)
即 ε\varepsilon 也是 ∘\circ 的单位元。

Theorem.22\text{Theorem.22}

G=f∘F⇔F=f−1∘GG = f \circ F \Leftrightarrow F = f^{-1} \circ G
Proof:\textbf{Proof:}
证明不难。

Theorem.23\text{Theorem.23}

若 ff 为完全积性函数，则 G=f∘F⇔F=(μf)∘GG = f \circ F \Leftrightarrow F = (\mu f) \circ G
Proof:\textbf{Proof:}
f−1=μff^{-1} = \mu f
未完待续（但是应该不会更新了）。
一些习题
习题（带答案），如果有错误的地方欢迎指正。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...