专栏文章

各种反演

yyemuzhe
算法·理论参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
2 份
快照标识符
@mj34y5fj
此快照首次捕获于
2025/12/13 01:23
3 个月前
此快照最后确认于
2025/12/15 01:30
3 个月前
查看原文

子集反演

公式

G _ S = \sum _ {T \subseteq S} F _ T \Longleftrightarrow F _ S = \sum _ {T \subseteq S} (-1) ^ {|S| - |T|} G _ T \tag {1}
G _ S = \sum _ {T \supseteq S} F _ T \Longleftrightarrow F _ S = \sum _ {T \supseteq S} (-1) ^ {|T| - |S|} G _ T \tag {2}

证明

对于 (1)(1) 式，考虑
FS=∑T⊆S(−1)∣S∣−∣T∣∑U⊆TFU=∑U⊆S∑U⊆T⊆S(−1)∣S∣−∣T∣=∑U⊆S∑i=∣U∣∣S∣(−1)∣S∣−i(∣S∣−∣U∣∣S∣−i)=∑U⊆S(1−1)∣S∣−∣U∣=∑U⊆S[∣S∣−∣U∣=0]=FS\begin {align*} F _ S & = \sum _ {T \subseteq S} (-1) ^ {|S| - |T|} \sum _ {U \subseteq T} F _ U \\ & = \sum _ {U \subseteq S} \sum _ {U \subseteq T \subseteq S} (-1) ^ {|S| - |T|} \\ & = \sum _ {U \subseteq S} \sum _ {i = |U|} ^ {|S|} (-1) ^ {|S| - i} \binom {|S| - |U|} {|S| - i}\\ & = \sum _ {U \subseteq S} (1 - 1) ^ {|S| - |U|} \\ & = \sum _ {U \subseteq S} [|S| - |U| = 0] \\ &= F _ S \end {align*}
故原式成立。
对于 (2)(2) 式证明同理。

二项式反演

公式

G _ i = \sum _ {j = 0} ^ i \binom i j F _ j \Longleftrightarrow F _ i = \sum _ {j = 0} ^ i (-1) ^ {i - j} \binom i j G _ j \tag {3}
G _ i = \sum _ {j = i} ^ n \binom j i F _ j \Longleftrightarrow F _ i = \sum _ {j = i} ^ n (-1) ^ {j - i} \binom j i G _ j \tag {4}

证明

其实就是子集反演的特殊情况。

推导

对于 (3)(3) 式，令 f(x)=∑n=0Fnn!xnf (x) = \sum _ {n = 0} \frac {F _ n} {n!} x ^ n，g(x)=∑n=0Gnn!xng (x) = \sum _ {n = 0} \frac {G _ n} {n!} x ^ n，因为
Gi=∑j=0i(ij)Fj=∑j=0ii!j!(i−j)!FjG _ i = \sum _ {j = 0} ^ i \binom i j F _ j = \sum _ {j = 0} ^ i \frac {i!} {j! (i - j)!} F _ j
Gii!=∑j=0i1(i−j)!⋅Fjj!\frac {G _ i} {i!} = \sum _ {j = 0} ^ i \frac 1 {(i - j)!} \cdot \frac {F _ j} {j!}
有
g(x)=f(x)⋅∑n=0xnn!=f(x)⋅exg (x) = f (x) \cdot \sum _ {n = 0} \frac {x ^ n} {n!} = f (x) \cdot e ^ x
故
f(x)=g(x)ex=g(x)⋅e−xf (x) = \frac {g (x)} {e ^ x} = g (x) \cdot e ^ {-x}
展开后
Fii!=∑j=0i(−1)i−j(i−j)!⋅Gjj!\frac {F _ i} {i!} = \sum _ {j = 0} ^ i \frac {(-1) ^ {i - j}} {(i - j)!} \cdot \frac {G _ j} {j!}
Fi=∑j=0i(−1)i−j(ij)GjF _ i = \sum _ {j = 0} ^ i (-1) ^ {i - j} \binom i j G _ j
(3)(3) 式得证，同理由 (4)(4) 式
Gi=∑j=in(ji)FjG _ i = \sum _ {j = i} ^ n \binom j i F _ j
设 f(x)=∑n=0Fnn!xnf (x) = \sum _ {n = 0} F _ n n! x ^ n，g(x)=∑n=0Gnn!xng (x) = \sum _ {n = 0} G _ n n! x ^ n，有
g(x)=f(x)⋅∑n=0x−nn!=f(x)⋅e1xg (x) = f (x) \cdot \sum _ {n = 0} \frac {x ^ {-n}} {n!} = f (x) \cdot e ^ {\frac 1 x}
则
g(x)=f(x)⋅e−1xg (x) = f (x) \cdot e ^ {-\frac 1 x}
展开后
Fi=∑j=in(−1)j−i(ji)GjF _ i = \sum _ {j = i} ^ n (-1) ^ {j - i} \binom j i G _ j
(4)(4) 式得证。

