[置换群&Polya计数]【学习笔记】

昨天看了一下午《组合数学》最后一章然后晚上去看别人的blog发现怎么都不一样，我一定是学了假的polya

其实是一样的，只不过《组合数学》没有太多的牵扯群论。于是又从群论角度学了一遍。

现在来总结，我主要从书上的角度来，群论的知识见$TA$爷的总结

---

置换

设$X$为有限集${1,2,...,n}$，$X$的置换$i_1,i_2,...,i_n$是函数：
$f:X \rightarrow X$
$f$是满射的
$X$所有置换的集合$S_n$

函数的$compositon$运算：

$(g \cdot f)(k)=g(f(k))=j_{i_k}$
满足结合律，通常不满足交换律
$(f \cdot g)\cdot h\ =\ f \cdot (g \cdot h)$
恒等置换$\iota(k)=k$
逆元$f^{-1}$
交换置换$f$的上下两行，再把上一行排序
$f(s)=k,\ f^{-1}(k)=s$
$f \cdot f^{-1}=\iota$

置换群

$S_n$的非空子集$G$满足：
$1.\ $合成运算的封闭性 $\forall f,g \in G,\ f \cdot g \in G$
$2.\ $单位元 $\iota \in G$
$3.\ $逆元的封闭性 $\forall f \in G,\ f^{-1} \in G$
阶：置换群中元素个数

置换群满足消去律：$f \cdot g=f \cdot h \rightarrow g=h$
证明：逆元和结合律

着色

就是给$X$中的每一个元素分配一个颜色
设$c$是$X$的一种着色，$i$的颜色为$c(i)$
$*$运算：

置换对着色的作用
$f$将$k$变为$f(k)$，所以$f*c$将$k$的颜色变到$f(k)$
$(f*c)(i_k)=c(k)\ k=1,2,..,n$
$(f*c)(l)=c(f^{-1}(l))\ l=1,2,...,n$

着色集

$C$满足：
$\forall f \in G,c \in C,\ f*c \in C$

两种运算的关系：$(g \cdot f)*c\ =\ g*(f*c)$
根据$compositon$的定义显然成立

等价关系：

类似偏序关系具有自反性和传递性，不同在于具有对称性
着色等价：
$\exists f \in G,\ f*c_1=c_2\ $则$c_1 ~ c_2$
证明：
$1.\ $自反性：$G$中单位元存在
$2.\ $对称性：$G$中逆元存在
$3.\ $传递性：$G$中合成运算具有封闭性
不同的等价类将$C$划分成若*分

$Burnside$定理

$G(c)={f:\ f \in G,\ f*c=c}$
使着色$c$不变的置换集合，$c$的稳定核

$C(f)={c:\ c \in C,\ f*c=c}$
置换$f$作用下不变的着色集合，$f$的不动点

$G(c)$形成一个置换群(是$G$的子群)
且$\forall f,g \in G,\ g*c=f*c$当且仅当$f^{-1} \cdot g \in G(c)$
证明：置换群的定义；乘逆元。

轨道-稳定核定理

与$c$等价的着色数
$orbit(c)=|{f*c:\ f \in G}|=\frac{|G|}{|G(c)|}$
等于$G$中置换个数除以$c$的稳定核中置换的个数

证明：
满足$g*c=f*c$的$g$的集合为${f \cdot h:\ h \in G(c)}$
由消去律可知集合大小为$|G(c)|$，$G(c)$中包括$\iota$所以这个集合包括$f$自身
也就是说对于每个$f$有$|G(c)|$个置换与他的效果相同
那么与$c$等价的着色数就是$\frac{|G|}{|G(c)|}$啦

还可以从陪集的角度：
$g$的集合是子群$G(c)$关于$f \in G$的一个陪集，大小为$|G(c)|$
一个陪集中对$c$的作用效果显然相同，每个陪集要么相等要么不相交，那么$c$能变成的着色就是不相等的陪集的个数。因为所有陪集的并集为$G$，所以不相等的陪集的个数就是$\frac{|G|}{|G(c)|}$
上面一句是我口胡的，正确与否概不负责，不详细写了。

$Burnside$定理

着色集$C$中非等价着色数
$N(G,C)=\frac{1}{|G|}\sum\limits_{f \in G}|C(f)|$
等于所有|C(f)|的平均值

证明：
我们用两种方法计数$f*c=c$的$(f,c)$的个数
$\sum\limits_{f \in G}|C(f)|\ =\ \sum\limits_{c \in C}|G(c)|$
$=|G|\sum\limits_{c \in C}{\frac{1}{orbit(c)}}$
式子中每个等价类的贡献为$1$，所以
$=|G| \times N(G,C)$
得证

$Polya$定理

将置换看成有向图

$D_f=(X,E_f),\ E_f={(i,f(i)):\ i \in X}$

$n$个点$n$个弧

可以划分成若干个有向环，每个有向环是一个循环置换

阶为$1$的循环就是恒等置换

$f$可以被分解成循环的$composition$的形式，不相交的循环满足分配律

设循环的个数$\#(f)$，用$k$种颜色着色，

那么$|C(f)|=k^{\#(f)}$

证明：显然$f$作用下不变的着色每一个循环中着色必须相同。

$N(G,C)=\frac{1}{|G|}\sum\limits_{f \in G}k^{\#(f)}$

然后《组合数学》上又推了生成函数

$f$的$i$阶循环的个数为$e_i$

$e_1+e_2+...+e_n=\#(f)$

$f$的类型$type(f)=(e_1,e_2,..,e_n)$

$f$的单项式$mon(f)=z_1^{e_1}...z_n^{e_n}$，其实就是都取$k$时就是$k^{\#(f)}$

对这个单项式求和就得到了$G$按类型的生成函数，系数为每个类型的个数

然后定义$G$的循环指数

$P_G(z_1,z_2,..,z_n)=\frac{1}{|G|}\sum\limits_{f \in G}z_1^{e_1}...z_n^{e_n}$

都带入$k$就是上面的非等价着色数的

然后还推广到给定每种颜色的个数，并不觉得在$OI$中有什么用...

[16:25:34]好吧我错了还是有用的，说一下吧

设$k$种颜色集合${u_1,u_2,...,u_k}$，每种颜色要求次数$p_i$

本来我们在循环指数中代入$k$，现在我们在$z_i$代入$u_1^i+u_2^i+...+u_k^i$

然后$u_1^{p_1} u_2^{p_2} ... u_n^{p_n}$的系数就是指定颜色的方案数了

然后有什么意义呢？

做背包

指数就是体积，系数就是方案数

就是把循环分给颜色