形式幂级数 $F(z)=\sum_{n\geq 1}a_nz^n$ 当 $[z^1]F(z)\neq 0$ 时存在复合逆且可用 Lagrange 反演求出，这一事实是众所周知的。那么在环 $\mathbb C(\!(z)\!)$ 上，什么样的形式 Laurent 级数存在复合逆，其复合逆是什么样的？记存在复合逆的那些形式 Laurent 级数的集合为 $\mathbb C(\![z]\!)$（我自己搞的记号），结论是

$$ \mathbb C(\![z]\!)=z\mathbb C[\![z]\!]\cup\left\{f\in\mathbb C(\!(z)\!):f=\sum_{n\geq -1}a_nz^n\right\}\cup\left\{f\in\mathbb C(\!(z)\!):f=\sum_{n\geq 1}a_nz^{-n}\right\}. $$

其中 $[z^1]F(z)$ 或 $[z^{-1}]F(z)$ 中至少有一者非零的条件是显然的；因此以上集合应包括了所有存在复合逆的形式 Laurent 级数。

下面记

$$ \begin{aligned} \mathbb C_{1}(\![z]\!)&:=\left\{f\in\mathbb C(\!(z)\!):f=\sum_{n\geq -1}a_nz^n\right\},\\ \mathbb C_2(\![z]\!)&:=\left\{f\in\mathbb C(\!(z)\!):f=\sum_{n\geq 1}a_nz^{-n}\right\}, \end{aligned} $$

我大致得到映射

$$ \begin{aligned} \varphi:\mathbb C_{1}(\![z]\!)&\longrightarrow\mathbb C_{2}(\![z]\!)\\ F&\longmapsto F^{\langle-1\rangle} \end{aligned} $$

是双射（命题 $\bf 1$）。即，$\mathbb C_1(\![z]\!)$ 中的所有级数的复合逆都在 $\mathbb C_2(\![z]\!)$ 中，反之亦然。

命题 $\bf 1$ 的证明

设 $G(z)$ 是 $F(z)$ 的复合逆，$G(z)=g_{-1}z^{-1}+g_0+g_1z+\cdots\in\mathbb C_1(\![z]\!)$，那么

$$ g_{-1}F(z)^{-1}+g_0+g_1F(z)+\cdots=z, $$

于是 $$ (g_{-1}F(z)^{-1}+g_0+g_1F(z)+\cdots)^{-1}=z^{-1}, $$

用 $z^{-1}$ 代入得

$$ (g_{-1}F(z^{-1})^{-1}+g_0+g_1F(z^{-1})+\cdots)^{-1}=z. $$

这表明 $F(z)$ 无非就是 $(G^{-1})^{\langle-1\rangle}(z^{-1})$，从而 $F(z)\in\mathbb C_2(\![z]\!)$。

若设 $G(z)=g_1z^{-1}+g_2z^{-2}+\cdots\in\mathbb C_2(\![z]\!)$，则对于其复合逆 $F(z)$ 我们观察到

$$ g_1F(z)^{-1}+g_2(F(z)^{-1})^2+\cdots=z, $$

于是

$$ F(z)=\left((G\circ z^{-1})^{\langle-1\rangle}\right)^{-1}, $$

它是最低存在 $z^{-1}$ 次项的形式 Laurent 级数，即 $F(z)\in\mathbb C_1(\![z]\!)$。

关于在扩充复平面上考虑的合理性

之前 rqy 给出一个在扩充复平面上考虑的方法：众所周知扩充复平面上在 $0$ 附近取值的 Laurent 级数在 $\mathbb C(\!(z)\!)$ 上是嵌入。于是我们可以考虑对形式 Laurent 级数进行值的代入。设 $\mathrm{ev}:\{\mathbb C^z\to\mathbb C\}\longrightarrow\mathbb C(\!(z)\!)$ 为这个嵌入，记 $\operatorname{ev}f(z)=F(z),\operatorname{ev}g(z)=G(z)$。对于 $F(z)\in\mathbb C_1(\![z]\!)$，由于 $f(0)=\infty$，故 $g(\infty)=0$，即它没有非零的非负项，所以必然有 $G(z)\in\mathbb C_2(\![z]\!)$。

对此我有一定的疑问，即：过程中对 $g(\infty)$ 进行的计算不一定合法。例如将此方法用以考虑 $F(z)\in\mathbb C_2(\![z]\!)$ 的情形时就得到错误的结论（$\infty$ 超出了 $g(z)$ Laurent 展开的收敛域）。

Analytic Combinatorics 里好像没有给证明.

Cycle 构造

所谓组合类 $\mathcal B$ 的 Cycle 构造 $\text{C}{\small\text{YC}}(\mathcal B)$ 是指

$$ \begin{aligned} \text{C}{\small\text{YC}}(\mathcal B):=(\text{S}{\small\text{EQ}}(\mathcal B)\backslash\{\epsilon\})/\mathbf S=\left(\sum_{n\geqslant 1}\mathcal B^n\right)\bigg/\mathbf S. \end{aligned} $$

我们将要证明如下关系：

$$ \mathcal A=\text{C}{\small\text{YC}}(\mathcal B)\;\Longrightarrow\;A(z)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}\log\frac{1}{1-B(z^k)}. $$

证明

对于一个染色，我们定义轨道的权函数为

$$ w(f)=\prod_{a\in A}w(f(a)). $$

带权 Burnside 引理：设 $O_1,\cdots,O_N$ 是群 $G$ 作用于 $X$ 的全部轨道；设 $w$ 为其上的一个权函数，它对于同一轨道具有相同的常数值。则

$$ \sum_{i=1}^Nw(O_i)=\frac{1}{|G|}\sum_{g\in G}\sum_{x\in\varphi(g)}w(x). $$

对于 Cycle 构造

$$ \mathcal A\cong\sum_{n\geq1}\mathcal B^n/\mathbf S, $$

这里的群作用无非是 $\langle\sigma\rangle$ 作用于 $\mathcal B^n$ 上。因此运用带权 Burnside 引理

$$ \sum_{i=1}^Nw(O_i)=\frac{1}{n}\sum_{k=1}^n\sum_{(\beta_i)_{i\leq n}\in\psi(\sigma^k)}w((\beta_i)_{i\leq n}). $$

根据置换群的经典结论，$\sigma^k$ 是 $(k,n)$ 个 $n/(k,n)\text -$轮换之积。因此有

$$ \sum_{i=1}^Nw(O_i)=\frac{1}{n}\sum_{k=1}^nB\big(z^{n/(k,n)}\big)^{(k,n)}=\frac{1}{n}\sum_{d\mid n}\varphi(d)B\big(z^d\big)^{n/d}. $$

于是

$$ \begin{aligned} A(z)&=\sum_{n=1}^{\infty}\frac{1}{n}\sum_{d\mid n}\varphi(d)B\big(z^d\big)^{n/d}\\ &=\sum_{d=1}^{\infty}\frac{\varphi(d)}{d}\sum_{n\geq 1}\frac{B\big(z^d\big)^{n}}{n}\\ &=\sum_{d=1}^{\infty}\frac{\varphi(d)}{d}\log\frac{1}{1-B(z^d)}. \end{aligned} $$