数学小记

标签：sum mu 反演 数学 choose Leftrightarrow subseteq 小记

发现自己数学好菜好菜 =_=

反演

莫比乌斯反演

莫比乌斯函数

\[\mu(n)= \begin{cases} 1 , &n=1 \\ (-1)^r, & n=p_1p_2 … p_r \\ 0 , & else \end{cases} \]

莫比乌斯反演的一般形式

\[f(n)=\sum_{d|n} g(d) \Leftrightarrow g(n)=\sum_{d|n} \mu(d)f({n \over d}) \]

\[f(n)=\sum_{n|d} g(d) \Leftrightarrow g(n)=\sum_{n|d} \mu(d)f({d \over n}) \]

本质上是在狄拉克雷卷积下，\(\mu\) 的逆元为 \(\epsilon\)
常用的关于 \(\mu\) 的结论

\[\sum_{d|n}\mu(d)=[n=1] \]

\[\sum_{d|n}\mu(d){n\over d}= \varphi(n) 即 \mu * ID= \varphi \]

例题 [MtOI2019]幽灵乐团

Min-Max 反演

在一些“大小关系”难以比较的题目中，Min-Max 反演扮演重要角色
一般形式：

\[\max(S)_k=\sum_{\varnothing \ne T \subseteq S} (-1)^{|T|-1} {|T|-1 \choose k-1} \min(T) \]

特别地，在 \(k=1\) 时

\[\max(S)=\sum_{\varnothing \ne T \subseteq S} (-1)^{|T|-1} \min(T) \]

此式在期望下也成立(甚至更常用)

\[\mathbb{E}\max(S)=\sum_{\varnothing \ne T \subseteq S} (-1)^{|T|-1} \mathbb{E} \min(T) \]

当然，交换 \(\max\) 与 \(\min\) 也是成立的
集训队作业 小Z的礼物

二项式反演

基本形式

\[f(n)=\sum_{i=0}^n (-1)^n {n \choose i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^n {n \choose i} f(i) \]

进一步地，有

\[f(n)=\sum_{i=0}^n {n \choose i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} {n \choose i} f(i) \]

更进一步地，有

\[f(n)=\sum_{i=n}^m {i \choose n} g(i) \Leftrightarrow g(n)=\sum_{i=n}^m (-1)^{i-n} {i \choose n} f(i) \]

这个式子更为常用，考虑这个式子的组合意义
\(f(n)\) 表示钦定(至少) \(n\) 个 \(n\) 元素，\(g(n)\) 表示恰好 \(n\) 个元素，那么 \(g(i)\) 对 \(f(n)\) 的贡献有 \({i \choose n}g(i)\)，即 \(f(n)=\sum_{i \ge n}{i \choose n}g(i)\)，而上式的 \(m\) 是选择个数的上界

子集反演

设现在的研究对象是集合 \(A\)，设 \(A=S\) 时的答案为 \(f(S)\)，\(S \subseteq A\) 时的答案为 \(g(S)\)，那么有

\[g(S)=\sum_{T \subseteq S} f(T) \Rightarrow f(S)=\sum_{T \subseteq S} (-1)^{|S|-|T|}g(T) \]

类似地，当 \(A \subseteq S\) 时答案为 \(g(S)\)

\[g(S)=\sum_{S \subseteq T} f(T) \Rightarrow f(S)=\sum_{S \subseteq T} (-1)^{|T|-|S|}g(T) \]

组合意义就是恰好为这个集合与最多/最少是这个集合之间的转化

标签：sum,mu,反演,数学,choose,Leftrightarrow,subseteq,小记
From： https://www.cnblogs.com/Matutino-Lux/p/17177901.html