群论小记

command_block · 2019-03-18 13:26:12 · 个人记录

1.群的概念与基本性质

- 封闭性 : 若 $a,b\in G$ ,则必有 $(a*b)\in G$。 - 结合律 : 对于任意的 $a,b,c\in G$ ,有 $(a*b)*c=a*(b*c)

存在单位元 : 存在一个 e\in G ,使得对于任意的 a\in G ,满足 a*e=e*a=a。

元素 e 则被称作单位元。
存在逆元 : 对于任意的 a\in G ,存在一个 b\in G ,满足 a*b=b*a=e。

元素 b 可以记作 a^{-1}。

则称 G 在 * 运算下是一个群。

有时把 * 省略不写。

设有两个不同的单位元 e_1,e_2 ,根据单位元的定义能得到 e_1=e_1e_2=e_2 ,矛盾。

\color{blue}\text{定理 1.2}:$ $ab=ac\Rightarrow b=c,\ ba=ca\Rightarrow b=c

证左部,右部同理。

ab=ac\ \Rightarrow\ a^{-1}(ab)=a^{-1}(ac)\ \Rightarrow\ (a^{-1}a)b=(a^{-1}a)c\ \Rightarrow\ b=c

若 a 有两个不同的逆 b,c。

则有 ab=e=ac ,使用\color{blue}\text{定理1.2} 约去 a 得到 b=c。

若只希望了解置换计数，可以到此为止。

\color{blue}\text{定理 1.4}:$ 对于任意的(有限)群 $G=\{e,a_1,a_2...a_n\}
对于任意的 a\in G 都存在一个常数 {\rm ord}(a) ,使得 a^{{\rm ord}(a)}=e。此时称 {\rm ord}(a) 为 a 的阶。

且有 a^{-1}=a^{{\rm ord}(a)-1}。

任取 a\in G ,构造 \{a,a^2,a^3...a^n,a^{n+1}\}。

由于封闭性,这 n+1 个元素都属于 G ,但 |G|=n ,所以必有两者相等。

不妨设 a^x=a^y,x<y。约掉 a^x 则有 a^{y-x}=e。

令 {\rm ord}(a)=y-x ,则有 a^{r(a)-1}a=a^{r(a)}=e。能得到 a^{r(a)-1}=a^{-1}

2. 置换与置换群

置换的定义

假设有 1,2,3...n 这 n 个元素, 令 k 被元素 a_k 所取代。

满足各个 a_k 互不相同,也就是“移动”后, n 个元素仍然都存在。

写作置换 : \begin{pmatrix}1&2&3&...&n\\a_1&a_2&a_3&...&a_n\end{pmatrix}

如 p=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}

这个置换就代表着:

把 1 移到第 3 个
把 2 移到第 1 个
把 3 移到第 4 个
把 4 移到第 2 个

又作:

1\xrightarrow{p}3,\quad 2\xrightarrow{p}1,\quad 3\xrightarrow{p}4,\quad 4\xrightarrow{p}2

置换乘法

置换的乘法就是把映射叠加。

设 p_2=\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}

则 1\xrightarrow{p}3\xrightarrow{p_2}4,\quad 2\xrightarrow{p}1\xrightarrow{p_2}2,\quad 3\xrightarrow{p}4\xrightarrow{p_2}3,\quad 4\xrightarrow{p}2\xrightarrow{p_2}1

所以有 p*p_2=\begin{pmatrix}1&2&3&4\\4&2&3&1\end{pmatrix}

也可以这样写 :

\small\begin{pmatrix}1&2&3&4\\3&1&4&2\\\end{pmatrix}*\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}*\begin{pmatrix}3&1&4&2\\4&2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3&4\\4&2&3&1\end{pmatrix}

容易证明如下的几条基本性质 :

置换的乘积还是置换。
置换乘法满足结合律。
单位元为 \begin{pmatrix}1&2&3&...&n\\1&2&3&...&n\\\end{pmatrix}
\begin{pmatrix}1&2&...&n\\a_1&a_2&...&a_n\end{pmatrix}$ 的逆为 $\begin{pmatrix}a_1&a_2&...&a_n\\1&2&...&n\end{pmatrix}

