Polya定理

Polya定理是组合数学中著名的定理。用于解决“本质不同的染色方案”计数问题,在OI中有一定范围的应用。

以下引用来自神犇阮行止的博文,此处转载仅处于某种莫名的强迫症与阮爷的CC协议。

问题

现在需要给2×2的棋盘黑白染色。求本质不同的染色方案数。

如果某染色方案经过顺时针旋转后与别的染色方案相同,则称它们本质相同。

暴力

我们先暴力列出每种染色方案:

发现本质不同的染色方案数有6种:\( C1,C2,C6,C10,C12,C16 \)。

burnside引理

burnside引理是polya定理的基础。

为了讨论方便,先给格子编号。

首先考虑“旋转”的本质——置换。旋转给出了一些置换方式,例如顺时针旋转90∘,用置换的语言说就是“原来的位置是1的现在摆在2,原来位置是2的现在摆在3……”,表示为{2,3,4,1}。类似地,我们枚举每一种置换:

\( f_{0^\circ} = \{1,2,3,4\} \)
\( f_{90^\circ} = \{2,3,4,1\} \)
\( f_{180^\circ} = \{3,4,1,2\} \)
\( f_{270^\circ} = \{4,1,2,3\} \)

接下来就是burnside引理了:

对于每个置换f,我们定义\( C(f) \)为在置换 f 下保持不变的方案数。
则有: 本质不同的方案数为\( C(f) \)的平均数。
即:\(  \text{ans} = \frac{1}{|G|} \sum_{f \in G} C(f) \)

用上面的例子来验证一下:

置换f 保持不变的方案 C(f)
\( {0^\circ} \) 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 16
\( {90^\circ} \) 1,16 2
\( {180^\circ} \) 1,10,11,16 4
\( {270^\circ} \) 1,16 2

则\( C(f) \)的平均数为:\( \frac{16+2+4+2}{4} = 6 \),发现确实是答案。

polya定理

上面的burnside引理很好用,然而它需要枚举每个方案,复杂度十分不好。

所以polya定理出来拯救世界了。它提供了一种快速计算\( C(f) \)的方法:

考虑置换f,我们一定能把它表示成循环的形式。例如上面的转\( 180^\circ \)可以表示为:\( \{3,4,1,2\} = (1,3)(2,4) \)。

令\( m(f) \)表示置换f的循环节个数,k表示有多少种颜色。则有:

\[  C(f) = k^{m(f)} \]

我们还是使用之前的例子来验证。

角度 置换 m(f)
\( {0^\circ} \) \( \{1,2,3,4\} = (1)(2)(3)(4) \) 4
\( {90^\circ} \) \( \{2,3,4,1\} = (1,2,3,4) \) 1
\( {180^\circ} \) \( \{3,4,1,2\} = (1,3)(2,4) \) 2
\( {270^\circ} \) \( \{4,1,2,3\} = (1,2,3,4) \) 1

从上面的例子中我们发现,\( C(f) \)。现在我们的任务只是求出\( m(f) \)了。它显然可以\( O(n) \)求出:

所以现在我们可以以\( O(np) \)的时间复杂度来求出整个问题的解。其中p表示置换数量。

是不是很简单?


以下是我对PolyaBurnside的简单理解:

我们要求本质不同的方案个数,

先找出每一种置换,置换指两种本质相同的方案的变换方案,不变也是一种置换,

对于每一种置换,求出对于这种置换来说本质相同的方案个数,

然后,对于刚刚计算出来下的每种置换下本质相同的方案个数求平均,

求出来的平均数就是想要的本质不同的方案个数。


这是一个坑,我以后有时间会举一些例子进行更加通俗的解释


以下附上BIKE大爷的冬令营讲稿,虽然对于初学者不太友好,但涵盖了大多数运用burnside的简单到复杂的情况:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注