0%

群论视角下的欧拉变换

对无标号计数的重新讨论。

摘一段去年写的东西:

首先介绍一下一个挺有用的东西:$\text{Euler}$ 变换。

众所周知,对一个生成函数 $F$ 做 $\text{Exp}$ 得到的生成函数的意义是:把 $n$ 分成若干无序组,每一个大小为 $s$ 的组都有 $[x^s]F$ 个方案。

而 $\text{Euler}$ 变换的含义与其类似,但是大小相同方案相同的两个组要求无序。

这个要求有点奇怪。所以可以想到枚举大小和每个方案,这时我们只能决定使用多少个这种方案(要求我们不考虑它们的顺序),所以 $\text{Euler}$ 变换即

整理得

(不得不说生成函数真的是数数困难患者的福音,原来见到“无标号”这三个字我只能懵 B,现在拿 $\text{Euler}$ 变换刚就好了)

现在掌握了群论理论,我们能不能暴力推导出它呢?

首先枚举儿子数 $i$。考虑应用 burnside 引理,显然一个置换 $f$ 的不动点只与其循环拆分(有序,显然循环间可以通过最前一个元素的位置分出顺序) $\{a_i\}$ 有关。具体来说是

(解释一下上式:循环内所有组的“染色”方案必须完全一样,选择大小均为 $s$ 方案数就只有 $[x^s]F$,但是“占地”却是 $a_is$,故有上式)

(似乎也叫做生成函数形式的 Polya 定理?)

思考有多少个循环能被循环拆分 $\{a_i\}$ 描述。首先决定每个标号属于哪个循环,然后循环内可以圆排列,而这样搞会破坏循环原本的有序,所以还要再除以循环数的阶乘。

我们发现现在后面这个部分可以写成 $\text{Exp}$ 的形式。设

则我们得到

直接带入 $y=1$ 即可。我们得到

???

是哪出了问题?

答案是:没有问题!将 Euler 变换 $\text{Ln}$ 再 $\text{Exp}$ 即得到我们的形式!

还以为有什么有趣的东西,结果就这?