但注意,置换乘法一般不满足交换律。

置换群

根据上面的若干性质,不难证明对 1...n 作用的所有置换形成一个群。

总是研究全体置换,未免乏味,我们一般只研究一个子群。

有如下事实 : 对于任意一个 n 阶有限群,存在一个 n 阶置换群与其同构。

解释一下同构是什么意思,想想一个二分图,左侧的点用对子 (a,b) 描述,向右侧的 a*b 连边。

若这两个图同构,则称两个群同构。(其实就是把所有的运算结果打了个表)

现在我们就是要证明置换群能够造出任意的图来。

对于 G=\{a_1,a_2...a_n\} ,取 a_k ,写出 a_ka_1,a_ka_2...a_ka_n。

这些乘积必然两两不同。假设有 a_ka_i=a_ka_j ,约去 a_k 可得 a_i=a_j ,矛盾。

我们设 p_k=\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_k&a_2a_k&...&a_na_k\end{pmatrix} (其实就是把所有关于 a_k 的运算写出来)

令 a_k 和 p_k 相对应,写作 a_k\leftrightarrow p_k。

则有 a_ia_j\leftrightarrow p_ip_j ,证明如下 :

p_ip_j=\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_i&a_2a_i&...&a_na_i\end{pmatrix}\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_j&a_2a_j&...&a_na_j\end{pmatrix}

=\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_i&a_2a_i&...&a_na_i\end{pmatrix}\begin{pmatrix}a_1a_i&a_2a_i&...&a_na_i\\(a_1a_i)a_j&(a_2a_i)a_j&...&(a_na_i)a_j\end{pmatrix}

=\begin{pmatrix}a_1&a_2&...&a_n\\a_1(a_ia_j)&a_2(a_ia_j)&...&a_n(a_ia_j)\end{pmatrix}

注意到,前面的“二分图”有 n^2 个 1...n 的信息,而 n 阶置换群也有 n^2 个信息,所以本质上其实是暴力打表。

置换的循环

把置换看做一张有向图, 连边 i\rightarrow a_i 。不难发现,每个点只有一个出度一个入度,所以会形成若干个环。

\begin{pmatrix}1&2&3&4\\3&1&4&2\\\end{pmatrix}

的循环是 (1,2,3,4)

\begin{pmatrix}1&2&3&4\\2&1&4&3\\\end{pmatrix}

的循环是 (1,2)(3,4)

\begin{pmatrix}1&2&3&4\\2&1&3&4\\\end{pmatrix}

的循环是 (1,2)(3)(4) ,通常省略一元循环写作 (1,2)。

置换可以用这些环来表示,而且表示方法是唯一的。

由于比双层写法更简洁,下面有时会以循环的方式写出置换。

2. Burnside / Polya

设 G 是 1...n 的一个置换群。

不动点

对于 p\in G,若 k\xrightarrow{p}k ,则称 k 是 p 下的不动点。

将 p 下的不动点个数即为 c(p)。

对于 p\in G ,若 k 是 p 的不动点,则称 p 属于 k 不动置换类。

记作 p\in Z_k。能够发现, Z_k 是 G 的一个子群。

等价类

等价类 E_k 设为对元素 k 施加任意的 G 中置换,能够获得的元素集合。 (又称为轨迹)

如 G=\{e,(1,2),(3,4),(1,2)(3,4)\}。

那么 1 在置换的作用下可以到达 1,2 ,但不可能到达 3,4 ,则有 E_1=\{1,2\}。

\color{blue}\text{定理 2.1}:$ 当 $x,y$ 属于一个等价类时,有 $|Z_x|=|Z_y|

