polya定理
这是组合数学中著名的定理。用于解决“本质不同的染色方案”计数问题。 问题 现在需要给 2 × 2 2 × 2 的棋盘黑白染色。求本质不同的染色方案数。 如果某染色方案经过 顺时针旋转 后与别的染色方案相同，则称它们本质相同。 暴力 我们先暴力列出每种染色方案： 发现本质不同的染色方案数有 6 6 种： C1,C2,C6,C10,C12,C16 。 burnside引理 burnside引理是polya定理的基础。 为了讨论方便，先给格子编号。 首先考虑“旋转”的本质——置换。旋转给出了一些置换方式，例如顺时针旋转 90 ∘ 90 ∘ ，用置换的语言说就是“原来的位置是 1 的现在摆在 2 ，原来位置是 2 的现在摆在 3 ……”，表示为 { 2 , 3 , 4 , 1 } { 2 , 3 , 4 , 1 } 。类似地，我们搞出所有的置换： f 0 ∘ = { 1 , 2 , 3 , 4 } f 0 ∘ = { 1 , 2 , 3 , 4 } f 90 ∘ = { 2 , 3 , 4 , 1 } f 90 ∘ = { 2 , 3 , 4 , 1 } f 180 ∘ = { 3 , 4 , 1 , 2 } f 180 ∘ = { 3 , 4 , 1 , 2 } f 270 ∘ = { 4 , 1 , 2 , 3 } f 270 ∘ = { 4 , 1 , 2 , 3 } 接下来就是 burnside引理 了： 对于每个置换 f f ，我们定义 C ( f ) C ( f ) 为 在置换 f f 下保持不变的方案数 。 则有： 本质不同的方案数为 C ( f ) C ( f ) 的 平均数 。 即： ans = 1 | G | ∑ f ∈ G C ( f ) ans = 1 | G | ∑ f ∈ G C ( f ) 用上面的例子来验证一下： 置换 f f 保持不变的方案 C ( f ) C ( f ) 0 ∘ 0 ∘ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 16 90 ∘ 90 ∘ 1,16 2 180 ∘ 180 ∘ 1,10,11,16 4 270 ∘ 270 ∘ 1,16 2 则 C ( ...