polya定理

这是组合数学中著名的定理。用于解决“本质不同的染色方案”计数问题。

问题

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

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

暴力

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

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

burnside引理

burnside引理是polya定理的基础。

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

首先考虑“旋转”的本质——置换。旋转给出了一些置换方式,例如顺时针旋转$90^\circ$,用置换的语言说就是“原来的位置是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)$平均数
即:$\displaystyle \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$表示有多少种颜色。则有:

$\displaystyle 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$

从上面的例子中我们发现,$k^{m(f)}$确实等于$C(f)$。现在我们的任务只是求出$m(f)$了。它显然可以$O(n)$求出:

int flag[10]={0},i,j,m=0;

for(i=1;i<=4;i++)
    if(flag[i]==0) 
    {
        j=i;
        while(flag[j]==0)
            flag[j]=1,j=f[j];
        m++;
    }

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

是不是很简单?


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close