根据等价类的定义,存在置换 $t\in G$ 使得 $\ x\xrightarrow{t} y,\quad y\xrightarrow{t^{-1}} x$。对于任意的 $p\in Z_x$ ,有 $y\xrightarrow{t^{-1}} x\xrightarrow{p} x\xrightarrow{t}y$ ,构造 $p'=t^{-1}pt$ ,则必有 $p'\in Z_y$。这就是一组从 $Z_x$ 到 $Z_y$ 的映射,同理也有 $Z_y$ 到 $Z_x$ 的映射。构建了双射之后,元素个数显然是相同的。 - **轨道-稳定化子定理** $\color{blue}\text{定理 2.2}:$ $|Z_k|\times|E_k|=|G|

\color{blue}\text{证明}:$ 设 $m=|E_k|$ ,设 $E_k=\{a_1(=k),a_2...a_m\}

根据等价类的定义,对于每个 a_i 都存在 p_i\in G 使得 k\xrightarrow{p_i} a_i。

设置换集合 G_i=Z_kp_i ,显然有 G_i\subseteq G。

由于 k\xrightarrow{p\in Z_k}k\xrightarrow{p_ i}a_i ,则有 k\xrightarrow{p\in Z_kp_i}a_i

能够发现 i≠j 时 ,G_i∩G_j=\varnothing。(这是显然的,因为两个群对 k 的作用不同)

那么有 G_1+G_2+...G_m\subseteq G。

另一方面,对于任意的 p\in G ,由等价类的定义,必有 a_i 使得 k\xrightarrow{p}a_i。

那么有 k\xrightarrow{p}a_i\xrightarrow{p_i^{-1}}k \Longrightarrow p*p_i^{-1}\in Z_k \Longrightarrow p\in Z_kp_i

所以, G 中的每个置换都被包含在某个 G_i 中,则有 G\subseteq G_1+G_2+...+G_m。

综上可得 G=G_1+G_2+...+G_m=Z_kp_1+Z_kp_2+...+Z_kp_m

- **Burnside引理** $\color{blue}\text{定理 2.3}:$ 称 $E_{1...n}$ 中本质不同的个数,为等价类个数,设为 $l$ ,则有 $$l=\dfrac{1}{|G|}\sum\limits_{p\in G}c(p)$$ 人话 : 等价类个数=各个置换下不动点个数的和的平均数。 $\color{blue}\text{证明}:$ 设 $m=|G|,G=\{a_1,a_2...a_m\}$。记 $s_{i,k}=[k\xrightarrow{a_i}k]$。能够发现, $\sum\limits_{k=1}^ns_{i,k}=c(a_i)$ (对置换 $a_i$ ,枚举各个元素,查看是否不动) 同时也有 $\sum\limits_{i=1}^ms_{i,k}=|Z_k|$ (对元素 $k$ ,枚举各个置换,查看是否不动) 则所有 $s$ 的和 $=\sum\limits_{i=1}^m\sum\limits_{k=1}^ns_{i,k}=\sum\limits_{i=1}^mc(a_i)=\sum\limits_{k=1}^n|Z_k|$。 **不妨**设 $l$ 个**互不相同**的等价类为 $E_1,E_2...E_l$ ,则有 $N=E_1,E_2...E_l$。那么,由于 $R$ 是 $N$ 的一个划分,我们可以把 $\sum\limits_{i=1}^n$ 换成 $\sum\limits_{t=1}^l\sum\limits_{i\in E_t}

则有 \sum\limits_{k=1}^n|Z_k|=\sum\limits_{t=1}^l\sum\limits_{i\in E_t}|Z_i|

回忆 \color{blue}\text{定理 2.1} ,由于 i,t 同属于一个等价类,可以把 |Z_i| 换成 |Z_t|。

\sum\limits_{t=1}^l\sum\limits_{i\in E_t}|Z_t|=\sum\limits_{t=1}^l|E_t||Z_t|

又因为 |E_t||Z_t|=|G| ,所以有上式 =l\times|G|

于是就有 \dfrac{1}{|G|}\sum\limits_{i=1}^mc(a_i)=l ,证毕。

Polya定理

以问题引入 : 给出一条长度为 6 的链条,每一节可以染上 4 种不同的颜色,但是翻转之后相同的方案被视为本质相同,问不同的染色方案数。

若将每种染色方案视为一个元素,令 N 为这些元素的集合,那么 N 在“翻转置换”作用下的等价类个数即为答案。