单位根反演

公式

[k | n] = \frac 1 k \sum _ {i = 0} ^ {k - 1} \omega _ k ^ {in} \tag {5}

证明

若 k∣nk | n，则 ωkn=1\omega _ k ^ n = 1，有
1k∑i=0k−1ωkin=1k∑i=0k−1(ωkn)i=1k∑i=0k−11=1k⋅k=1\frac 1 k \sum _ {i = 0} ^ {k - 1} \omega _ k ^ {in} = \frac 1 k \sum _ {i = 0} ^ {k - 1} (\omega _ k ^ n) ^ i = \frac 1 k \sum _ {i = 0} ^ {k - 1} 1 = \frac 1 k \cdot k = 1
否则因为 ωkkn=1\omega _ k ^ {kn} = 1，有
1k∑i=0k−1ωkin=1k⋅1−ωkkn1−ωkn=0\frac 1 k \sum _ {i = 0} ^ {k - 1} \omega _ k ^ {in} = \frac 1 k \cdot \frac {1 - \omega _ k ^ {kn}} {1 - \omega _ k ^ n} = 0
原式得证。

莫比乌斯反演

公式

G _ i = \sum _ {j | i} F _ j \Longleftrightarrow F _ i = \sum _ {j | i} \mu \left(\frac i j\right) G _ j \tag {6}
或者也有另外一种形式
I * \mu = \epsilon \tag {7}
即
[i = 1] = \sum _ {j | i} \mu (j) \tag {8}

证明

对于 (8)(8) 式，考虑 ii 的每一个质因数 p1c1,p2c2,…,pkckp _ 1 ^ {c _ 1}, p _ 2 ^ {c _ 2}, \ldots, p _ k ^ {c _ k}，记 i′=p1p2⋯pki ^ \prime = p _ 1 p _ 2 \cdots p _ k，则
∑j∣iμ(j)=∑j∣i′μ(j)=∑i=0k(ki)(−1)i=(1−1)k=[k=0]=[n=1]\sum _ {j | i} \mu (j) = \sum _ {j | i ^ \prime} \mu (j) = \sum _ {i = 0} ^ k \binom k i (-1) ^ i = (1 - 1) ^ k = [k = 0] = [n = 1]
故 (8)(8) 成立，考虑证明 (6)(6)：
Fi=∑j∣iμ(ij)∑k∣jFk=∑k∣iFk∑k∣j∣iμ(ij)=∑k∣iFk∑ij∣ikμ(ij)=∑k∣iFk[ik=1]=Fi\begin {align*} F _ i & = \sum _ {j | i} \mu \left (\frac i j\right) \sum _ {k | j} F _ k \\ & = \sum _ {k | i} F _ k \sum _ {k | j | i} \mu \left(\frac i j\right) \\ & = \sum _ {k | i} F _ k \sum _ {\frac i j | \frac i k} \mu \left(\frac i j\right) \\ & = \sum _ {k | i} F _ k \left[\frac i k = 1\right] \\ &= F _ i \end {align*}
证毕。

欧拉反演

公式

I * \varphi = id \tag {9}
即
i = \sum _ {j | i} \varphi (j) \tag {10}

证明

i=∑k=1i1=∑k=1i∑j=1i[gcd⁡(i,k)=j]=∑j∣i∑k=1i[gcd⁡(i,k)=j]=∑j∣i∑k=1ij[gcd⁡(ij,k)=1]=∑j∣iφ(ij)=∑j∣iφ(j)\begin {align*} i & = \sum _ {k = 1} ^ i 1 \\ & = \sum _ {k = 1} ^ i \sum _ {j = 1} ^ i [\gcd (i, k) = j] \\ & = \sum _ {j | i} \sum _ {k = 1} ^ i [\gcd (i, k) = j] \\ & = \sum _ {j | i} \sum _ {k = 1} ^ {\frac i j} \left[\gcd \left(\frac i j, k\right) = 1\right] \\ & = \sum _ {j | i} \varphi \left(\frac i j\right) \\ & = \sum _ {j | i} \varphi (j) \end {align*}

拉格朗日反演

见此

评论

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

正在加载评论...