几个组合构造的证明

有人问无标号海胆计数, 然后大喊CYC构造, 然后发现大家都把各种构造是啥忘了.

设 $A(x)=\sum_i a_ix^i$ 是我们要构造的东西

可重集构造MSET

EI在WC上讲过, MSET是这样的:
$$
\begin{gathered}
\mathrm{MSET} A(x)=\prod (\dfrac{1}{1-x^i})^{a_i}\
=\exp \sum_i -a_i\ln (1-x^i)\
=\exp \sum_i a_i \sum_{j=1} \dfrac{x^{ij}}{j}\
=\exp \sum_{i=1} \dfrac{A(x^i)}{i}
\end{gathered}\
$$

幂集构造PSET

类比MSET, 写式子, 求ln, 展开ln, 交换求和号.

$$
\begin{gathered}
\mathrm{PSET} A(x)=\prod_i (1+x^i)^{a_i}\
=\exp \sum_i a_i \ln (1+x^i)\
=\exp \sum_i a_i \sum_{j=1} \dfrac{x^{ij}}{j}(-1)^{j-1}\
=\exp \sum_{i=1} \dfrac{(-1)^{i-1}}{i}A(x^i)
\end{gathered}
$$

环构造CYC

不burnside的证明来自 Analytic Combinatorics.

首先大家都知道不能直接 $\mathrm{SEQ}$ 再积分, 因为循环节.

那么定义一个序列/环是本原的当且仅当没有循环节, 则对本原序列的GF积分就是本原环.

先数序列, 用 $x$ 统计容量, $y$ 统计成分, $F(x, y)=\mathrm{SEQ}{\ge 1}(yA(x))=\dfrac{yA(x)}{1-yA(x)}$ 表示非空序列, 设 $G(x, y)$ 为本原序列的GF, 则有 $F(x, y)=\sum{i\ge 1} G(x^i, y^i)$. 应用莫反得到

$$
G(x, y)=\sum_{i\ge 1} \mu(i)F(x^i, y^i)=\sum_{i\ge 1}\mu(i)\dfrac{y^iA(x^i)}{1-y^iA(x^i)}
$$

于是本原环的GF有

$$
\begin{gathered}
H(x, y)=\int \dfrac{G(x, y)}{y} \mathrm{d}y\
=\sum_{i\ge 1} \int \mu(i)\dfrac{A(x^i)}{1-y^iA(x^i)}\mathrm{d}y\
\because \int \dfrac{a}{1-ay^i}\mathrm{d}y=-\ln(1-ay^i)\dfrac{1}{i}\
\therefore H(x, y)=-\sum_{i\ge 1} \dfrac{\mu(i)}{i}\ln(1-A(x^i)y^i)
\end{gathered}
$$

最后环的GF显然有

$$
\begin{gathered}
B(x, y)=\sum_{k\ge 1}H(x^k, y^k)\
=-\sum_{k\ge 1} \sum_{i\ge 1} \dfrac{\mu(i)}{i}\ln(1-A(x^{ik})y^{ik})\
=-\sum_{k\ge 1} \ln(1-A(x^k)y^k)\sum_{i\mid k}\dfrac{\mu(i)}{i}\
\because \sum_{i\mid k}\dfrac{\mu(i)}{i}=\frac{1}{k}\sum_i \mu(i)\dfrac{k}{i}=\dfrac{\varphi(k)}k\
\therefore B(x, y)=-\sum_{k\ge 1}ln(1-A(x^k)y^k)\dfrac{\varphi(k)}{k}
\end{gathered}
$$

大功告成.

试看看

无标号荒漠计数

$1$

无标号海胆计数

$\mathrm{CYC}(\mathrm{SEQ}(x))$