问题在于,置换的大小是 |N|=6^4 ,非常庞大,不便于计算。

能够发现,“翻转”同样是对 1...6 这些“位置”的置换,且也是群。

若能把对“位置”的小置换群,和对“状态”的大置换群联系起来,就能更方便地计算了。

设 $G$ 是 $n$ 个元素的置换群,则染色总方案数为 : $$\dfrac{1}{|G|}\sum\limits_{p\in G}T(p)$$ 其中 $T(p)$ 指在置换 $p$ 下,不动的染色方案数。 - 比如 $\begin{pmatrix}1&2&3&4\\2&1&4&3\\\end{pmatrix}$。那么染成 $\{a,a,b,b\}$ ,置换完了之后还是 $\{a,a,b,b\}$ ,则称之为不动的染色方案染成 $\{a,b,c,d\}$ 置换完了之后是 $\{b,a,d,c\}$ ,和原来不相等,则不是“不动方案”。
\color{blue}\text{证明}:
设 G' 是对状态的置换群。不难发现大置换和小置换有对应关系,使用小置换对每种状态讨论即可得到大置换。

形式化的讲,设 p\in G 对应 p'\in G'。

若一种染色方案 a 在经过 p 的“移动”之后,变为了 b ,则 a\xrightarrow{p'}b。

所以有 |G|=|G'|。

根据经典的Burnside引理,可以得到答案为 \dfrac{1}{|G'|}\sum\limits_{p'\in G'}c(p')

而 c(p') 的意义正是 G 中相对应的置换 p 下不动的染色方案数,证毕。
接下来介绍如何求 T(p)。

设 d(p) 为 p 的循环个数,则(根据等式的传递性)每个循环中必须染上同一种颜色,且不同循环之间没有影响。

能得到 T(p)=m^{d(p)}。

回到题目, G 中有两个置换 : e,\begin{pmatrix}1&2&3&4&5&6\\6&5&4&3&2&1\end{pmatrix}。

后者有循环节 (1,2)(3,4)(5,6) ,则贡献为 4^3

前者有循环节 (1)(2)(3)(4)(5)(6) ,则贡献为 4^6

总方案数是 \dfrac{1}{2}(4^6+4^3)。

3. 习题

P4980 【模板】Polya定理

这道题里的置换就是旋转。

有旋转 0...n-1 格的置换,共 n 个。

设 p_i=\begin{pmatrix}1&2&...&n-i&n-i+1&...&n\\1+i&2+i&...&n&1&...&i\\\end{pmatrix} (旋转 i 格)

Polya式子 : \dfrac{1}{n}\sum\limits_{i=0}^{n-1}n^{d(p_i)}

暴力 : 根据上文介绍的方法，对每个置换缩点求循环个数 d(p) ,复杂度 O(n^2)。

打表或者拿出草稿纸画了一通后,你会发现 d(p_i)=\gcd(n,i)。

若每次跳 $i$ 步,在长度为 $n$ 的环上,多少次才能回到原点呢? 当 $i\perp n$ 时,可以证明 $0,i,2i,3i...(n-1)i$ 在$\pmod n$ 意义下互不相同。此时的答案就是 $n$。若 $i\not\perp n$ ,采用模分类,设 $d=\gcd(i,n)$ ,若从 $0$ 开始,不难发现 $d\!\!\not|\ i$ 的位置都是无用的。这就变成了子问题 $\frac{n}{d},\frac{i}{d}$ ,此时两者互质,答案就是 $\frac{n}{d}$。

得 {\rm Ans}=\dfrac{1}{n}\sum\limits_{i=1}^nn^{gcd(n,i)}

相信已近在学习群论的你,一定能把这道数论水题秒掉的。

=\dfrac{1}{n}\sum\limits_{d|n}k^d\sum\limits_{i=1}^n[\gcd(n,i)=d]

后面的 \sum\limits_{i=1}^n[\gcd(n,i)=d]
=\sum\limits_{i=1}^{n/d}[n\perp i]=\varphi(n/d)

整理得 {\rm Ans}=\sum\limits_{d|n}\varphi(d)k^{n/d}

大力求欧拉函数大概是O(\sqrt{n}\log n)的样子(反正快速幂也是这个复杂度)。

然而还有一个质因数分解+dfs凑出所有因数+光速幂的 O(\sqrt{n}) 解法,懒得写。

Code:

#include<algorithm>
#include<cstdio>
#define ll long long 
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
int phi(int n)
{
  int ans=n;
  for (int i=2;i*i<=n;i++)
   if (n%i==0){
     ans=ans/i*(i-1);
     while(n%i==0)n/=i;
   }
  if (n>1)ans=ans/n*(n-1);
  return ans;
}
void solve(int n)
{
  ll ans=0;
  for (int i=1;i*i<=n;i++)
    if (n%i==0){
      if (i*i!=n)ans=(ans+powM(n,n/i-1)*phi(i))%mod;
      ans=(ans+powM(n,i-1)*phi(n/i))%mod;
    }
  printf("%lld\n",ans);
}
int T,n;
int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d",&n);
    solve(n);
  }return 0;
}

