前些日子室友说了一道15年秋招的笔试题,题目如下:
用三种颜色给立方体的六个面着色,颜色可以使用一种或多种,旋转后可以相同的涂色记为一种涂色方式,问一共有多少种涂色方式?
当时一心想直接罗列出来,但是涂色的种类比较的多,而且立方体的旋转也有很多种,有按照面中心点连线,棱中心连线,顶点连线三种方式。人为的去列举很容易出现错误。下面讲一下使用Polya计数定理来进行计算,有关Polya定理的说明可以在网上查询或者从以下地址简单查看http://cs.tju.edu.cn/faculty/zhangkl/teaching/comb/lec12.pdf.
这里假设读者对Polya与Burnside引理都有了解,仅仅列举出对应的做题步骤与具体过程。
① 获取置换群
② 写出对应的多项式公式
③ 计算结果
获取/找出置换群
按照立方体的旋转方式,大概分为以下几种(记立方体顶点为1-6):
-
不旋转
(1,2,3,4,5,6)
1组
-
沿面中心线旋转90°或者270°
(1,2,3,4)(5) (6)
6组
-
沿面中心线旋转180°
(1,3)(2,4)(5)(6)
3组
-
沿棱中心线旋转180°
(1,2)(3,4)(5,6)
6组
-
沿对角顶点连线旋转120°或者240°
(1,2,3)(4,5,6)
8组
写出对应的多项式公式
sum = (w1^6 + 6 * w1^2 * W4^1 + 3 * w1^2 * w2^2 + 6 * w2^3 + 8 * w3^2) / 24
计算结果
将所有的w替换为3即可得出3中颜色的涂色种类,即
sum=(3^6+6*3^2*3+3*3^2*3^2+6*3^3+8*3^2)/24 = 57
如有任何知识产权、版权问题或理论错误,还请指正。
转载请注明原作者及以上信息。