找回密码
 立即注册
搜索
总共850条微博

动态微博

查看: 797|回复: 1
打印 上一主题 下一主题
收起左侧

多边形染色答案

[复制链接]

158

主题

544

帖子

9110

积分

跳转到指定楼层
楼主
发表于 2006-3-23 22:40:17 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

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

 
回复

使用道具 举报

6

主题

412

帖子

2694

积分

沙发
发表于 2006-3-24 03:25:12 | 只看该作者

[:-Q][:-Q][>:D<]


  




回复 支持 反对

使用道具 举报

24小时热帖
    一周热门
      原创摄影
        美食美文
          您需要登录后才可以回帖 登录 | 立即注册

          本版积分规则

          Archiver|手机版|珍珠湾ART

          Powered by Discuz! X3 © 2001-2013 All Rights Reserved