Cycle 构造 OGF 关系式的证明
Gorenstein
·
·
算法·理论
设 \mathcal A=\text{C}{\small\text{YC}}(\mathcal B)，那么
\mathcal A\cong\sum_{n\geq1}\mathcal B^n/\mathbf S,
其中 \mathbf S 是 \langle\sigma\rangle 轨道等价类。我们要证明
A(z)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}\log\frac{1}{1-B(z^k)}.
求 \sum_{i=1}^Nw(O_i)，其中 \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}