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} $$