Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.?

share|improve this question
    
One can do a careful enumeration, breaking things up into cases. The cases breakdown is connected to the group structure, but zero knowledge of group theory is needed. Set the box on end (small face down). Count first the number of colourings in which the top and bottom face have the same colour. That colour can be chosen in $6$ ways. Continue! It is not hard, but one needs to concentrate. –  André Nicolas Jul 21 '11 at 2:56
    
Swap ends, rotate $\pi/2$, shouldn't that be $6^2$? For that to fix, both ends must be one color, and all four other faces must be one color, giving $6^2$. –  Gerry Myerson Jul 21 '11 at 3:24
1  
@Gerry: That operation swaps the four rectangular faces pairwise -- see my answer. –  joriki Jul 21 '11 at 13:26
1  
@André: That's a bit more work than is needed, since you'd then be counting all the colourings of the rectangles twice, whereas if you count the chiral and achiral ones separately and multiply them by the right factors, you only need to count them once (see my answer). –  joriki Jul 21 '11 at 13:53
1  
@joriki: I regretted suggesting two squares same colour count first, since different colours is less treacherous, choose two colours, set the box on table with colour you like less down. A mistake counting is now unlikely. For the squares same colour, a little slip is more likely. –  André Nicolas Jul 21 '11 at 14:07

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
That’s also what the 4th English edition does. –  Brian M. Scott Jul 21 '11 at 19:27
    
Thanks for your great answer. Using chirality and achirality makes the problem easier. But there seems to be a typo. I doubt that $\binom65$ in your answer need to be changed to $\binom62$. –  Gobi Jul 22 '11 at 2:21
    
@Gobi: You're quite right; thanks, fixed. –  joriki Jul 22 '11 at 2:28

Your $6^4$ is correct. However, $6^2$ for the third end-swapping case is wrong: it really is $6^3$, as you originally had it. If the rotation is $\pi/2$ clockwise, the ends swap, the top and right side swap, and the bottom and left side swap, so you get to choose three colors, not two.

Here’s an elementary enumeration along the lines suggested by André Nicolas. Set the prism on end. Suppose first that the top and bottom faces get the same color; we’ll count the number of distinguishable ways to color the four sides.

Using just one color: $6$ ways.

Using two colors, $3$ sides of one color and $1$ of the other: There are $6$ ways to choose the color for the single face and then $5$ ways to choose the other color, for a total of $30$ ways. (Running total: $36$)

Using two colors, $2$ sides of each color: There are ${6 \choose 2} = 15$ ways to choose the two colors. Once the colors are chosen, they can be applied in just $2$ distinguishable ways: either opposite sides are the same color, or they are different colors. The total number of ways is therefore again $30$. (Running total: $66$)

Using three colors: In this case one color must appear twice, the other two once each. There are $6$ ways to choose the color that appears twice, and there are then ${5 \choose 2} = 10$ ways to choose the other two colors. The two faces of the same color may be either adjacent or opposite. In either case it makes no difference how the remaining two colors are applied to the other two sides, since we can swap ends, so we get a total of $120$ ways in this case, $60$ from each subcase. (Running total: $186$)

Using four colors: There are ${6\choose 4} = 15$ ways to choose the colors. Arbitrarily choose one of the colors to paint one side. There are $3$ ways to color the opposite side, and since we can swap ends, it makes no difference which way we apply the remaining two colors to the other two sides. This case yields a total of $15\cdot 3 = 45$ ways, for a grand total of $231$.

For each of these $231$ colorings of the four sides, there are $6$ ways to color the top and bottom faces, for a total of $1386$ colorings in which the top and bottom faces get the same color.

The analysis when the top and bottom faces get different colors is fairly similar. This time, however, it’s easier to account for the coloring of the top and bottom faces as we go along, noting that there are ${6\choose 2} = 15$ pairs of colors for the top and bottom faces.

Using just one color for the four sides: no change, so $6$ ways to color the sides and $6\cdot 15 = 90$ colorings altogether. (Swapping ends doesn’t affect the sides.)

Using two colors: no change, so $60$ ways and $60\cdot 15 = 900$ colorings; swapping ends affects the sides, but they can be restored by a rotation. (Running total: $990$)

Using three colors: As before, there are $6$ ways to choose the color that appears twice and then $10$ ways to choose the other two colors, and the two faces of the same color may be either adjacent or opposite. If they are opposite, it makes no difference how the remaining two colors are applied to the other two sides, so that sub-case yields $60$ ways and $60\cdot 15 = 900$ colorings. If they are adjacent, however, the order in which the other two colors are applied to the other two sides does matter, and we get $120$ ways. Since these $120$ ways of coloring the sides are not preserved by swapping ends, each apparently extends to $30$ different ways of coloring the prism, for a total of $120\cdot 30 = 3600$ colorings. However, this actually counts each coloring twice. Say that the two singleton side colors are $a$ and $b$, and that the top and bottom colors are $c$ and $d$. The coloring in which $b$ immediately follows $a$ in clockwise order and $c$ is on top is the same as the coloring in which $a$ immediately follows $b$ and $d$ is on top. Each of these colorings is therefore counted twice in the $3600$, once with the side colors in the order $ab$ and once with them in the order $ba$. This subcase therefore produces only $1800$ colorings. (Running total: $3690$)

Using four colors: There are still $15$ ways to choose the colors. As before, arbitrarily choose one of the colors to paint one side. There are still $3$ ways to color the opposite side, but we can no longer swap ends, so the order in which we apply the remaining two colors to the other two sides now matters. This case yields a total of $15\cdot 6 = 90$ ways. A little thought shows that it’s like the second three-color subcase, so it gives rise to $90\cdot 15 = 1350$ colorings and a grand total of $5040$ colorings with distinct top and bottom colors.

Thus, there are altogether $1386+5040 = 6426$ distinguishable colorings of the prism. As a check, the Polya Enumeration Theorem yields the same result.

share|improve this answer

Perhaps we can solve this relatively quickly. As pointed out by Brian M. Scott the Polya Enumeration Theorem (PET) applies here. The cycle index of the face permutation group $G$ is easy to compute. We now list the contributions from the different automorphisms. There is the identity, which contributes $$a_1^6.$$ There are two rotations (90 degrees and 270 degrees) about the long central axis parallel to the long sides, which contribute $$2\times a_1^2 a_4.$$ The 180 degree rotation about said axis contributes $$a_1^2 a_2^2.$$

Two additional symmetries arise when we fix two opposite long edges and rotate by 180 degrees, giving $$2\times a_2^3.$$ Finally there are two 180 degree rotations about an axis passing through the centers of two opposite long faces, giving $$2\times a_1^2 a_2^2.$$

This gives the cycle index $$Z(G) = \frac{1}{8} \left(a_1^6 + 2 a_1^2 a_4 + 2 a_2^3 + 3 a_1^2 a_2^2\right).$$

Supposing that we have $N$ colors we want to evaluate $$Z(G)(C_1+C_2+\cdots+C_N)_{C_1=1, C_2=1, \ldots C_N=1}$$ which turns out to be $$\frac{1}{8} \left(N^6 + 2 N^3 + 2 N^3 + 3 N^4\right) = \frac{1}{8} \left(N^6 + 3 N^4 + 4 N^3\right).$$

This produces the sequence $$1, 18, 135, 640, 2250, 6426, 15778, 34560, 69255, 129250, 227601, 381888, 615160,\ldots$$ which indeed has for at most six different colors being used the value $$6426$$ as noted by the other posters.

There is another PET computation at this MSE link.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.