群论 学习笔记

作者: xht37 分类: 笔记 发布时间: 2019-08-02 11:17

点击数:434

OI 中的群论

理论

置换群

置换就是把 $n$ 个元素做一个排列变换,一般地,把 $i$ 变成 $a_i$ 的置换记为 $
\left(
\begin{matrix}
1 & 2 & \dots & n \\
a_1 & a_2 & \dots & a_n
\end{matrix}
\right)
$。

置换本质上为一一映射的函数,因此置换可以结合,有结合律

置换 $\zeta =
\left(
\begin{matrix}
1 & 2 & \dots & n \\
1 & 2 & \dots & n
\end{matrix}
\right)
$ 为恒等置换。若置换 $f,g$ 满足 $f*g=\zeta$,则 $g$ 为 $f$ 的,记作 $f^{-1}$。

一个置换的集合 $G$ 满足:

  1. 若 $f,g \in G$,则 $f*g\in G$。
  2. $\zeta \in G$。
  3. 若 $f \in G$,则 $f^{-1} \in G$。

则称 $G$ 为一个置换群

在置换群的作用下,元素存在等价关系。等价关系满足自反性、对称性、传递性。满足等价关系的元素处于同一个等价类中。

Burnside 引理

对于一个置换 $f$,若一个元素 $s$ 经过 $f$ 后不变,则称 $s$ 为 $f$ 的不动点

记 $f$ 的不动点个数为 $C(f)$,则对于一个置换群,等价类个数为所有 $C(f)$ 的平均值。

Polya 定理

置换可以分解成循环的乘积,其中每个循环代表一些元素的“循环移位”。如 $\left(
\begin{matrix}
1 & 2 & 3 & 4 & 5 \\
3 & 5 & 1 & 4 & 2
\end{matrix}
\right) = (1\ 3)(2\ 5)(4)$。

循环节为循环的个数,如 $(1\ 3)(2\ 5)(4)$ 的循环节为 $3$。

对于一个置换 $f$,$C(f)=k^{m(f)}$,其中 $k$ 为颜色数,$m(f)$ 为 $f$ 的循环节。

综上,在置换群中,等价类个数等于所有置换 $f$ 的 $k^{m(f)}$ 的平均数。

【练习】UVA12103 Leonardo’s NotebookSP1843 LEONARDO – Leonardo Notebook

【练习】UVA1156 Pixel Shuffle

应用

【例题】经典问题

给 $2 \times 2$ 的方格涂黑白两色,旋转后相同算一种,问一共有几种涂色方案。

置换群中包括四个置换:

  1. 不旋转:$f =
    \left(
    \begin{matrix}
    1 & 2 & 3 & 4 \\
    1 & 2 & 3 & 4
    \end{matrix}
    \right) = (1)(2)(3)(4), C(f) = k ^ {m(f)} = 2 ^ 4 = 16$;
  2. 顺时针旋转 $90^\circ$:$f =
    \left(
    \begin{matrix}
    1 & 2 & 3 & 4 \\
    2 & 3 & 4 & 1
    \end{matrix}
    \right) = (1\ 2\ 3\ 4), C(f) = k ^ {m(f)} = 2 ^ 1 = 2$;
  3. 逆时针旋转 $90^\circ$:$f =
    \left(
    \begin{matrix}
    1 & 2 & 3 & 4 \\
    4 & 1 & 2 & 3
    \end{matrix}
    \right) = (1\ 2\ 3\ 4), C(f) = k ^ {m(f)} = 2 ^ 1 = 2$;
  4. 旋转 $180^\circ$:$f =
    \left(
    \begin{matrix}
    1 & 2 & 3 & 4 \\
    3 & 4 & 1 & 2
    \end{matrix}
    \right) = (1\ 3)(2\ 4), C(f) = k ^ {m(f)} = 2 ^ 2 = 4$。

综上,答案为 $\frac{16+2+2+4}{4} = 6$。

【例题】经典问题扩展

经典问题相当于:圆上有 $4$ 个点,$2$ 种颜色,旋转同构,求方案数。
我们把它扩展一下:圆上有 $n$ 个点,$k$ 种颜色,旋转同构,求方案数。

仔细分析可以发现,当我们旋转 $i$ 个点时,一共会有 $\gcd(i,n)$ 个循环,每个循环会有 $\frac{n}{\gcd(i,n)}$ 个元素。

因此 $ans = \frac{1}{n} \sum_{i = 0}^{n-1} k^{\gcd(i,n)}$。

【练习】P4980 【模板】Polya定理

【例题】经典问题再扩展

圆上有 $n$ 个点,$k$ 种颜色,旋转同构,翻转同构,求方案数。

旋转同构总共形成 $a=\sum_{i = 0}^{n-1} k^{\gcd(i,n)}$ 个不动点。

翻转同构分两种情况考虑:

当 $n$ 为奇数时,对称轴有 $n$ 条,每条对称轴形成 $\frac{n-1}{2}$ 个长度为 $2$ 的循环,$1$ 个长度为 $1$ 的循环,共 $\frac{n+1}{2}$ 个循环,因此总共形成 $b=nk^{\frac{n+1}{2}}$ 个不动点。

当 $n$ 为偶数时,有两种对称轴。穿过两个点的对称轴有 $\frac{n}{2}$,共形成 $\frac{n}{2} + 1$ 个循环;不穿过点的对称轴有 $\frac{n}{2}$,共形成 $\frac{n}{2}$ 个循环,因此总共形成 $b=\frac{n}{2}(k^{\frac{n}{2} + 1} + k^{\frac{n}{2}})$ 个不动点。

综上,$ans = \frac{a+b}{2n}$。

【练习】UVA10294 Arif in Dhaka (First Love Part 2)

【例题】P4128 [SHOI2006]有色图

请参考小粉兔的题解窝写不过他 QwQ

【练习】P4727 [HNOI2009]图的同构记数

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注