多边形染色答案

constant

1）用三种颜色染一个正三角形，有多少种染法？
2）用四种颜色染一个正方形，有多少种染法？
3）一般的，用k种颜色染一个正n边形，有多少种染法？

答案www.ddhw.com

一个正n边形，共有n-1种旋转和n种翻转。所以应该把所有的染法都找出来，再除2n。但有的染法在旋转和翻转以后并不能产生2n个变种，例如用一种颜色染成的多边形，不管怎么转，都只有一种。对这样的染法，就要多数几遍。一般来说是这样：

用k种颜色染正n边形，不考虑旋转和翻转，共有n^k种染法。对这2n-1种变换，有一些染法变换之后不变，还是同一种染法，例如对称的和周期性的。把这些不变染法的总和加到n^k上，然后再除2n。

这个方法叫做Burnside引理，是Polya计数定理的一种简单形式。应用到我们的问题上，当n=2j+1时，每个翻转有(j+1)^k种不变染法，当n=2j时，一半的翻转有(j+1)^k种不变染法，一半有j^k种。而旋转的不变染法有GCD(n,i)^k种，其中i为旋转的边数。所以总染法为

n=2j+1时, n^k + n*(j+1)^k + sum(i=1 to n-1, GCD(n,i)^k),
n=2j 时，n^k + j*((j+1)^k+j^k) + sum(i=1 to n-1, GCD(n,i)^k)。

对前两问，可以算出答案为10和55。

www.ddhw.com

 

huxlnn