combinatoricsramsey-theory
Suppose you have six squares of stained glass, all of different colors, and you would like to make a rectangular stained glass window in the shape of a 2 × 3 grid.
How many different ways can you do this, taking symmetry into account? (Note that any pattern may be rotated 180°, flipped vertically, or flipped horizontally. You should count all the possible resulting patterns as the same window.)
I've tried 6! / 3 but this is not correct. Any tips?
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.
Consider a rectangular grid containing $m$ squares in each column and $n$ squares in each row. Label the rows of squares by the indices $1$, $2$, ..., $m$ and the rows of vertices by the indices $0$, $1$, ..., $m$ and do similarly for columns. Suppose that the vertices of the grid have been colored in such a way that every one of the $mn$ squares contains a vertex of each color.
Now suppose that a new row of squares is added to the grid. Can the previous coloring be extended to the last row of vertices (row $m+1$)? If so, in how many ways? The answer to the first question is that it can. This is so because we can color row $m+1$ the same way we colored row $m-1$. To answer the second question, notice that, once the color of any vertex in the row is decided, the colors of all the remaining vertices in the row are determined, assuming a coloring is possible at all. (Successively color neighbors of previously colored vertices until the whole row is colored. Each vertex that gets colored is the fourth member of a square in which three vertices have already been colored. Either the fourth color will be uniquely colored or two of the three colors already used will be the same, making the coloring untenable.) Since the first vertex can be colored in two ways, we conclude that row $m+1$ has at least one coloring and at most two colorings.
To determine whether the number of colorings is one or two, observe that if the coloring of row $m$ uses three or four colors, than at some point in the row we will have $$ m:\ \ldots abc\ldots, $$ where $a$, $b$, and $c$ are different colors. The colors in the corresponding positions in row $m+1$ are then forced, $$ \begin{aligned} m:&\ \ldots abc\ldots\\ m+1:&\ \ldots cda\ldots, \end{aligned} $$ where $d\notin\{a,b,c\}$. In fact, the colors in the corresponding positions in row $m-1$ are forced in the same way, and rows $m-1$ and $m+1$ are therefore colored identically. So in this case there is one coloring of row $m+1$. Also, the number of colors used in column $n$ will not be changed by the addition of row $m+1$.
If row $m$ uses only two colors, then two colorings are possible for row $m+1$, $$ \begin{aligned} m:&\ abababa\ldots & m:&\ abababa\ldots\\ m+1:&\ cdcdcdc\ldots & m+1:&\ dcdcdcd\ldots. \end{aligned} $$ The number of colors used in column $n$ may be changed by the addition of row $m+1$.
Observe that if a row uses only two colors, then all preceding and subsequent rows only use two colors; if a row uses three or more colors, then all preceding and subsequent rows use three or more colors. Clearly similar considerations apply to columns.
We are now in a position to write a system of recurrences for the number of colorings of an $m\times n$ grid. Define $$ \begin{aligned} Q_{m,n}&=\text{num. colorings with two colors in row $m$, two colors in column $n$,}\\ R_{m,n}&=\text{num. colorings with two colors in row $m$, three colors in column $n$,}\\ S_{m,n}&=\text{num. colorings with three colors in row $m$, two colors in column $n$,}\\ T_{m,n}&=\text{num. colorings with three colors in row $m$, three colors in column $n$.} \end{aligned} $$ Then $$ \begin{aligned} \begin{bmatrix}Q_{1,1} & R_{1,1}\\ S_{1,1} & T_{1,1}\end{bmatrix}&=24\cdot\begin{bmatrix}1 & 0\\ 0 & 0\end{bmatrix}\\ \begin{bmatrix}Q_{m,n} & R_{m,n}\\ S_{m,n} & T_{m,n}\end{bmatrix}&=\begin{bmatrix}Q_{m-1,n} & Q_{m-1,n}+2R_{m-1,n}\\ S_{m-1,n} & T_{m-1,n}\end{bmatrix}=\begin{bmatrix}Q_{m,n-1} & R_{m,n-1}\\ Q_{m,n-1}+2S_{m,n-1} & T_{m,n-1}\end{bmatrix} \end{aligned} $$ From this it is not hard to obtain the result you need.
For a conceptual explanation, observe that $T_{m,n}=0$ for all $m$, $n$. So either all rows use only two colors, or all columns use only two colors, or both. If all rows use only two colors then, since there are $4!=24$ colorings for the first square in row $1$, and since the coloring of the first two rows of vertices is determined by the choice of coloring for this square, there are $24\cdot2^{m+1-2}=24\cdot2^{m-1}$ colorings of the grid in this case. Similarly, the number of colorings in the case that all columns use only two colors is $24\cdot2^{n-1}$. Using inclusion-exclusion, the total number of colorings of the grid is $24\cdot\left(2^{m-1}+2^{n-1}-1\right)$ colorings.
Added summary: Let's formalize and flesh out a few details of the conceptual explanation above.
Proposition: If an $m\times n$ grid, $m,n\ge1$, has been four colored so that each of the four colors is used in every square then at least one of the following holds.
Proof: Observe that if a row or column uses only two colors, then the colors in that row or column alternate, $ababab\ldots$. Now perform induction on the number of squares in the grid. The base case is the case of one square, for which the statement clearly holds. For the induction step, at least one of $m$, $n$ is greater than $1$. Let's say $m$ is. Then, by the induction hypothesis, the statement holds for the four coloring of the $(m-1)\times n$ grid obtained by deleting the last row of vertices. Suppose that the rows of this smaller grid each use only two colors. If the colors in the last row of this smaller grid are $ababab\ldots$, then the colors in the deleted row can only be $cdcdcd\ldots$ or $dcdcdc\ldots$, where $c$ and $d$ are the two colors different from $a$ and $b$. If the rows of the smaller grid each use three or more colors, then the columns each use only two colors. Furthermore, the deleted row (row $m$) is colored the same as row $m-1$, and hence introduces no new color into any column. $\square$
Now if the rows each use only two colors, then let row $0$ be colored $ababab\ldots$ and let row $1$ be colored $cdcdcd\ldots$. There are $4!$ choices for the colors $a$, $b$, $c$, $d$. Then each of rows $2$, $4$, $6$, etc. must be colored either $ababab\ldots$ or $bababa\ldots$, and each of rows $3$, $5$, $7$, etc. must be colored either $cdcdcd\ldots$ or $dcdcdc\ldots$. Hence there are $24\cdot2^{m-1}$ colorings in this case. Similarly, in the case that the columns each use only two colors, there are $24\cdot2^{n-1}$ colorings. We over-count if we simply add the number of colorings in each of the two cases since there are $4!$ colorings in which both rows and columns each use only two colors. Hence the total number of colorings is $24\cdot(2^{m-1}+2^{n-1}-1)$. Specializing to the case where $m=n$, we get $24\cdot(2^m-1)$ colorings.
Best Answer
HINT: Representing the six colors by the numbers $1$ through $6$, we see that the following arrangements are equivalent:
$$\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}\qquad\begin{bmatrix}3&2&1\\6&5&4\end{bmatrix}\qquad\begin{bmatrix}4&5&6\\1&2&3\end{bmatrix}\qquad\begin{bmatrix}6&5&4\\3&2&1\end{bmatrix}$$
The first is the original; the second is flipped about the vertical axis; the third is flipped about the horizontal axis; and the last is rotated $180^\circ$ degrees (or flipped about each of the axes).
What should you divide by?