P4727 [HNOI2009]图的同构记数

第一眼这道题以为是子集\rm DP或者容斥什么的,结果数据范围 n\leq 60? 怕不是有多项式算法?

今早闲得无聊拿着《组合数学(第4版)》看了看,里面居然有讲到这个问题。

边 (有,无) 的状态可以看做对一个完全图染色,某条边染成黑色说明存在,染成白色就假装不存在,我们成功地把这个问题转化成了一个染色计数问题。

我们先看看式子 : \dfrac{1}{|G|}\sum\limits_{p∈G}T(p)

我们现在是在对边计数,但是我们的置换是所有的点置换。

显然,可以由点置换构造出边置换,但是点置换的个数是 n! 的,无法直接枚举。我们需要找到更好的性质来批量处理。

万幸的是, 点置换循环节的构成 和 边置换的不动点个数 有一定的关系。

考虑一个点置换,他每个循环的大小为 \{S_1,S_2,S_3,...S_m\} (m为循环节个数,且 S_1\leq S_2\leq ...\leq S_m)

能够感知,所有循环节组成相同的点置换,边的等价类个数是相同的。

也就是说我们只要枚举 S ,也就是 n 的正整数拆分,就能确定一类边置换。

而正整数拆分的数量级是 O(e^{\sqrt{\frac{2}{3}n\pi}}) ,是亚指数的。本题中极限情况仅在百万级。

现在,对于一组 S ,计算出这个完全图会究竟会被分成多少个等价类,设其为 c ,根据 \rm Polya 那么不动点个数就是 2^c。

对于循环节内的边,会被分为\left\lfloor\dfrac{S}{2}\right\rfloor个等价类。

理解 : 我们可以把这个循环节看成一个圈,由于这个圈会转,肯定会让某些边相同。

循环内节点按 1...S 编号,假设有边 (1,p) ,那么边 (2,p+1) , (3,p+2) ……和 (S-p+1,S) 肯定都和 (1,p) 相同。

我们枚举p,会发现 p>\left\lfloor\dfrac{S}{2}\right\rfloor 的情况会和 p\leq \left\lfloor\dfrac{S}{2}\right\rfloor的情况重复。

如图 : 左边 S=8 ,等价类数为 \left\lfloor\dfrac{8}{2}\right\rfloor=4 ; \quad 右边 S=7 ,等价类数为 \left\lfloor\dfrac{7}{2}\right\rfloor=3。
对于两个循环节之间的边,会被分为gcd(S_1,S_2)个等价类。

理解 : 我们还是采用圈来理解,由于这个两个圈都会转,情况有点复杂。

循环内节点按 1...S_1 与 1...S_2 编号,假设有边 (x,y) ,那么有多少条边和这条边相同呢?

这等价于考虑 : 这条边会在多少次置换后回到原位 ?

答案是 lcm(S_1,S_2) ,如果不理解的话,想象着两个齿轮咬合着转。

