前言
最近花了几天时间学习了关于群论的一些东西, 现在总结一下.
主要是通过看书《组合数学》, 和参考博客DruuBee Orz
这个总结会非常粗略, 我只会写一些必须的东西, 因为画图太麻烦时间仓促,所以例子会比较少,想要理解请多画图.
置换群与对称群
置换
定义
通俗一点地讲:
如果我们有一个正方形, 它的四个顶点从左上角按照顺时针依次为$A,B,C,D$,我们将它顺时针旋转九十度,那么现在从左上角按照顺时针依次为$D,A,B,C$.我们把这种位置的交换叫做置换.
专业一点的讲:
设$X$为有限集,为了方便我们取$X$为前$n$个正整数组成的集合(即$X=\lbrace 1,2,\dots,n\rbrace$).$X$的某一置换$i_1,i_2,\dots,i_n$可以看做$X$到其自身的一对一函数,其定义为
$$f:X\to X$$
其中
$$f(1)=i_1,f(2)=i_2,\dots,f(n)=i_n$$
我们可以将其表示为一种阵列的形式
$$
\begin{pmatrix}
1 & 2 & \cdots & n \\
i_1 & i_2 & \cdots & i_n
\end{pmatrix}
$$
在刚才的例子中我们将$A,B,C,D$写作$1,2,3,4$就可以得到如下置换
$$
\begin{pmatrix}1 & 2 & 3 & 4 \\
4 & 1 & 2 & 3
\end{pmatrix}
$$
置换的合成
我们规定一种关于集合的运算合成,用符号 $\circ$ 表示.
例如
$$
f=\begin{pmatrix}1 & 2 & 3 & 4 \\
3 & 2 & 4 & 1
\end{pmatrix}
$$
$$
g=\begin{pmatrix}1 & 2 & 3 & 4 \\
2 & 4 & 3 & 1
\end{pmatrix}
$$
我们可以自己模拟一下得到如下结果
$$
g\circ f=
\begin{pmatrix}1 & 2 & 3 & 4 \\
3 & 4 & 1 & 2
\end{pmatrix}
$$
$$
f\circ g=
\begin{pmatrix}1 & 2 & 3 & 4 \\
2 & 1 & 4 & 3
\end{pmatrix}
$$
上面的例子也说明了合成不满足交换律
但是它是满足结合律的,即
$$(f\circ g)\circ h = f\circ(g\circ h)$$
置换的幂
我们通常用幂符号表示一个置换与它自身的合成:
$$
f^1=f,f^2=f\circ f,f^3=f\circ f \circ f,\cdots,f^k=f\circ f\circ f\circ \cdots\circ f(k个f)
$$
恒等置换
恒等置换就是集合各个元素对应它本身的置换,我们记为$\iota$
$$
\iota=\begin{pmatrix}1 & 2 & \cdots & n \\
1 & 2 & \cdots & n
\end{pmatrix}
$$
显然
$$
\iota\circ f=f\circ\iota
$$
同时我们规定
$$
f^0=\iota
$$
置换的逆
我们定义置换的逆,这个脑补一下就会想到是怎么回事,我们记它为$f^{-1}$
再脑补一下可知
$$
f\circ f^{-1} = f^{-1}\circ f = \iota
$$
置换群
定义
考虑一个多边形为正$n$边形
我们定义如下形式的置换为$\rho_n$:
$$
\rho_n=\begin{pmatrix}1 & 2 & \cdots & n-1 & n \\
2 & 3 & \cdots & n & 1
\end{pmatrix}
$$
考虑一个多边形为正$n$边形,我们将它的一个顶点放置到最高的位置,并将这个位置叫做起点.从起点开始顺时针方向标号为$1,2,\cdots,n-1,n$
对这个多边形进行置换$\rho_n$的话,从起点开始顺时针方向标号依次变为$2,3,\cdots,n,1$
再次脑补一下,我们相当于将这个$n$边形逆时针旋转了$\frac{2\pi}{n}$后将$2$放在了起点上
显然对于旋转来讲,我们有$n$种不同的旋转方案,即$\rho_n^1,\rho_n^2,\rho_n^3,\cdots,\rho_n^n$.其中$\rho_n^n$相当于没有旋转,则可知
$$
\rho_n^n=\rho_n^0=\iota
$$
我们将这些不同的置换放在一个集合里,这个集合就被称为置换群,我们将这个置换群记作$G$.
正$n$边形还有一种变换叫做反射(即以某条直线为轴翻转)
如正五边形以起点和起点对边中点所在直线为轴旋转的一个置换
$$
\tau=\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\
1 & 5 & 4 & 3 & 2
\end{pmatrix}
$$
显然类似这样的反射有五种,为了方便叙述,我们规定$\tau_i$表示将图形反射并将标号为$i$的点放在起点上.
此时
$$
G = \lbrace \rho_n^0=\iota,\rho_n^1,\rho_n^2,\rho_n^3,\rho_n^4,\tau_1,\tau_2,\tau_3,\tau_4,\tau_5 \rbrace
$$
其实变换并不止旋转与反射:
如果规定操作合理,你可以将两个角剪下来并交换位置,这也是一种变换,只不过一般不会出现这种情况.
而且,旋转与反射并不是一定存在的:
例如对于立体图形来就这两个操作就不好描述了,所以并不是所有的几何图形都有旋转与反射;而且有时会人为规定反射不可取或旋转不可取.
性质
不加证明地给出置换群满足的三条性质:
- 合成运算的封闭性:对$G$中的每一个置换$f$与$g$,$f\circ g$也属于$G$.
- 单位元:恒等置换$\iota$属于$G$
- 逆元的封闭性:对$G$中的每一个置换$f$,它的逆元$f^{-1}$也属于$G$
可知上面正五边形的$G$满足这三条性质,因此上面的$G$是一个置换群
对称
定义
设$\Omega$为一几何图形(也许是多维的),$\Omega$到它自身的一个运动或全等对称成为$\Omega$的一个对称.显然上面正五边形的$G$中每一个置换都是一个对称.
对称群
定义
对一个集合的一些对称置换的置换群 叫做对称群.
着色
定义
$X$的一种着色是给$X$的每一个元素指定一种颜色的分配方案.
我们设一种着色方案为$c$,元素$i$的颜色表示为$c_i$.
性质
我们考虑一个着色$c$与一个置换$f$的关系.
定义$f*c$为使得一个集合的着色$c$按照置换$f$转移.
例如
$$
c=\begin{pmatrix}a & b & c & d & e
\end{pmatrix}
$$
$$
f=\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\
1 & 5 & 4 & 3 & 2
\end{pmatrix}
$$
则
$$
f*c=\begin{pmatrix}a & e & d & c & b
\end{pmatrix}
$$
下面考虑$\circ$运算与$*$运算的关系
$$
(g\circ f)*c=g*(f*c)
$$
着色集
定义
顾名思义,着色集即对一个集合一些着色方案的集合,记为$C$
等价关系
如果$c_1$在$G$的某个置换作用下得到了$c_2$,我们就称$c_1$与$c_2$是等价的,记作
$$c_1 \sim c_2$$
性质
对于$G$中的任意元$f$,$f*c$仍然属于$C$
关于等价关系有以下三条性质
- 自反性: 对于任意的$c$,$c\sim c$
- 对称性: 如果$c_1\sim c_2$,则$c_2\sim c_1$
- 传递性: 如果$c_1\sim c_2$,且$c_2\sim c_3$,则$c_1\sim c_3$
注意等价将$C$中的着色划分成若干部分,使得所有等价的着色在同一个部分.
Burnside定理
设$G$是作用于$X$上的置换群,$C$是对$X$的染色集,且$G$作用于$C$上,即任意$f$与$c$,有$$f*c\in C$$
$G(c)$
对于一个着色$c$我们可以选择一些置换,使得这些置换中任意一个$f$有
$$f*c=c$$
我们把这个置换的集合记作$G(c)$,即使得着色$c$不变的$G$中所有置换的集合,也称之为着色$c$的稳定核.
$C(f)$
对于一个置换$f$我们可以选择一些着色,使得这些着色中任意一个$c$有
$$f*c=c$$
我们把这个着色集合记作$C(f)$.
定理1
对于每一种着色$c$,$G(c)$也是一个置换群,而且对于$G$中的任意置换$f$与$g$,$g*c=f*c$当且仅当$f^{-1}\circ g\in G$
证明略
推论1
$C$中与$c$等价的着色数等于$G$中置换的个数除以$c$的稳定核中的置换个数,即
$$
|\lbrace f*c:f\in G\rbrace|=\frac{|G|}{|G(c)|}
$$
证明
对于任意一个$G$中的置换$f$,若存在
$$
g*c=f*c
$$
则其中的$g$实际上为
$$
\lbrace f\circ h:h\in G(c)\rbrace
$$
易知上面集合中的置换个数实际上等于$|G(c)|$,从而对每一个$f$都有$|G(c)|$个置换作用在$c$上与$f$有相同效果.总共有$|G|$个置换,所以,与c等价的着色方案数
$$
|\lbrace f*c:f\in G\rbrace|
$$
等于
$$
\frac{|G|}{|G(c)|}
$$
证毕.
定理2(burnside定理)
设$G$是$X$的置换群,而$C$是$X$中一个满足下面条件的着色集合:对于$G$中所有的$f$和$C$中的所有$c$都有$f*c$仍在$C$中,则$C$中非等价着色数$N(G,C)$由下式给出
$$
N(G,C)=\frac{1}{|G|}\sum_{f\in G}|C(f)|
$$
换言之$C$中的非等价着色数等于在$G$下保持不变的着色的平均数.
证明
首先计数使$f$保持$c$不变的对偶$(f,c)$的个数.
方法一
$$
\sum_{f\in G}|C(f)|
$$
方法二
$$
\sum_{c\in C}|G(c)|
$$
我们让这两个式子相等
$$
\sum_{f\in G}|C(f)|=\sum_{c\in C}|G(c)|
$$
此时根据推论1得
$$
|G(c)|=\frac{|G|}{(与c等价的着色数)}
$$
因此,
$$
\sum_{c\in C} = |G|\cdot\sum_{c\in C}\frac{1}{(与c等价的着色数)}
$$
由于同一等价类中中的每个着色对上式的贡献都为
$$
\frac{1}{(与c等价的着色数)}
$$
那么同一等价类中的所有着色对上式的贡献和为$1$
,所以上式等于
$$
N(G,C)\cdot|G|
$$
那么,由第一个等式可以得到
$$
\sum_{f\in G}|C(f)|=N(G,C)\cdot|G|
$$
方程两侧同时除以$|G|$,得到
$$
N(G,C)=\frac{1}{|G|}\sum_{f\in G}|C(f)|
$$
证毕
例子
1.把$n$个不同的对象放在一个圆上,问有多少种放法(旋转后相同的放法视为同一种放法)?
答:
$$
G=\lbrace\rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1}\rbrace
$$
$$
N(G,C) = \frac{1}{n}(n!+0+0+\cdots+0)=(n-1)!
$$2.对红色与蓝色对正五边形进行染色,有多少种染色方法(旋转与翻转后相同视为同一种方法)?
答:
$$
G=\lbrace\rho_5^0=\iota,\rho_5^1,\rho_5^2,\rho_5^3,\rho_5^4,\tau_5^1,\tau_5^2,\tau_5^3,\tau_5^4,\tau_5^5\rbrace
$$
$$
C(\rho_5^i)=\begin{cases}
32 & i=0\\\\
2 & i=1,2,3,4
\end{cases}
$$
$$
C(\tau_5^i) = 8 , i=1,2,3,4,5
$$
$$
N(G,C) = \frac{1}{10}(32+2+2+2+2+8+8+8+8+8)=8
$$
Polya定理
循环
记形如
$$
\begin{pmatrix}
a_1 & a_2 & a_3 & \cdots & a_{n-1} & a_n \\
a_2 & a_3 & a_4 & \cdots & a_n & a_1
\end{pmatrix}
$$
的一个置换为循环
每个置换都可以写为若干个循环的乘积
如
$$
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
3 & 5 & 6 & 4 & 2 & 1
\end{pmatrix}=
\begin{pmatrix}
1 & 3 & 6
\end{pmatrix}
\begin{pmatrix}
2 & 5
\end{pmatrix}
\begin{pmatrix}
4
\end{pmatrix}
$$
Polya计数公式
设函数$m(f)$为置换$f$的循环个数则有以下定理
$$
N(G,C)=\frac{1}{|G|}\cdot\sum_{f\in G}k^{m(f)}
$$
Polya定理在不同的题目中应用不同,下面以题目来说明.
以下题目解题思路参考博客DruuBee
例子
[poj] 2409: Let it Bead
用k种颜色对n个珠子构成的环上色, 旋转翻转后相同的只算一种, 求本质不同的着色方案数.对于表示翻转的置换的统计,请点入上面链接查看.
下面解释在统计表示旋转的置换时的公式
$$
\sum_{i=1}^{n}k^{gcd(n,i)}
$$
通俗的解释是:请手动画图找规律.
专业一点的解释:请打开黑书查看P252
下面引用这里的解释
假设起点在x，则x，x+i，x+2*i，……，x+k*i，……
假设在第t次，第一次回到起点，则x=(x+t*i)%n => t*i%n=0 => t=LCM(i,n)/i=n*i/GCD(n,i)/i=n/GCD(n,i)。
那么可以上n/t种颜色，即n/(n/GCD(n,i))种，所以旋转的着色方案有k^GCD(n,i)种。[poj] 2154: Color
用n种颜色对n个珠子构成的环上色, 旋转后相同的只算一种, 求本质不同的着色方案数分析请点入上面链接
[poj] 2888: Magic Bracelet
对n个珠子构成的环染m种颜色, 并且规定一些颜色不能相邻. 旋转后相同算是同一种方案, 求本质不同的着色方案数.(m≤10,n≤109)分析请点入上面链接
这是三道例题(不要怪我懒= =),更多例题请参考博客DrunBee