Fraleigh(7th) Ex17.9: A rectangular prism 2 ft long with 1-ft square ends is to have each of its six faces painted with one of six possible colors. How many distinguishable painted prisms are possible if each color may be used on any number of faces?
I solved it but the answer is different from mine. I think my answer is right, but I haven't seen any error in the solution. Here is the solution.
We use Burnside's formula: (number of orbits in $X$ under $G$)=$\frac 1 {|G|} \cdot \sum_{g \in G}|X_g|$. In this problem, the group $G$ of the prism has order $8$, four positions leaving the end faces in the same position and four positions with the end faces swapped. The set $X$ of possible ways of painting the prism has $6^6$ elements. We have
$|X\text{_id}|=6^6$,
$|X\text{_(same ends, rotate 90° or 270°)}|=6^3$,
$|X\text{_(same ends, rotate 180°)}|=6^4$,
$|X\text{_(swap ends, keeping top face on top)}|=6^4$,
$|X\text{_(swap ends, as above, rotate 90° or 270°)}|=6^2$,
$|X\text{_(swap ends, as above, rotate 180°)}|=6^3$: But I think this should be $6^4$. If you swap ends(keeping top face on top) and then rotate $180°$, the left and right faces are fixed and top-bottom, front-back is interchanged. So there are $6^4$ fixed elements as same to swapping ends keeping top face on top case. Who is right?
And is there a proof by elementary(or combinatoric??) method without using group-theory? I haven't studied combinatorics in college so I don't know how this problem will be solved by combinatorics. Does it also use group-theory and Burnside's formula, etc.?
Best Answer
We can almost factor the problem into the separate problems of determining the number $n_s$ of colourings on the square faces distinguishable under swapping and the number $n_r$ of colourings on the rectangular faces distinguishable under rotations about the prism axis. The only interaction between these two subproblems arises because if the square faces have the same colour, the colourings of the rectangular faces will behave differently depending on whether they are chiral, i.e. distinguishable from their mirror image. The product $n_sn_r$ counts a chiral colouring of the rectangles and its mirror image twice, even though they can be transformed into each other by swapping the square faces if those have the same colour, so we have to count the chiral and achiral colourings of the rectangles separately and compensate for the double-counting.
For $(4)$ identical colours on the rectangles, there is $1$ achiral pattern with $6$ colour choices.
For $(3,1)$ identical colours on the rectangles, there is $1$ achiral pattern with $6\cdot5$ colour choices.
For $(2,2)$ identical colours on the rectangles, there are $2$ achiral patterns with $\binom62$ colour choices each.
For $(2,1,1)$ identical colours on the rectangles, there is $1$ achiral pattern with $6\binom52$ colour choices and $1$ chiral pattern with $6\cdot5\cdot4$ colour choices.
For $(1,1,1,1)$ identical colours on the rectangles, there is $1$ chiral pattern with $6\cdot5\cdot4\cdot3/4$ colour choices.
Each of the achiral colourings of the rectangles can be combined with $\binom62+6$ colourings of the square faces, whereas for the chiral colourings of the rectangles the $6$ colourings of the square faces with identical colours are double-counted, so to compensate we should count only $\binom62+3$ colourings of the square faces per chiral colouring of the rectangles.
Putting it all together, we have $6+6\cdot5+2\binom62+6\binom52=126$ achiral colourings of the rectangles with $\binom62+6=21$ colourings of the square faces and $6\cdot5\cdot4+6\cdot5\cdot4\cdot3/4=210$ chiral colourings of the rectangles with $\binom62+3=18$ colourings of the square faces, for a total of $126\cdot21+210\cdot18=6426$ distinguishable colourings of the prism.
Now comes the weird part. The answer given in the book leads to $6246$, with just two digits swapped. But if you correct the error you spotted, you only get $6381$. The reason is yet another error -- the number for "swap ends, as above, rotate $90°$ or $270°$" that Gerry corrected from $6^4$ to $6^2$ should in fact be $6^3$, since this operation swaps two pairs of adjacent rectangles into each other. That makes the total come out right to $6426$.
P.S.: Oddly enough, your typo made the number in your original post come out right, since the overall result of the three errors was just that the numbers in the last two lines were swapped :-). What's also odd is that the "Instructor's Solutions Manual" for the 7th edition that I found online contains the incorrect solution you quote, whereas the Spanish edition that you can also find online, which seems to be from 1988 and thus older than the 7th English edition, doesn't give a detailed solution, but gives the correct number $6426$ in the solutions section.