【数学】群论与Polya计数
本该写作Pólya，这里为了省事就记为Polya了。
模板是这样一道题：
给定一个 \(n\) 个点，\(n\) 条边的环，有 \(n\) 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 \(10^9+7\) 取模
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
群：集合\(G\)和\(G\)上的一个二元运算 · 构成一个群，当且仅当其满足：
-
封闭性：\(\forall f,g \in G,f·g \in G\)。
-
结合律：\(\forall f,g,h \in G,(f·g)·h = f·(g·h)\)。
-
单位元：\(\exists e\in G,\forall g\in G,g·e = e·g = g\)。
-
逆元：\(\forall f \in G,\exists g \in G,f·g = g·f = e\)。
例如，整数和加法就可以构成一个群。
我们定义一个置换形如：\(\begin{pmatrix}1 & 2 & 3 & .. & n\\p_1 & p_2 & p_3 & .. & p_n \end{pmatrix}\)
其中\(p\)是\(1\to n\)的一个排列。
置换群：元素都是置换的群。
（对于以下行为，读者先不用急着了解这些东西要干什么，先理解好，后面就推出来了。）
对于一个置换，如果我们将\(i\)向\(p_i\)，那么我们发现我们得到了一个由一堆环组成的一个图。我们称这个环为轨道。
对于一个染色方案\(c\)，我们称这个染色方案的稳定子为\(\{g|g \in G,g(c) = c\}\)，即一些对这个染色置换后这个染色不变的置换，例如
\(\begin{pmatrix}1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}\)
对于染色\((1,0,0)\)来说就是稳定子的一个元素。
轨道-稳定子定理：
\[|G^x| \times |G(x)| = |G| \]即一个染色轨道大小乘上稳定子个数等于置换群的大小。
Burnside引理：
\[|X / G| = \frac 1{|G|} \sum_{g \in G}|X^g| \]即轨道个数等于置换不动点的平均值，可以将”本质不同“问题转化为不动点问题。
不动点：对于一个置换\(g\)，染色\(c\)的个数使\(g(c) = c\)。
Polya引理：
\[|X / G| = \frac 1{|G|} \sum_{g \in G}color^{c(g)} \]其中\(c(g)\)是一个置换的环个数，将\(Burnside\)中的不动点转化到染色上。
标签：染色,置换,计数,群论,不动点,forall,pmatrix,Polya From： https://www.cnblogs.com/TheLastCandy/p/17599225.html