0%

Burnside引理与Polya计数原理

Burnside引理与Polya计数原理

Burnside引理简介

这个定理主要叙述了在置换群作用下元素的不动情况。

为了方便起见,我们引入颜色的概念,假设一个长度为$n$的向量$x$,其中$x$的第$i$维度记为$x_{i}$,定义一共有$m$种颜色,即$x_{i}\in{1,2,\cdots,m}$。假设$y$是$n$上的一个置换,则$y(x)$表示相应颜色的置换。

设$G$是一个置换群,设两个本质不同的染色为两个维度为$n$的向量$x$与$t$,且不存在$g \in G$,使得$g(x) = y$.

假设所有的染色方案集合为$S$.

则可以发现上面定义了一种等价关系。

$Burnside$引理给出了计数这个商集大小的方法。

Burnside引理感性证明

我知道自己没法写出严格的证明,我只能按照自己的思路整理出合我自己思路的证明思路。

严格思路可以参考链接

该定理的证明方式主要基于对于$G$的不同分组计数方式。

我们知道不同的$G$的计数方式可以形成一个等式,而只要我们要求的商集大小存在于这个等式之中,我们就可以求得商集的大小。

我们考虑$G$是一个置换群,将其作用于${1,2,\cdots,n}$上亦是一个等价关系,先考虑其中的一个等价类$[k]$.

不妨记$[k] = {k,k_{1},\cdots,k_{p}}$,其中由等价关系得到对于任意一个$k_{i}$都存在一个$g_{i} \in G$使得$g_{i}(k_{i})=k$

更感性一点,我们可以发现通过$k_{i}$可以找到一个$G$的子集$G_{k_{i}}$对于这个子集中的任意一个元素,都是一个置换,且是一个可以从$k_{i} \rightarrow k$的置换。

根据这样的一个简单说明,我们知道$[k]$中的每个元素都对应了一个$G$的子集,并且这些子集是无交的而且这些的并是$G$,想想为什么吧。

于是我们得到了一个关于$|G|$的式子,即$$|G| = \sum_{\hat{k}\in [k]}|G_{\hat{k}}|$$

到此为止便是简单思路能够思考到的位置了。

下面就是些只能仰慕的推导了。

数学家们发现$|G_{\hat{k}}|$是相等的。

可以简单在这里证明一下。

令$G_{k_{i}} = {g_{1},\cdots,g_{q}}$,取$g_{1}$作用于$G_{k}$,记结果为$\hat{G_{k}}$现在$\hat{G_{k}}$的每个元素都是$k \rightarrow k_{i}$的一个置换,根据定义$\hat{G_{j}} \subseteq G_{k}$ 用来比大小的话就是$|G_{k_{i}}| = \hat{G_{k}} \leq G_{k}$

接下来只要证明反向包含就行了。

任取$G_{k_{i}}$的一个元素$g_{j}$, 显然$g_{j} = g_{1}*g_{1}^{-1}*g_{j}$,其中$g_{1}^{-1}*g_{j} \in G_{k}$,于是$g_{j} \in \hat{G_{k}}$,于是反向包含就证好了。

于是我们得到了$$|G| = |G_{k}||[k]|$$

为了思路的连贯,并没有保持和参考文章一样的记号。

接下来,对于$G$与$S$列一个矩阵,定义$\mu(g,s) = [g(s)==s]$

$\sum_{g}\sum_{s}\mu(g,s) = \sum_{s}|G_{s}| = t |G_{s}|[s] = t|G|$

于是最后的结果为$t = \frac{1}{|G|}\sum_{g}\sum_{s}\mu(g,s)$

Polya计数原理的简述与感性证明

之所以将它称之为计数原理在于这个方法简化了上面引理的一部分计算。

引用上面Burnside引理的结果$t = \frac{1}{|G|}\sum_{g}\sum_{s}\mu(g,s)$

Polya计数原理简化了$\sum_{s}\mu(g,s)$的计算。

原理在于对每个置换进行循环分解。

大概举个例子$g = (1)(2,3)(4,5,7)(6)(9)$

可以理性观察这个置换,只有每个括号里的元素颜色一样的时候才会对答案有贡献。

于是$\sum_{s}\mu(g,s) = m^{|g|}$

其中$|g|$表示$g$再进行循环分解后有多少个括号。

于是上面的式子就变成了$t = \frac{1}{|G|}\sum_{g}m^{|g|}$

abab