Friday, February 28, 2014

use 3 color to paint a cube (都要用上)求多少种涂法儿)

Suppose you have three colors in which to paint the face of a cube, 
either red, blue, or yellow. How many different color patterns are 
there if each face of the cube must be painted red, blue, or yellow 
(assuming that two patterns are the same if the two cubes painted 
with them can be made to look the same by simply rotating one or the 
other. E.g. there is only one pattern of say, five red faces and one 
yellow).
 
分情况呗。    首先, 至少要先上r,b,y 3个颜色。
那么还剩3种颜色要取:   
1) 全r, 全b, 全y
2) 两个相同,一个不同   6 种情况  (3*2)  先选2 个(r) 。再选另一个 (b)
3)  再一次 r,b,y 
solution  =  3 * ( 3个r )  +  6 * ( 2个 ,1个b) + (r,g,b)

然后看其permutation , 首先,先固定一个面。
3个r的情况 = 先固定 b,再找 y,  再4个r = 1(把b放在bottom)*2(b在上面或者某个侧面) *1 (全填即可)=2
 
r,b,y +  2个r,+ b = 1 (先固定y) *【1 b 一上一侧) + 1(bb在侧面相邻) + 1( bb不相邻)】* 1(全填r)= 3
 
再一次 r,b,y = step 1 * 先固定一个r在最底下 = 1 
               step 2:  固定另一个r   
                       case 1: 在上面  1种。  其余4个面,有2种涂法
                       case 2; 在侧边, 1种  ,其余4个面, step 1 : 先选一个在上边, 2种选择,例如选择b
                                                         step 2:  确定第二个r的位置。2种选择。
                                                         step 3; fill 2 y 
solution = 3*2 + 6 * 3 + 1*{ 2 + 2*2  }= 30 种?????????


这里有个链接 , 或许可以看


This is a problem requiring the use of Burnside's lemma. You consider 
the 24 symmetries of a cube and sum all those symmetries that keep 
colours fixed. The number of non-equivalent configurations is then the 
total sum divided by the order of the group (24 in this case).

We first find the cycle index of the group of FACE permutations 
induced by the rotational symmetries of the cube.

Looking down on the cube, label the top face 1, the bottom face 2 and 
the side faces 3, 4, 5, 6 (clockwise).

You should hold a cube and follow the way the cycle index is 
calculated as described below. The notation (1)(23)(456) = 
(x1)(x2)(x3) means that we have a permutation of 3 disjoint cycles 
in which face 1 remains fixed, face 2 moves to face 3 and 3 moves to 
face 2, face 4 moves to 5, 5 moves to 6, and 6 moves to 4. (This is 
not a possible permutation for our cube, it is just to illustrate the 
notation.) We now calculate the cycle index.

(1) e = (1)(2)(3)(4)(5)(6);  index = (x1)^6
(2) 3 permutations like (1)(2)(35)(46); index 3(x1)^2.(x2)^2
(3) 3 permutations like (1)(2)(3456); index 3(x1)^2.(x4)
(4) 3 further as above but counterclockwise; index 3(x1)^2.(x4) 
(5) 6 permutations like (15)(23)(46); index 6(x2)^3
(6) 4 permutations like (154)(236); net index 4(x3)^2
(7) 4 further as above but counterclockwise; net index 4(x3)^2

Then the cycle index is

P[x1,x2,...x6] =(1/24)[x1^6 + 3x1^2.x2^2 + 6x2^3 + 6x1^2.x4 + 8x3^2]

and the pattern inventory for these configurations is given by the 
generating function:  

(I shall use r = red, b = blue, y = yellow as the three colours.)

f(r,b,y) = (1/24)[(r+b+y)^6 + 3(r+b+y)^2.(r^2+b^2+y^2)^2 
           + 6(r^2+b^2+y^2)^3 + 6(r+b+y)^2.(r^4+b^4+y^4) 
           + 8(r^3+b^3+y^3)^2]

and putting r = 1, b = 1, y = 1 this gives

  = (1/24)[3^6 + 3(3^2)(3^2) + 6(3^3) + 6(3^2)(3) + 8(3^2)]

  = (1/24)[729 + 243 + 162 + 162 + 72]

  = 1368/24

  = 57   

So there are 57 non-equivalent configurations.

No comments:

Post a Comment