「学习总结」群 置换群

📅 Last Updated: 2020-12-29
📊 Word Count: 1891
⏱️ Estimated Reading Time: 13 minutes
📄 PDF 📝 Source

群，一种特殊的代数结构，满足封闭性、结合律、存在幺元和对于每个元素存在逆元的四种性质。

置换群，一种特殊的群，其中的元素描述了一种交换操作。 # 群论简介 ## 定义 称 集合 SS 和 SS 上运算 ⋅\cdot，共同构成得代数结构记作 (S,⋅)(S, \cdot)，为一个群，当且仅当其满足如下性质：

  • S≠∅S \not = \varnothing
  • 封闭性：∀a,b∈S,a⋅b∈S\forall a, b\in S, a\cdot b \in S
  • 结合律：∀a,b,c∈S,a⋅(b⋅c)=(a⋅b)⋅c\forall a, b, c\in S, a \cdot (b \cdot c)= (a \cdot b) \cdot c
  • 幺元：∃e∈S,∀a∈S,e⋅a=a⋅e=a\exists e \in S, \forall a \in S, e \cdot a = a \cdot e= a
  • 逆元：∀a∈S,∃b∈S,a⋅b=e\forall a \in S, \exists b \in S, a \cdot b = e

几个栗子

  • 实数集与实数间的乘法 (R,×)(\mathbb{R}, \times) 不是群，元素 0∈R0 \in \mathbb{R}，但是 00 不存在逆元。
  • (R′,×)(\mathbb{R'}, \times) 是一个群，幺元为 11。 其中 R′= x ∣ x∈R ∧ x≠0 \mathbb{R'} = \\{\ x\ |\ x\in \mathbb{R}\ \land \ x \not = 0\ \\}
  • (Z,+)(\mathbb{Z}, +) 是一个群，幺元是 00。
  • (R,+)(\mathbb{R}, +) 是一个群，幺元是 00。
  • (P,×)(\mathbb{P}, \times) 是一个群，幺元是 11 ，其中 PP 为某个质数的剩余系。

一类特殊的群

  • 阿贝尔群：除了满足群的性质，还需要满足 a⋅b=b⋅aa \cdot b = b \cdot a 即 交换律。

置换群

不严谨定义

把 11 ~ nn 个对象 进行交换操作的群，置换群中集合的元素描述了一种交换操作。 对应的，置换群的运算就是分别执行两种交换操作。

一种描述交换操作（置换）的记号。

举个栗子： 给执行交换操作前的元素依次编号为 1,2,3,41, 2, 3, 4（对编号后，编号为 ii 元素简称元素 i） ，交换操作后变为 3,1,2,43, 1, 2, 4。

可以描述成 (1,2,3)(4)(1, 2, 3)(4)，读作：将元素 11 换到位置 22，将元素 22，换到位置 33，将元素 33 换至位置 11，将元素 44 换至位置 44。

可以考虑成： 一张包含 nn 个点的图，然后使 点ii 与 点aia_i 有边相连。对于每个连通块来说，图的形态一定是一个环，从环上一个点开始按照任意方向遍历图，得到的遍历顺序就是上面描述中的一个括号内的内容。联通块的个数就是上面描述中的括号数量，其实这个可以被称为轨道数。

交换群的栗子： 一个对 33 个元素的交换群：e,(1,2)(3),(1,3)(2),(1,2,3),(1,3,2),(2,3)(1)\\{e,(1,2)(3),(1,3)(2),(1,2,3),(1,3,2),(2,3)(1)\\}

(1)(2)⋯(n)(1)(2) \cdots (n) 简记为 ee 即 对原元素不做交换。

burnside 引理

简化定义

设要对 nn 个元素用 mm 种颜色染色，对应置换群为 SS，在该置换群下任意一种得到的相同方案算同一种方案。求本质不同的染色方案数。

根据 burnside 引理，其答案为。

ANS=1∣S∣∑s∈Smη(s)(1) ANS = \frac{1}{|S|}\sum_{s \in S}\limits{m^{\eta(s)}} \qquad{(1)}

其中 η(s)\eta(s) 为置换方案 ss 的轨道数。 这是关于 burnside 引理的一个简化版定义。

一个栗题： nn 个排成一圈的点用 mm 种颜色染色，问方案数（旋转前后的方案为一种方案）.

显然需要解决两个问题： - 置换群的构造. - 置换群元素轨道数目.

考虑这个置换群的置换集合可以是什么： (假设 nn 为 66). S={(1)(2)(3)(4)(5)(6),(1,2,3,4,5,6),(1,3,5)(2,4,6)(1,4)(2,5)(3,6)(1,5,3)(2,6,4)(1,6,5,4,3,2)} S = \begin{Bmatrix} (1)(2)(3)(4)(5)(6), \\\\ (1, 2, 3, 4, 5, 6), \\\\ (1, 3, 5) (2, 4, 6) \\\\ (1, 4) (2, 5) (3, 6) \\\\ (1, 5, 3) (2, 6, 4) \\\\ (1, 6, 5, 4, 3, 2) \\\\ \end{Bmatrix} 分别对应转动的位置个数为 00 ~ n−1n - 1。稍微模拟一下这个过程，显然移动 kk 个位置的方案，轨道数为 gcd⁡(k,n)\operatorname{gcd}(k, n). 然后就一般化了.

完整定义

设 AA 和 BB 为有限集合，X=BAX = B^A 表示从 AA 到 BB 的映射。GG 是 AA 上置换群，X/GX / G 表示 GG 作用在 XX 上产生的所有等价类集合，若存在两种映射经过 GG 的置换作用后是相同的，则将两种映射视为同一种。 burnside 引理指出：

∣X/G∣=1∣G∣∑g∈G∣Xg∣(2) |X / G| = \frac{1}{|G|}\sum_{g \in G} \limits{|X^g|} \qquad{(2)}

其中 XgX^g 表示在映射集合 XX 中有多少元素可以经过 gg 的变化，变成一样的。

考虑与之前定义 (eq.~eq. 1) 的联系： - 一种染色方案可以看成 元素 和 颜色 的映射。 - 对于置换 ss ，如果要保证其作用前后映射方案相同，必须要保证其同轨道内的元素被映射到了同一元素，即 染成了相同的颜色。 - 那么考虑置换 ss 的每一条轨道 η\eta，每一条轨道颜色相同的方案数就是 mη(s)m^{\eta(s)} - 这与 (eq.~eq. 2) 的定义是相符的。

一道例题 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。

现在有一个迷宫，这个迷宫是由若干个正 n(=4,6)n(=4,6) 边形组成的k层迷宫。如果 k=1k=1 ，那么该迷宫就由单独一个正 nn 边形组成；如果 k>1k>1，则在 k−1k−1 层的基础上，沿着所有最外层的边增加一个正 nn 边形，新增加的正 nn 边形若有重叠，则保留其中一个即可。具体可以参考下图：

现在为了打破迷宫的结界，你需要在迷宫的某些边上开一扇门。你总共需要开 rr 扇门，每条边最多打开一扇门。但是如果两种开门的方案通过旋转相同，那么视为同一种方案。以及由于是死亡迷宫，所以死了也是可以的，所以你并不需要保证你开门的方案能够让你走出去。求总共的方案数。

现在可以简化一下描述一种操作的语言，burnside 引理 不关心置换的具体对象，只关心置换的大小和出现次数。可以用简写 (a)b(a)^b 表示：有 bb 个长度为 aa 的轨道。 先特殊考虑一下 k=2k = 2 的情况，一共有 1616 条边。可以分为转 0o,90o,180o,270o0^o,90^o,180^o, 270^o. - 转 0o0^o 的置换，可以描述为 (1)16(1)^{16}. - 转 90o90^o 的置换，可以描述为 (4)4(4)^4. - 转 180o180^o 的置换，可以描述为 (2)8(2)^8. - 转 270o270^o 的置换，可以描述为 (4)4(4)^4.

特殊化一下，不难发现就是：（一共有 4k24k^2 条边）

  • 转 0o0^o 的置换，可以描述为 (1)4k2(1)^{4k^2}.
  • 转 90o90^o 的置换，可以描述为 (4)k2(4)^{k^2}.
  • 转 180o180^o 的置换，可以描述为 (2)2k2(2)^{2k^2}.
  • 转 270o270^o 的置换，可以描述为 (4)k2(4)^{k^2}.

根据 XgX^g 的定义——表示在映射集合 XX 中有多少元素可以经过 gg 的变化，变成一样的。我们始终要保证对于一种置换，同一轨道的元素完全相同. 所以对于第一种置换，贡献就是在轨道数中选出 rr 个让他们都变成 “有门存在” 的状态，即 (4k2r)\dbinom{4k^2}{r}. 其余的同理，答案就是。 14∑g∈G(η(g)rt) \frac{1}{4}\sum_{g\in G}\limits{\dbinom{\eta(g)}{\frac{r}{t}}} 其中 tt 为 轨道 gg 的循环长度。 当 rt\frac{r}{t} 不是整数的时候，贡献为 00 ，因为 不存在某种染色方法，使得这种置换中同轨道的元素颜色相同.

适用于立体图形的 burnside 引理

包括对正 nn 面体和足球的 面，点或棱染色。 #### 立方体面染色 首先讨论置换群： 考虑正方体有 1212 条棱，66 个面，88 个点。

旋转轴类型 角度 数量 置换
不转 0o0^o 1 (1)6(1)^6
面面 90o90^o 3 (1)2(4)1(1)^2(4)^1
面面 180o180^o 3 (1)2(2)2(1)^2(2)^2
面面 270o270^o 3 (1)2(4)1(1)^2 (4)^1
棱棱 180o180^o 6 (2)3(2)^3
点点 120o120^o 4 (3)2(3)^2
点点 240o240^o 4 (3)2(3)^2

关于角度的确定：观察旋转轴图形周围的形状。数量为总数的一半。

正十二面体染色

2020 个点，1212 个面，3030 条棱，面为五边形。

循环节：即对于一种置换方案的轨道长度。简单理解为转多少次能够转到原来的位置。

旋转轴类型 角度 循环节 数量 面染色置换群 边染色置换群 点染色置换群
不转 0o0^o 1 1 (1)12(1)^{12} (1)30(1)^{30} (1)20(1)^{20}
面面轴 72o72^o 5 6 (1)2(5)2(1)^2(5)^2 (5)6(5)^6 (5)4(5)^4
面面轴 144o144^o 5 6 (1)2(5)2(1)^2(5)^2 (5)6(5)^6 (5)4(5)^4
面面轴 216o216^o 5 6 (1)2(5)2(1)^2(5)^2 (5)6(5)^6 (5)4(5)^4
点点轴 120o120^o 3 10 (3)4(3)^4 (3)10(3)^{10} (1)2(3)6(1)^2(3)^6
点点轴 240o240^o 3 10 (3)4(3)^4 (3)10(3)^{10} (1)2(3)6(1)^2(3)^6
棱棱轴 180o180^o 2 15 (2)6(2)^6 (1)2(2)14(1)^2(2)^{14} (2)10(2)^{10}

以某个对象为旋转轴，其置换群中必然有两个长度为 11 的轨道，作为旋转轴的对象，旋转前后应该是重叠的。 然后剩下的根据轨道循环节直接算出即可。 可以发现这是一个无脑的工作

足球的置换群

实在不想写了…… 足球的点数不好求，但是可以根据立体图形外角和公式求出： 立体图形外角和为 720o720^o 。 即 点数×外角度=720o\text{点数} \times \text{外角度} = 720^o.

例题：

待填。

题外话

📚 Version History

Source Code Change History
v1
🔗 Source Hash: d80ff91a18e5045662ee06d4e4b4fcef75e3adc11c9c8c52323dd5ee7ee3bc51
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」群 置换群.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache/oi-blog_「学习总结」群 置换群.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../95150feaf9.pdf.md', '-o', 'cache/95150feaf9.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[WARNING] Could not fetch resource /post_images/qun_0.png: /post_images/qun_0.png: withBinaryFile: does not exist (No such file or directory)
  Replacing image with description.
[WARNING] Could not fetch resource /post_images/qun_1.png: /post_images/qun_1.png: withBinaryFile: does not exist (No such file or directory)
  Replacing image with description.
[WARNING] Could not fetch resource /post_images/qun_2.png: /post_images/qun_2.png: withBinaryFile: does not exist (No such file or directory)
  Replacing image with description.
[WARNING] Could not fetch resource /post_images/qun_3.png: /post_images/qun_3.png: withBinaryFile: does not exist (No such file or directory)
  Replacing image with description.
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \usepackage{longtable,booktabs,array}
  \usepackage{calc} % for calculating minipage widths
  % Correct order of tables after \paragraph or \subparagraph
  \usepackage{etoolbox}
  \makeatletter
  \patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{}
  \makeatother
  % Allow footnotes in longtable head/foot
  \IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}}
  \makesavenoteenv{longtable}
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「学习总结」群 置换群},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」群 置换群}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-12-29 07:09:41}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  群，一种特殊的代数结构，满足封闭性、结合律、存在幺元和对于每个元素存在逆元的四种性质。
  
  置换群，一种特殊的群，其中的元素描述了一种交换操作。 \# 群论简介 \#\#
  定义 称 集合 \(S\) 和 \(S\) 上运算 \(\cdot\)，共同构成得代数结构记作
  \((S, \cdot)\)，为一个群，当且仅当其满足如下性质：
  
  \begin{itemize}
  \tightlist
  \item
    \(S \not = \varnothing\)
  \item
    封闭性：\(\forall a, b\in S, a\cdot b \in S\)
  \item
    结合律：\(\forall a, b, c\in S, a \cdot (b \cdot c)= (a \cdot b) \cdot c\)
  \item
    幺元：\(\exists e \in S, \forall a \in S, e \cdot a = a \cdot e= a\)
  \item
    逆元：\(\forall a \in S, \exists b \in S, a \cdot b = e\)
  \end{itemize}
  
  \subsection{几个栗子}\label{ux51e0ux4e2aux6817ux5b50}
  
  \begin{itemize}
  \tightlist
  \item
    实数集与实数间的乘法 \((\mathbb{R}, \times)\) 不是群，元素
    \(0 \in \mathbb{R}\)，但是 \(0\) 不存在逆元。
  \item
    \((\mathbb{R'}, \times)\) 是一个群，幺元为 \(1\)。 其中
    \(\mathbb{R'} = \\{\ x\ |\ x\in \mathbb{R}\ \land \ x \not = 0\ \\}\)
  \item
    \((\mathbb{Z}, +)\) 是一个群，幺元是 \(0\)。
  \item
    \((\mathbb{R}, +)\) 是一个群，幺元是 \(0\)。
  \item
    \((\mathbb{P}, \times)\) 是一个群，幺元是 \(1\) ，其中 \(P\)
    为某个质数的剩余系。
  \end{itemize}
  
  \subsection{一类特殊的群}\label{ux4e00ux7c7bux7279ux6b8aux7684ux7fa4}
  
  \begin{itemize}
  \tightlist
  \item
    \textbf{阿贝尔群}：除了满足群的性质，还需要满足
    \(a \cdot b = b \cdot a\) 即 \textbf{交换律}。
  \end{itemize}
  
  \section{置换群}\label{ux7f6eux6362ux7fa4}
  
  \subsection{不严谨定义}\label{ux4e0dux4e25ux8c28ux5b9aux4e49}
  
  把 \(1\) \textasciitilde{} \(n\) 个对象
  进行交换操作的群，置换群中集合的元素描述了一种交换操作。
  对应的，置换群的运算就是分别执行两种交换操作。
  
  一种描述交换操作（置换）的记号。
  
  \textbf{举个栗子：} 给执行交换操作前的元素依次编号为
  \(1, 2, 3, 4\)（对编号后，编号为 \(i\) 元素简称元素 i） ，交换操作后变为
  \(3, 1, 2, 4\)。
  
  可以描述成 \((1, 2, 3)(4)\)，读作：将元素 \(1\) 换到位置 \(2\)，将元素
  \(2\)，换到位置 \(3\)，将元素 \(3\) 换至位置 \(1\)，将元素 \(4\)
  换至位置 \(4\)。
  
  \textbf{可以考虑成：} 一张包含 \(n\) 个点的图，然后使 点\(i\) 与
  点\(a_i\)
  有边相连。对于每个连通块来说，图的形态一定是一个环，从环上一个点开始按照任意方向遍历图，得到的遍历顺序就是上面描述中的一个括号内的内容。联通块的个数就是上面描述中的括号数量，其实这个可以被称为轨道数。
  
  \textbf{交换群的栗子}： 一个对 \(3\)
  个元素的交换群：\(\\{e,(1,2)(3),(1,3)(2),(1,2,3),(1,3,2),(2,3)(1)\\}\)
  
  \((1)(2) \cdots (n)\) 简记为 \(e\) 即 对原元素不做交换。
  
  \subsection{burnside 引理}\label{burnside-ux5f15ux7406}
  
  {} {}
  
  \subsubsection{简化定义}\label{ux7b80ux5316ux5b9aux4e49}
  
  设要对 \(n\) 个元素用 \(m\) 种颜色染色，对应置换群为
  \(S\)，在该置换群下任意一种得到的相同方案算同一种方案。求本质不同的染色方案数。
  
  根据 burnside 引理，其答案为。
  
  \[
  ANS = \frac{1}{|S|}\sum_{s \in S}\limits{m^{\eta(s)}}
  \] \{\#eq:bns\}
  
  其中 \(\eta(s)\) 为置换方案 \(s\) 的轨道数。 这是关于 burnside
  引理的一个\textbf{简化版}定义。
  
  \textbf{一个栗题}： \(n\) 个排成一圈的点用 \(m\)
  种颜色染色，问方案数（旋转前后的方案为一种方案）.
  
  显然需要解决两个问题： - 置换群的构造. - 置换群元素轨道数目.
  
  考虑这个置换群的置换集合可以是什么： (假设 \(n\) 为 \(6\)). \[
  S = \begin{Bmatrix}
  (1)(2)(3)(4)(5)(6), \\\\
  (1, 2, 3, 4, 5, 6), \\\\
  (1, 3, 5) (2, 4, 6) \\\\
  (1, 4) (2, 5) (3, 6) \\\\
  (1, 5, 3) (2, 6, 4) \\\\
  (1, 6, 5, 4, 3, 2) \\\\
  \end{Bmatrix}
  \] 分别对应转动的位置个数为 \(0\) \textasciitilde{}
  \(n - 1\)。稍微模拟一下这个过程，显然移动 \(k\) 个位置的方案，轨道数为
  \(\operatorname{gcd}(k, n)\). 然后就一般化了.
  
  \subsubsection{完整定义}\label{ux5b8cux6574ux5b9aux4e49}
  
  设 \(A\) 和 \(B\) 为有限集合，\(X = B^A\) 表示从 \(A\) 到 \(B\)
  的映射。\(G\) 是 \(A\) 上置换群，\(X / G\) 表示 \(G\) 作用在 \(X\)
  上产生的所有等价类集合，若存在两种映射经过 \(G\)
  的置换作用后是相同的，则将两种映射视为同一种。 burnside 引理指出：
  
  \[
  |X / G| = \frac{1}{|G|}\sum_{g \in G} \limits{|X^g|}
  \] \{\#eq:burnside\}
  
  其中 \(X^g\) 表示在映射集合 \(X\) 中有多少元素可以经过 \(g\)
  的变化，变成一样的。
  
  考虑与之前定义 (eq.\textasciitilde{}@eq:bns) 的联系： -
  一种染色方案可以看成 元素 和 颜色 的映射。 - 对于置换 \(s\)
  ，如果要保证其作用前后映射方案相同，必须要保证其同轨道内的元素被映射到了同一元素，即
  染成了相同的颜色。 - 那么考虑置换 \(s\) 的每一条轨道
  \(\eta\)，每一条轨道颜色相同的方案数就是 \(m^{\eta(s)}\) - 这与
  (eq.\textasciitilde{}@eq:burnside) 的定义是相符的。
  
  \textbf{一道例题}
  众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
  
  现在有一个迷宫，这个迷宫是由若干个正 \(n(=4,6)\) 边形组成的k层迷宫。如果
  \(k=1\) ，那么该迷宫就由单独一个正 \(n\) 边形组成；如果 \(k>1\)，则在
  \(k−1\) 层的基础上，沿着所有最外层的边增加一个正 \(n\) 边形，新增加的正
  \(n\) 边形若有重叠，则保留其中一个即可。具体可以参考下图：
  
  {}
  
  现在为了打破迷宫的结界，你需要在迷宫的某些边上开一扇门。你总共需要开
  \(r\)
  扇门，每条边最多打开一扇门。但是如果两种开门的方案通过旋转相同，那么视为同一种方案。以及由于是死亡迷宫，所以死了也是可以的，所以你并不需要保证你开门的方案能够让你走出去。求总共的方案数。
  
  现在可以简化一下描述一种操作的语言，burnside 引理
  不关心置换的具体对象，只关心置换的大小和出现次数。可以用简写 \((a)^b\)
  表示：有 \(b\) 个长度为 \(a\) 的轨道。 先特殊考虑一下 \(k = 2\)
  的情况，一共有 \(16\) 条边。可以分为转 \(0^o,90^o,180^o, 270^o\). - 转
  \(0^o\) 的置换，可以描述为 \((1)^{16}\). - 转 \(90^o\)
  的置换，可以描述为 \((4)^4\). - 转 \(180^o\) 的置换，可以描述为
  \((2)^8\). - 转 \(270^o\) 的置换，可以描述为 \((4)^4\).
  
  特殊化一下，不难发现就是：（一共有 \(4k^2\) 条边）
  
  \begin{itemize}
  \tightlist
  \item
    转 \(0^o\) 的置换，可以描述为 \((1)^{4k^2}\).
  \item
    转 \(90^o\) 的置换，可以描述为 \((4)^{k^2}\).
  \item
    转 \(180^o\) 的置换，可以描述为 \((2)^{2k^2}\).
  \item
    转 \(270^o\) 的置换，可以描述为 \((4)^{k^2}\).
  \end{itemize}
  
  根据 \(X^g\) 的定义——表示在映射集合 \(X\) 中有多少元素可以经过 \(g\)
  的变化，变成一样的。我们始终要保证对于一种置换，同一轨道的元素完全相同.
  所以对于第一种置换，贡献就是在轨道数中选出 \(r\) 个让他们都变成
  “有门存在” 的状态，即 \(\dbinom{4k^2}{r}\). 其余的同理，答案就是。 \[
     \frac{1}{4}\sum_{g\in G}\limits{\dbinom{\eta(g)}{\frac{r}{t}}}
  \] 其中 \(t\) 为 轨道 \(g\) 的循环长度。 当 \(\frac{r}{t}\)
  不是整数的时候，贡献为 \(0\) ，因为
  不存在某种染色方法，使得这种置换中同轨道的元素颜色相同.
  
  \subsubsection{适用于立体图形的 burnside
  引理}\label{ux9002ux7528ux4e8eux7acbux4f53ux56feux5f62ux7684-burnside-ux5f15ux7406}
  
  包括对正 \(n\) 面体和足球的 面，点或棱染色。 \#\#\#\# 立方体面染色
  首先讨论置换群： 考虑正方体有 \(12\) 条棱，\(6\) 个面，\(8\) 个点。
  
  \begin{longtable}[]{@{}llll@{}}
  \toprule\noalign{}
  旋转轴类型 & 角度 & 数量 & 置换 \\
  \midrule\noalign{}
  \endhead
  \bottomrule\noalign{}
  \endlastfoot
  不转 & \(0^o\) & 1 & \((1)^6\) \\
  面面 & \(90^o\) & 3 & \((1)^2(4)^1\) \\
  面面 & \(180^o\) & 3 & \((1)^2(2)^2\) \\
  面面 & \(270^o\) & 3 & \((1)^2 (4)^1\) \\
  棱棱 & \(180^o\) & 6 & \((2)^3\) \\
  点点 & \(120^o\) & 4 & \((3)^2\) \\
  点点 & \(240^o\) & 4 & \((3)^2\) \\
  \end{longtable}
  
  关于角度的确定：观察旋转轴图形周围的形状。数量为总数的一半。
  
  \paragraph{正十二面体染色}\label{ux6b63ux5341ux4e8cux9762ux4f53ux67d3ux8272}
  
  \(20\) 个点，\(12\) 个面，\(30\) 条棱，面为五边形。
  
  循环节：即对于一种置换方案的轨道长度。简单理解为转多少次能够转到原来的位置。
  
  \begin{longtable}[]{@{}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.1471}}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.1029}}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.0882}}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.0882}}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.1765}}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.2206}}
    >{\raggedright\arraybackslash}p{(\linewidth - 12\tabcolsep) * \real{0.1765}}@{}}
  \toprule\noalign{}
  \begin{minipage}[b]{\linewidth}\raggedright
  旋转轴类型
  \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
  角度
  \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
  循环节
  \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
  数量
  \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
  面染色置换群
  \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
  边染色置换群
  \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright
  点染色置换群
  \end{minipage} \\
  \midrule\noalign{}
  \endhead
  \bottomrule\noalign{}
  \endlastfoot
  不转 & \(0^o\) & 1 & 1 & \((1)^{12}\) & \((1)^{30}\) & \((1)^{20}\) \\
  面面轴 & \(72^o\) & 5 & 6 & \((1)^2(5)^2\) & \((5)^6\) & \((5)^4\) \\
  面面轴 & \(144^o\) & 5 & 6 & \((1)^2(5)^2\) & \((5)^6\) & \((5)^4\) \\
  面面轴 & \(216^o\) & 5 & 6 & \((1)^2(5)^2\) & \((5)^6\) & \((5)^4\) \\
  点点轴 & \(120^o\) & 3 & 10 & \((3)^4\) & \((3)^{10}\) &
  \((1)^2(3)^6\) \\
  点点轴 & \(240^o\) & 3 & 10 & \((3)^4\) & \((3)^{10}\) &
  \((1)^2(3)^6\) \\
  棱棱轴 & \(180^o\) & 2 & 15 & \((2)^6\) & \((1)^2(2)^{14}\) &
  \((2)^{10}\) \\
  \end{longtable}
  
  以某个对象为旋转轴，其置换群中必然有两个长度为 \(1\)
  的轨道，作为旋转轴的对象，旋转前后应该是重叠的。
  然后剩下的根据轨道循环节直接算出即可。 可以发现这是一个无脑的工作
  
  \paragraph{足球的置换群}\label{ux8db3ux7403ux7684ux7f6eux6362ux7fa4}
  
  实在不想写了…… 足球的点数不好求，但是可以根据立体图形外角和公式求出：
  立体图形外角和为 \(720^o\) 。 即
  \(\text{点数} \times \text{外角度} = 720^o\).
  
  \section{例题：}\label{ux4f8bux9898}
  
  待填。
  
  \section{题外话}\label{ux9898ux5916ux8bdd}
  
  {}
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../longtable.sty)
  (.../booktabs.sty)
  (.../array.sty)
  (.../calc.sty)
  (.../footnotehyper.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 106.
  
  [1] [2]
  
  Package longtable Warning: Column widths have changed
  (longtable)                in table 1 on input line 283.
  
  [3]
  
  Package longtable Warning: Table widths have changed. Rerun LaTeX.
  
  [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  Package longtable Warning: Table widths have changed. Rerun LaTeX.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../longtable.sty)
  (.../booktabs.sty)
  (.../array.sty)
  (.../calc.sty)
  (.../footnotehyper.sty)
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 106.
  
  [1] [2] [3] [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.