那么每个等价类的边得个数为 lcm(S_1,S_2) ,边的总数为 nm ,则等价类的总数是 \dfrac{nm}{lcm(S_1,S_2)}=gcd(S_1,S_2)

如图 : 左边 S_1=4,S_2=2 ,等价类数为 gcd(2,4)=2;

第一个等价类的边 (1,1),(2,2),(3,1),(4,2)

第二个等价类的边 (1,2),(2,1),(3,2),(4,1)

那么根据上述,对于循环节大小为 \{S_1,S_2,S_3,...S_m\} 的点置换,其对应的边置换的贡献为:

\large{2^{\small\sum\limits_{i=1}^m\lfloor\frac{S_i}{2}\rfloor+\sum\limits_{i=1}^m\sum\limits_{j=i+1}^mgcd(S_i,S_j)}}

我们接下来还要算循环节大小为 \{S_1,S_2,S_3,...S_m\} 的点置换有几个。

我们考虑把 \{1,2,3,...,n\} 分成 m 个集合,大小分别为 \{S_1,S_2,S_3,...S_m\}。

我们考虑生成一个长为 n 的排列,然后按照 S 分成 m 组,其实就是多重排列问题。

得 \dfrac{n!}{\Pi_{i=1}^mS_i!}

如果有两个 S 相同,是可以调换顺序的,所以还要除掉一些东西。

设 B_i 为 S=i 的个数,得 \dfrac{n!}{\Pi_{i=1}^mS_i!*\Pi_{i=1}^nB_i!}

我们还要在每个集合内连边,使得它构成一个循环。

> 可以视作把 $n$ 元链首尾相,由于旋转,每个换对应 $n$ 个链,方案数即为 $n!/n=(n-1)!$。乘回划分集合的方案数,得到$\dfrac{n!*\Pi_{i=1}^m(S_i-1)!}{\Pi_{i=1}^mS_i!*\Pi_{i=1}^nB_i!}=\dfrac{n!}{\Pi_{i=1}^mS_i*\Pi_{i=1}^nB_i!}

然后在乘上对应的边置换的贡献,得到

\dfrac{n!}{\Pi_{i=1}^mS_i*\Pi_{i=1}^nB_i!}*\large{2^{\small\sum\limits_{i=1}^m\lfloor\frac{S_i}{2}\rfloor+\sum\limits_{i=1}^m\sum\limits_{j=i+1}^mgcd(S_i,S_j)}}

别忘了除以置换个数 n!。

最后注意实现复杂度和常数,小心被卡。

Code:

#include<cstdio>
using namespace std;
const int mod=997;
int n;
int powM(int a,int t=mod-2){
  int ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
int facn,inv[66],ifac[66],gcd[66][66],
    s[66],b[66],ans;
void dfs(int num,int pos,int last)
{
  if (num==0){
    int t=0,sav=facn;
    for (int i=1;i<=n;i++)b[i]=0;
    for (int i=1;i<pos;i++)b[s[i]]++;
    for (int i=1;i<=n;i++)sav=sav*ifac[b[i]]%mod;
    for (int i=1;i<pos;i++)sav=sav*inv[s[i]]%mod;
    for (int i=1;i<pos;i++)
      for (int j=i+1;j<pos;j++)
        t+=gcd[s[i]][s[j]];
    for (int i=1;i<=n;i++)t+=s[i]/2;
    sav=sav*powM(2,t)%mod;
    ans=(ans+sav)%mod;
    return ;
  }if (last>num)last=num;
  for (int i=1;i<=last;i++){
    s[pos]=i;
    dfs(num-i,pos+1,i);
  }
}
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++)inv[i]=powM(i);
  ifac[0]=1;
  for (int i=1;i<=n;i++)
    ifac[i]=ifac[i-1]*inv[i]%mod;
  facn=powM(ifac[n]);
  for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
      for (int k=1;k<=n;k++)
        if (i%k==0&&j%k==0)gcd[i][j]=k;
  dfs(n,1,n);
  printf("%d",ans*ifac[n]%mod);
  return 0;
}

类似的题目 : P4128 [SHOI2006]有色图

题解 P4916 【魔力环】