Burnside 引理

烷（van）基计数

求基团 \(-C_xH_{2x+1}\) 的结构有多少种（不考虑空间异构，能否稳定存在等情况）。

等价问题：求所有节点满足孩子 \(\leq 3\) 的有根树的数目。

令 \(F(x)\) 表示答案的生成函数，显然

是不正确的，因为对于一个节点，1号儿子与2号儿子完全相同，和2号儿子与3号儿子完全相同，仅仅贡献一次。我们要 无标号有根树 的计数。任意重排列儿子的顺序得到的若干种树之间无差别。这里就要用 Burnside引理 来求解。

对应式子，我们可以写出

分治fft 即可，复杂度 \(\mathcal O(n\log^2 n)\)。如果用 牛顿迭代，可以做到 \(\mathcal O(n\log n)\)。

烷（van）烃计数

求化学式 \(C_xH_{2x+2}\) 的结构有多少种。

对于上述问题，发现有两点不同：

• 根可以有4个儿子
• 有根树 \(\rightarrow\) 无根树

定理：设 \(p\) 是一棵无根树的 点等价类数（即把这棵无根树的所有点拿出来做为根，不同构的树的数目），\(q\) 是一棵无根树的 边等价类数（即把这棵无根树的所有边拿出来做为类似根的特殊边，不同构的树的数目），\(s\) 表示这棵树是否有两个重心，并且当重心间的边切除后，两棵子树是否同构，则

设答案多项式为 \(A(x)\)，两边 \(\sum\) 起来就有：

根据 Burnside引理：

注意 \(Q(x)\) 减一是由于 边存在必须两端都有点。

直接求解即可。

烯烃计数

求化学式为 \(C_xH_{2x}\) 的烯烃的结构数（忽略空间异构和顺反异构）。

考虑枚举碳碳双键的位置，并且尝试断开，发现两端必须是碳，并且这个碳的度数为2。

考虑令 \(G(x)\) 表示两端形态的方案数，显然

显然 \(G(x)\) 不能 \(+1\)。

设答案的生成函数为 \(A(x)\)，则

化学数数：烷基计数、烷烃计数、烯烃计数

原文：https://www.cnblogs.com/ac-evil/p/14529250.html