burnside
cmd讲的真的不是很清楚。
看soulist 的博客把，。
soulist NB!!!
拉格朗日定理
首先对于两个群 \(H\subset G\)。
那么 \(|H|\) 是 \(|G|\) 的因数。
考虑给 \(H\) 添 \(g\in G\)，得到的 \(gH\) 不相同时，不可能有交。
于是乎给 \(gH\) 就是相当于平移（可能不是平的，就是移动）。
轨迹·稳定子定理。
群 \(G\) 作用在集合 \(X\) 上。
轨迹和稳定子都是定义在集合元素 \(x\) 上。
轨迹 \(G(x)\) 表示 \(x\) 在任意 \(g\in G\) 作用下能到达的地方。（就是cmd写的等价类，注意这个是 \(X\) 的子集。）
稳定子 \(G^x\) 表示 \(g\in G\) 且满足能使得 \(x \xrightarrow{g} x\) 。（注意这个 \(G^x\) 是 \(G\) 的子集）（甚至是子群）
在证明 轨迹·稳定子定理 之前，我们要说明 \(G^x\) 是 \(G\) 的子群。
主要考虑结合律即可 \((x \xrightarrow{f} x,x \xrightarrow{g} x )\Rightarrow x \xrightarrow{f\times g} x\)。
单位元肯定存在，逆元逆过来整也行，封闭性就显然了。
接下来说明 轨迹·稳定子定理 。
对于 \(x\in X\) 有如下公式成立： \[ |G^x|\times |G(x)| = |G| \] 首先根据 \(G^x\subset G\)，根据拉格朗日定理： \[ |G^x|\times |\{H\mid H=gG^x\}| = |G| \] 中间那坨表示 \(G^x\) 不同乘上 \(g\) 后生成的新群，也就是soulist说的陪群。
引入记号 \(g(x) ,g \in G\)。
\(x\xrightarrow{g}g(x)\)。这个是定义。
那么证明是在构造双射： \[ g(x)\longleftrightarrow gG^x,g\in G \] 如果 \(g(x)=f(x)\) , \(g\times f^{-1}(x)=\epsilon(x)\in G^x\)。则 \(gf^{-1}G^x=G^x\Longleftrightarrow gG^x=fG^x\)。
反之亦然。
所以 \(g(x)\) 与 \(G^x\) 陪群一一对应。
所以 \(|\{g(x)\}|=|G(x)|\) 等于 \(G^x\) 陪群个数。
既得 \(|G(x)|\times|G^x|=|G|\).
这里比较反直观的是即使存在 \(G(x)\) 这个根集合 \(X\) 有关的存在，但是 \(|G(x)|\times|G^x|\) 的值却等于群的大小。
这里似乎可以拿整数模 \(n\) 乘法群来类比理解。
模 \(n\) 加法群也可以。
说句闲话
不严谨的理解方法，考虑 \(g\in G^x\) 的那个与 \(x\) 有关的置换，可以到达 \(G(x)\) 个位置。
大概对于每一个轨道的，我们都可以让所有稳定子作用到轨道上，这些会是不同的 \(g\)。
考虑同一组稳定子作用后肯定是不同的，而且根据作用结果，不同组间一定不同，所以得证。
burnside引理。
通用的burnside引理也是对于群 \(G\) 作用在集合 \(X\) 上说的。 \[ \begin{aligned} l=\frac{1}{|G|}\sum_{g\in G} c(g)\\ c(g)=\sum_{x\in X} [x\xrightarrow{g}x] \end{aligned} \] \(l\) 的含义为作用后的等价类的个数，也就是不同 \(G(x)\) 的个数。（比较显然 \(\forall x\in G(t),G(x)=G(t)\)。
两个元素可以互达当且仅当在同一轨道中。
\(c(g)\) 的含义是集合 \(X\) 中在 \(g\) 作用下的不动点的个数。
首先考虑如何算 \(l\),根据定义。 \[ \begin{aligned} l=\sum_{x\in X} \frac{1}{|G(x)|}=&\frac{1}{|G|}\sum_{x\in X}|G^x|=\frac{1}{|G|}\sum_{x\in X}\sum_{g\in G}[x\xrightarrow{g}x]\\ l=&\frac{1}{|G|}\sum_{g\in G}c(g) \end{aligned} \]
Polya定理。似乎polya就是burnside引理特殊情况。
有 \(n\) 个有编号的球，将其染色，有 \(m\) 种颜色。
给定一个群 \(G\)，如果一对染色状态 \(s,t\),存在 \(g\in G,s\xrightarrow{g}t\) 那么认为 \(s,t\) 是同一个染色状态。
考虑我们现在的集合 \(X\) 是所有染色方案，群 \(G\)。
对 \(X\),\(G\) 求等价类的个数。
直接使用 burnside 引理： \[ l=\frac{1}{|G|}\sum_{g\in G}c(g) \] 考虑 \(c(g)\) 的组合含义，染色方案在置换的角度下的不动点。
考虑这样只能把这个置换 \(g\) 中的所有环添成一个颜色，所以 \(c(g)=m^{cir(g)}\),\(cir(g)\) 表示 \(g\) 中环的个数。
经典问题是给一个长度为 \(5\) 的环，将其染色，问在可以顺时针转的角度下有多少不同的染色方案。
考虑这个限制的群。 \[ \{1,2,3,4,5\},\\\{2,3,4,5,1\},\\\{3,4,5,1,2\},\\\{4,5,1,2,3\},\\\{5,1,2,3,4\} \] 这个群只有第一个是 \(5\) 个环，剩下的都是 \(1\) 个环，考虑 \(5\in \mathbb{P}\)。
所以答案是： \[ \frac{1}{5}(m^5+4m) \] .
【完】Maybe?