本人不确保结果正确性。
类似的题集也很多，比如 https://ac.nowcoder.com/acm/contest/27275#question
我做了部分题目的题解 https://www.cnblogs.com/yhm138/articles/15847432.html
目录
Burnside引理
例题1.1
例题1.2
例题1.3
Polya定理
例题2.1
例题2.2
例题2.3
例题2.4
例题2.5
都是利用了群论研究计数问题。它们联系密切，可以从Burnside引理推出Polya定理。
记\(c(f)\)是置换\(f\)的圆分解后cycle个数，颜色数\(m\)
其实Polya定理就是说置换\(f\)的不动点个数为\(m^{c(f)}\)。
(因为对每个cycle而言，其中的各元素都涂相同种颜色才会在置换\(f\)作用下保持不变)
Burnside引理
用\(D(a_j)\)表示在置换\(a_j\)下不变的元素的个数。\(L\)表示本质不同的方案数目。
\[L=\frac{1}{|G|}\sum\limits_{j=1}^{s}D(a_j)
\]
用中文表述Burnside引理的话，
集合\(M\)关于置换群\(G\)的等价类数目，等于\(G\)中每个置换下不动点的个数的算术平均数。
例题1.1
问你长为4的01构成的环有多少种？
对应的置换群是\(\mathbb{Z_4}\)群
记\(a_1\)是恒等变换\(\begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{pmatrix}\)，\(a_2\)是\(\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}\)，\(a_3\)是\(\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{pmatrix}\)，\(a_4\)是\(\begin{pmatrix} 1 & 2 & 3 & 4 \\4 & 1 & 2 & 3 \end{pmatrix}\)
在置换\(a_1\)下不变有16种(全部长度为4的01排列共\(2^4种\))
在置换\(a_2\)下不变有2种 0000和1111
在置换\(a_3\)下不变有4种 0000和1111和1010和0101
在置换\(a_4\)下不变有2种 0000和1111
\[L=\frac{1}{4}(16+2+4+2)=6
\]
例题1.2
写个特没意思的，现在想知道3-排列集合在\(\mathbb{S_3}\)群下的等价类个数
\[1=\frac{1}{6}(0+0+0+0+0+6)
\]
例题1.3
问你八面体配合物 Mabcdef 的异构体数目。考虑到正八面体和正六面体是对偶多面体，实际这也是正六面体的6个面做六染色(每个颜色都出现一次)的本质不同方案数目。
八面体的旋转群是\(\mathbb{S_4}\)
\[30=\frac{1}{4!}(6!+\underbrace{0+0+0+...+0}_{23个0})
\]
Polya定理
设\(G\)是\(p\)个对象的一个置换群，用\(m\)种颜色涂染\(p\)个对象，则不同染色方案为:
\[L=\frac{1}{|G|}(m^{c(g_1)}+m^{c(g_2)}+...+m^{c(g_s)})
\]
其中：\(G=\{g_1,g_2,...,g_{s}\}\)，\(c(g_i)\)为置换\(g_i\)的循环节数（即置换圆分解后的圆个数）
例题2.1
等边三角形的三个顶点用红绿蓝三种颜色来着色，问你本质不同的方案数。
对应的群是二面体群\(\mathbb{D_3}=\{(1)(2)(3),(123),(321),(1)(23),(2)(13),(3)(12)\}\)
\[L=\frac{1}{6}[(3)^3+(3)^1+(3)^1+(3)^2+(3)^2+(3)^2]=10
\]
\[\begin{aligned}
L(r,g,b)&=\frac{1}{6}\{(r+g+b)^3+(r^3+g^3+b^3)+(r^3+g^3+b^3)+[(r+g+b)(r^2+b^2+g^2)]+[(r+g+b)(r^2+b^2+g^2)]+[(r+g+b)(r^2+b^2+g^2)]\}\\
&=\frac{1}{6}\{6 b^3+6 b^2 g+6 b^2 r+6 b g^2+6 b g r+6 b r^2+6 g^3+6 g^2 r+6 g r^2+6 r^3\}
\end{aligned}
\]
如果想看特定颜色组合情形，用类似母函数的方法替换3为\((r+g+b)\)或\((r^2+g^2+b^2)\)或\((r^3+g^3+b^3)\)
比如\((1)(23)\)对应的就是\((r+g+b)(r^2+g^2+b^2)\)
\((123)\)对应的就是\((r^3+g^3+b^3)\)
例题2.2
正方体的4条体对角线用红蓝两种颜色着色，问你有多少种本质不同的着色方案。
对应的置换群是\(\mathbb{S_4}\)，里面的旋转诱导了(4根)体对角线的置换，并且由其确定。
把体对角线看成元素。
\(\mathbb{S_4}\)共有24个置换，
| 圆分解后圆的个数 | 这样的置换个数 |
|---|---|
| 1 | 6 |
| 2 | 11 |
| 3 | 6 |
| 4 | 1 |
\[\begin{aligned}
L&=\frac{1}{24}[\sum\limits_{i=1}^{4}S_1(4,i)\cdot2^i]\\
&=\frac{1}{24}(6\cdot2^1+11\cdot2^2+6\cdot2^3+1\cdot2^4)\\
&=5
\end{aligned}
\]
例题2.3
正方体的8个顶点用红蓝两种颜色着色，问你有多少种本质不同的着色方案。
有24个置换，这次把8个点看作元素
| 置换 | 圆分解后圆个数 | 这样的置换个数 |
|---|---|---|
| 恒等变换 | 8 | 1 |
| ① | 4 | 6 |
| ② | 4 | 8 |
| ③ | 2，4 | 6，3 |
| ①:对棱中点连线为转轴，对应一个180度旋转，这样的旋转轴有6个（对应6对相对的棱），故6个旋转 | ||
| ②:体对角线为转轴，对应一个120度或者240度旋转，这样的旋转轴有4个（对应4个主对角线），故8个旋转 | ||
| ③:对面中心连线为转轴，对应一个90,180,270度旋转，这样的旋转轴有3个（对应3个坐标方向），因此有3x3=9个旋转 |
\[\begin{aligned}
L&=\frac{1}{24}[1\cdot2^8+6\cdot2^4+8\cdot2^4+6\cdot2^2+3\cdot2^4]\\
&=23
\end{aligned}
\]
例题2.4
正方体的6个面用红蓝两种颜色着色，问你有多少种本质不同的着色方案。
有24个置换，这次把6个面看作元素
| 置换 | 圆分解后圆个数 | 这样的置换个数 |
|---|---|---|
| 恒等变换 | 6 | 1 |
| ① | 3 | 6 |
| ② | 2 | 8 |
| ③ | 3，4 | 6，3 |
\[\begin{aligned}
L&=\frac{1}{24}[1\cdot2^6+6\cdot2^3+8\cdot2^2+6\cdot2^3+3\cdot2^4]\\
&=10
\end{aligned}
\]
例题2.5
正四面体的4个顶点用红蓝两种颜色着色，问你有多少种本质不同的着色方案。
有12个置换：
恒等变换，1个
顶点和对面中点连线为转轴的120°或240°旋转，共8个
对棱中点连线为转轴的180°旋转，共3个
把4个顶点看作元素，
这是交错群\(\mathbb{A_4}=\{(0)(1)(2)(3),(123),(132),(021),(012),(031),(013),(023),(032),(01)(23),(03)(12),(02)(13)\}\)
\[L=\frac{1}{12}(1\cdot2^4+8\cdot2^2+3\cdot2^2)=5
\]
如果是给正四面体的4个面用红蓝两种颜色着色，答案也是5。把4个面看作元素，群也是交错群\(\mathbb{A_4}\)
我想到了以前算同分异构体的时候，当时还不知道Burnside引理和Polya定理，群论更是一窍不通。。。
我的入门书应该是Nathan Carter的Visual Group Theory
推荐这个github.ioGroupExplorer
