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
|