群
群是由一个集合及一个二元运算组成的代数结构，记为 \((G,\cdot)\).
其符合群公理，即满足封闭性，结合律，单位元，逆元。
子群
群 \((G,\cdot),(H,\cdot)\)，满足 \(H\subseteq G\)，则 \((H,\cdot)\) 是 \((G,\cdot)\) 的子群。
置换
一个有限集合 \(S\) 到自身的双射称为 \(S\) 的一个置换。集合 \(S=\{a_1,a_2,\dots,a_n\}\) 上的置换可表示为
\[f=\binom{a_1,a_2,\dots,a_n}{a_{p_1},a_{p_2},\dots,a_{p_n}} \]\(S\) 上的所有置换的总数显然为 \(n!\).
置换群
集合 \(S\) 上所有置换关于置换的乘法满足封闭性/结合律/有单位元（恒等置换，每个元素映射到自身）/有逆元（交换置换表示中的上下两行），因此构成一个群。
这个群的任意一个子群称为置换群。
循环置换
循环置换是一类特殊的置换，可表示为
\[\left(a_1,a_2,\dots,a_m\right)=\binom{a_1,a_2,\dots,a_{m-1},a_m}{a_2,a_3,\dots,a_m,a_1} \]若两个循环置换不含有相同的元素则称它们不相交。
- 任意一个置换可以分解为若干不相交的循环置换的乘积，如
连有向边后容易发现其就是若干环的集合。
共轭类
有相同格式的置换的全体构成一个共轭类。
置换群 \(S_n\) 中属于 \((1)^{c_1}(2)^{c_2}\dots(n)^{c_n}\)（长为 \(i\) 的循环有 \(c_i\) 个）共轭类的元素个数为
\[\frac{n!}{c_1!c_2!\dots c_n!\cdot1^{c_1}2^{c_2}\dots n^{c_n}} \]Burnside 引理
设 \(G=\{a_1,a_2,\dots,a_g\}\) 是集合 \(X\) 上的置换群。
把每个置换写成不相交的循环的乘积。
记 \(c_1(a_k)\) 为在置换 \(a_k\) 的作用下不动点的个数。
\(X\) 在 \(G\) 的作用下被分为若干等价类，即能在置换的作用下互相到达的元素被分为一类。
- 不同的等价类的个数为 \(\displaystyle L=\frac{1}{|G|}\Big[c_1(a_1)+c_1(a_2)+\dots+c_1(a_g)\Big]\)
证明：考虑形如 \((x,g)\) 的二元组，其中 \(x\in X\)，\(g\in G\)。那么这样的二元组共 \(|X||G|\) 个。
如果两个二元组 \((x,g)\) 和 \((y,h)\) 满足 \(h(y)=g(x)\)，称它们是等价的（或者说这是一个等价关系）。
根据等价关系可以将所有二元组划分为若干等价类，且每个等价类的大小都等于轨道的大小。
（这个轨道是什么？）
那么有
\[|X||G|=\sum_{\text{等价类}}|X_x| \]也可以按不同的 \(g\in G\) 计数：
\[|X||G|=\sum_{g\in G}|\{(x,g):x^g=x\}| \]里面指在 \(g\) 作用下不变的二元组的集合，它就等于 \(X^g\) 的大小，即
\[|X||G|=\sum_{g\in G}|X^g| \]联立等式有
\[\sum_{\text{等价类}}|X_x|=\sum_{g\in G}|X^g| \]除以 \(|G|\) 之后变成
\[L=\frac{1}{|G|}\Big[c_1(a_1)+c_1(a_2)+\dots+c_1(a_g)\Big] \]为什么呢？不管了。
给一个应用的例子：给 \(2\times2\) 的正方形涂两种颜色，球旋转后本质不同的方案数。
旋转 \(90/180/270/0\) 度不变的总方案数为 \(2,4,2,16\).
那么本质不同的总数即
\[\frac{\sum c_1=\{2,4,2,16\}}{|G|=4}=6 \]只能说有一定道理。
Polya 定理
设 \(G\) 是在有 \(n\) 个对象的集合上的一个置换群。用 \(m\) 种颜色对 \(n\) 个对象染色，不同的方案数为（经 \(G\) 置换后相同记为一种）
\[L=\frac{1}{|G|}\Big[m^{c(a_1)}+m^{c(a_2)}+\dots+m^{c(a_g)}\Big] \]即 Burnside 引理的一个推论。
Examples
- 对等边三角形的三个顶点染上 RGB 三种颜色的方案。旋转、翻转记为一种。
\(0\rightarrow(1)(2)(3)\rightarrow3^3\).
\(120\rightarrow(123)\rightarrow3\).
\(240\rightarrow(132)\rightarrow3\).
\(\operatorname{flip}0/120/240\rightarrow c=2\rightarrow3^2\).
总方案数为 \(\displaystyle\frac{3^3+2\times3^1+3\times3^2}{6}=10\).
- 对正四面体的四个顶点用四种颜色着色的方案数。
\((1)(2)(3)(4)\rightarrow 4^4\).
\((1)(234)\rightarrow{* } 2\times4\times4^2\)
\((12)(34)\rightarrow3\times4^2\).
方案数 \(\displaystyle\frac{4^4+8\times 4^2+3\times 4^2}{12}=36\).
可以尝试理解一下。
与生成函数的结合
如果现在用 RGB 给两个球染色。
\[(r+g+b)^2=r^2+g^2+b^2+2rg+2rb+2gb \]表示了 \(6\) 种不同类型的方案，系数为该种方案的数目。
对于长度为 \(i\) 的循环节，里面的每个对象都应染为相同的颜色，其染色方案表示为
\[b_1^i+b_2^i+\dots+b_m^i \]此置换 \(P\) 对应的染色方案为
\[\sum_{i=1}^{n}(b_1^i+b_2^i+\dots+b_m^i)^{c_i(P)} \]则生成函数形式的 Polya 定理为
\[\frac{1}{|G|}\sum_{P\in G}\sum_{i=1}^{n}(b_1^i+b_2^i+\dots+b_m^i)^{c_i(P)} \]模板题实际是由 Burnside 引理推到 Polya 定理的一个例子。
给环染色，本质不同指旋转。点、颜色数均为 \(n\).
\(T\le10^3\)，\(n\le 10^9\).
可以视作旋转 \(0\sim n-1\) 次的置换下得到的等价类的数量。
定义集合 \(M\) 为所有表示初始环的排列。
旋转 \(0\) 个的不动点的数量为 \(n^n\).
旋转 \(k\) 个时，一个元素为不动点即存在循环节的长度 \(a\) 满足 \(a|k\).
又因为一定有 \(a|n\)，那么就会存在长为 \(\gcd(k,n)\) 的循环节。
这是可以任取前 \(\gcd(k,n)\) 个，于是得到答案为：
\[\frac{1}{n}\sum_{k=1}^{n}n^{\gcd(k,n)} \]反演一下得到
\[\frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d}) \]暴力计算 \(\varphi\)，本题复杂度 \(O(Tn^{\frac{3}{4}})\).
标签：dots,frac,cdot,Big,置换,相关,sum From： https://www.cnblogs.com/SError0819/p/17609925.html