How many unique ways can two black stones and one white stone be placed on a 5x5 grid, disregarding reflectional and rotational symmetry?

61 Views Asked by At

This problem has been bothering me for quite a while, but I don't think I have the combinatorics background to answer it.

Considering each grid position as distinct, the overall number of possible positions is just $\binom{25}{2}\cdot 23$. Dividing by $4$ gives the number of positions possible excluding rotational symmetries as $1725$. But I'm at a bit of a loss for how to take reflections into account, particularly because the grid has odd side lengths. So if the three pieces are all along one of the axes of reflection, they will lose a unique reflection. For the grid below, the reflection about the third row and a $180^\circ$ rotation move the stones to the same coordinates, so they aren't unique transformations.

$$\begin{array}{|c|c|c|c|c|} \hline \;\;&\;\;&\;\;&\;\;&\;\;\\ \hline & & \bullet& & \\ \hline & & \bullet & & \\ \hline & & \circ & & \\ \hline & & & & \\ \hline \end{array}$$

But there are grids for which all rotations and reflections are distinct. For example, take this grid, for which all 4 rotations (including no rotation) and all 4 reflections are distinct:

$$\begin{array}{|c|c|c|c|c|} \hline \;\;&\;\;&\;\;&\;\;&\;\;\\ \hline & \bullet & & & \\ \hline & & \bullet & & \\ \hline & & \circ & & \\ \hline & & & & \\ \hline \end{array}$$

Is there a general strategy to solve this kind of problem? And if so, could the same question be generalized to boards with side length $n$?

If anyone is interested, this is related to a proposal to mitigate first-player advantage in the modern abstract strategy game Tak.

1

There are 1 best solutions below

3
On BEST ANSWER

The name of the lemma used to solve this problem is called Burnside's lemma, and it is usefull whenever the group is not too large and we can count the number of fixed colorings under each group element.

The group in question is the dyhedric group $D_{2\times4}$, it has $8$ elements. We have to look at how these actions work and try to count the number of fixed coloring under them.

Note that for each element of the group the tiles will be split up into orbits, and in order for a coloring to be fixed we must have that each orbit is monocromatic.

First notice the identity fixes all $\binom{25}{3}\times 3$ colorings

Now we consider the rotations by $90$ or $270$ degrees. It is impossible to make all the orbits monocromatic because they all have size $4$ except for one of them which has size $1$.

We now consider the rotation by $180$ degrees. In this case we have one orbit of $1$ element, and $12$ orbits with $2$ elements, the only colorings that work is when the white stone is in the middle and the two black ones are in one of the orbits, so there are $12$ fixed colorings.

Next we consider the reflections. In this case they are all the same, splitting the board into $5$ orbits of size $1$ and $10$ orbits of size $2$. It is clear that the white stone must go into one of the orbits of size $1$ and that the black ones must fill one of the other orbits, so there are $50$ permutations. But wait ! It is also possible for the two black ones to be in orbits of size $1$, so this gives an extra $\binom{5}{3}\times 3=30$ possibilities.

We can now plug this into the formula:

$\text{answer} = \frac{1\times\binom{25}{3}3 + 2\times 0 + 1\times12 + 4\times 80}{8}=1009$


Notice that this strategy generalizes straightforwardly to any board of odd size at least $3$.

We get: $\text{answer} = \frac{1\times\binom{n^2}{3}3 + 2\times 0 + 1\times(n^2-1)/2 + 4\times (n(n^2-n)/2 + \binom{n}{3}\times 3)}{8}$