Number of ways of arranging stained glass panes on a $2\times 4$ grid(upto rotations and flips).

combinationscombinatoricspermutations

Suppose you have eight 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 × 4$ grid.

How many different ways can you do this, taking symmetry into account? (Note that any pattern may be rotated 180 degrees, flipped vertically, or flipped horizontally. You should count all the possible resulting patterns as the same window)

I computed $\frac{8!}{8}$ since for each window, there are $2$ windows that are identical when rotating one of the windows by $180$ degrees, $2$ windows identical when flipping one of the windows vertical, and $2$ windows identical when flipping horizontally. Thus, $8$ identical windows for each $8!$ number of initial windows. Is there anything wrong with this solution?

Best Answer

You can view an arrangement as an element of a set $S$. The total number of elements in $S$ is $8!$ (without any restrictions). Consider any element, for example; $$ \begin{bmatrix} 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8 \end{bmatrix} $$ (each number corresponds to a color). Now, we can get $3$ additional elements of $S$ just by a $180^\circ$ rotation, a vertical flip or a horizontal flip, giving you $$ \begin{bmatrix} 8 & 7 & 6 & 5\\ 4 & 3 & 2 & 1 \end{bmatrix}, \begin{bmatrix} 4 & 3 & 2 & 1\\ 8 & 7 & 6 & 5 \end{bmatrix}, \begin{bmatrix} 5 & 6 & 7 & 8\\ 1 & 2 & 3 & 4 \end{bmatrix} $$

Notice that applying these operations to any one of $4$ elements results in an element from one of these only. Hence, you can partition $S$ into such independent groups of $4$. Therefore the total number of arrangements identical upto rotations and flips is $\dfrac{8!}{4}$.

Problem in your solution:

You can now see why the solution $\dfrac{8!}{8}$ is not correct. When you first divide by $2$, let's say to remove $180^\circ$ rotations, half of the elements are rightly removed. The next time you divide by $2$, the horizontal flips are removed. To remove the vertical flips, you've divided by $2$ once more, but notice that a $180^\circ$ rotation followed by horizontal flip is essentially a vertical flip, so by just dividing by $4$ you've removed even the vertically flipped versions of every element in the process, hence dividing by $2$ once more leads to a miscount.

Related Question