Pólya enumeration theorem
着色
集合 (X) 有置换群 (G)。(mathcal{C}) 是 (X) 的着色集合；(G) 作用在 (mathcal{C}) 上。
则 (forall fin G, extbf{c}inmathcal{C}) 有
[f* extbf{c}inmathcal{C}
]
[exists fin Gquad s.t.quad f* extbf{c}= extbf{c}
]
稳定核
着色 ( extbf{c}) 的稳定核：
[G( extbf{c})={fin G;|;f* extbf{c}= extbf{c}}
]
着色的稳定核是置换群。
并且 (forall f,gin G) 有：当且仅当
[(f^{-1}circ g)in G( extbf{c})
]
时
[f* extbf{c}=g* extbf{c}
]
导出一个推论，
[|{f* extbf{c};|;fin G}|=frac{|G|}{|G( extbf{c})|}
]
等式左边：与 ( extbf{c}) 等价的着色数。
Burnside
在 (f) 的作用下，(mathcal{C}) 中所有保持不变的着色的集合
[mathcal{C}(f)={ extbf{c};|;f* extbf{c}= extbf{c}}
]
发现有
[sumlimits_{fin G}|mathcal{C}(f)|=sumlimits_{ extbf{c}inmathcal{C}}|G( extbf{c})|=N(G,mathcal{C}) imes|G|
]
于是，(mathcal{C}) 中非等价着色数
[N(G,mathcal{C})=frac{1}{|G|}sumlimits_{fin G}mathcal{C}(f)
]
即 Burnside引理。
Pólya
循环：首先任意置换都可以分解为多个循环
比如说一个置换是
((1,2,3,4,5)
ightarrow(1,3,4,5,2))
就有 ((1)) 和 ((2,3,4,5)) 这两个循环节
记置换 (f) 的循环分解中，循环的个数为 (#(f))
并且着色所用颜色数为 (k) 那么
[|mathcal{C}(f)|=k^{#(f)}
]
Generating Function
设 (k) 种颜色的集合 ({u_1,u_2,cdots,u_k})
那么，针对各颜色的数目的 (mathcal{C}) 的非等价着色数的生成函数
[P(sumlimits_{i=1}^k u_i;,;sumlimits_{i=1}^k u_i^2;,;cdots;,;sumlimits_{i=1}^k u_i^n)
]
其中 (u_1^{p_1}u_2^{p_2}cdots u_k^{p_k}) 的系数就是每个颜色 (u_i) 各用 (p_i) 次的非等价着色数。
References
( extrm{[1]}quad extrm{Brualdi, Richard A.}quad extit{"Introductory}; extit{ Combinatorics."})