Applying Burnside's Lemma to a Permutational Problem.

Question

Let us imagine a $5 \times 5$ board with a hole in the center, totalling $24$ pieces. Each piece must be a zero, a one or a two. But, on the board, there can only be between $0$ and $6$ ones, and between $0$ and $6$ twos.

Speaking generally, this would consist of $$ \sum_{n=0}^{6} \sum_{k=0}^6 \binom{24}{n}\binom{24-n}{k} \approx 6 \text{ billion board states.} $$

My question is, how many possible board states exist if we consider symmetries of the game board to be equivalent, e.g. $$ \boxed{\begin{matrix} 0 & 1 & 2 & 0 & 0 \,\\ 0 & 1 & 1 & 2 & 0 \,\\ 2 & 0 & \times & 0 & 0 \,\\ 0 & 0 & 0 & 0 & 0 \,\\ 0 & 2 & 2 & 1 & 0 \, \end{matrix}} \quad = \quad \boxed{\begin{matrix} 0 & 0 & 2 & 1 & 0 \,\\ 0 & 2 & 1 & 1 & 0 \,\\ 0 & 0 & \times & 0 & 2 \,\\ 0 & 0 & 0 & 0 & 0 \,\\ 0 & 1 & 2 & 2 & 0 \, \end{matrix}} $$

The same going for all rotational symmetries, etc. I assume this requires Burnside's Lemma but I don't know how it would be implemented in this form.

Thank you.

Answer 1

The first step is to figure out what your group of symmetries is. Since you seem to be allowing reflections and rotations, this is $D_4$ (or $D_8$ depending on your notation, the group has 8 elements, 4 rotations, and 4 reflections). Then, for each group element, you need to figure out how many boards are preserved by the element.

For example, consider a reflection about one of the diagonals. There are a few different cases that we need to consider based on how many 1s and 2s there are along the diagonal, and how many there are above the diagonal (because the number above the diagonal will equal the number below the diagonal).

There are 10 spaces above the diagonal, and 4 spaces on the diagonal. If we have i 1s above the diagonal, j 2s above the diagonal, k 1s on the on the diagonal, and $\ell$ 2s on the diagonal, then we must have $2i+k\leq 6$, $2j+\ell\leq 6$, and so the number of combinations is

$$\sum_{i=0}^{3}\sum_{j=0}^3 \sum_{k=0}^{6-2i} \sum_{\ell=0}^{6-2j} \binom{10}{i}\binom{10-i}{j}\binom{4}{k}\binom{4-k}{\ell}.$$

The calculation is the same for all 4 reflections. For rotations, you'll have 3 calculations: one for rotation by $0$ degrees (and EVERY board is invariant under this), one for rotations by 90 degrees in one direction or the other (you can take 6 of your squares, say in the top left, and you can place at most 1 1 and 1 2 in those squares, as each 1 in those 6 squares will give 4 1s on the board), and one for rotation by 180 degrees (you can take 12 squares, and have up to 3 1s and 3 2s in those squares).

The rotations are all straight forward, and the reflections, while a bit trickier, will all yield the same calculation, and plugging them into Burnside's lemma will yield your result.

Answer 2

We first label the 24 pieces, then view the rotations and reflections of the board as the group action : $D_4$ acts on the set $\{1,2,\cdots,24\}$, by sending each piece to the piece it goes after the respective operations. Then each element of $D_4$ can be viewed as an element in $S_{24}$.

Now, for a certain permutation, say $\sigma$, can be decomposed into disjoint cycles, by the Burnside's lemma, what we need is the number of states that are fixed by $\sigma$. Suppose there are k disjoint cycles in the decomposition of $\sigma$ ( including the 1-cycles), one state is fixed by $\sigma$ iff the pieces in the same cycle have the same value. For instance, $$ (1,2,3,4)(6,7,8)\cdots$$ the pieces labelled by 1,2,3,4 must have the same value, and the pieces labelled by 6,7,8 must have the same value. Then, we can calculate how many states are fixed by this permutation as the caculation for the total number of the states, but be careful about the length of each cycle, sinse there is a limited condition on the number of 1s and 2s.