I need to find all the different colorings of the 5x5 square in $n$ colors in a symmetry group using Burnside's lemma. I get that if $c$ is the number of colorings $c=1/|G|*\sum|St(g)|$ And $St(g)$ is $n^t$ where $t$ is the number of cycles that g creates. Am I right that $|G|=8$? How do I calculate the number of cycles?


I'm not $100\%$ sure precisely what this question is asking regarding the stated problem so I'll just go through the problem itself.

Firstly, how you answer the question depends on what symmetries you want the $5\times 5$ square to have. If just rotations then $|G_1|= 4$, if rotations and reflections then $|G_2|=8$. The groups act on the $25$ cells of the square so it is appropriate to label cells in some way. I'll use the following labels but it doesn't really matter how you do it as long as cells are distinct.

$$\begin{array}{|c|c|c|c|c|}\hline 1&2&3&4&5\\\hline 6&7&8&9&10\\\hline 11&12&13&14&15\\\hline 16&17&18&19&20\\\hline 21&22&23&24&25\\\hline\end{array}$$

Then, for example, a counterclockwise rotation of $90^{\circ}$ would be represented in cycle notation


meaning: "cell $1$ is replaced by cell $5$, cell $5$ by cell $25$, cell $25$ by cell $21$ and so forth". If we use $z_k$ to represent a cycle of length $k$ then this example permutation is of the form $z_4^6z_1^1$.

Notice that this is also the form of a $90^\circ$ clockwise rotation. The list of permutation types for rotations and reflections is as follows:

$$\begin{array}{|c|c|c|}\hline \textbf{type} & \textbf{description}&\textbf{permutations of this type}\\\hline z_1^{25} & \text{identity} & 1\\\hline z_1^{1}z_4^{6} & \text{$90^\circ$ cw/ccw rotations} & 2\\\hline z_1^1z_2^{12} & \text{$180^\circ$ rotation} & 1\\\hline z_1^5z_2^{10} & \text{diagonal reflections} & 2\\\hline z_1^5z_2^{10} & \text{horizontal/vertical reflections} & 2\\\hline\end{array}$$

If you are just using rotations then your cycle index is:

$$P_{G_1}=\frac{1}{4}\left(z_1^{25}+2z_1^1z_4^6+z_1^1z_2^{12}\right)\, .\tag{1}$$

If you include reflections then the cycle index is:

$$P_{G_2}=\frac{1}{8}\left(z_1^{25}+2z_1^1z_4^6+z_1^1z_2^{12}+4z_1^5z_2^{10}\right)\, .\tag{2}$$

In each permutation, cells in a given cycle must be coloured the same so that colourings are fixed under that permutation. Therefore if there are $n$ colours we can replace each $z_k$ with $n$ in $(1)$ and $(2)$. This gives the number of $n$ colourings of the $5\times 5$ square under each symmetry group $G_1$ and $G_2$:

$$P_{G_1}(n)=\frac{1}{4}\left(n^{25}+2n^7+n^{13}\right)\, ,\tag{1$^*$}$$ $$P_{G_2}(n)=\frac{1}{8}\left(n^{25}+2n^7+n^{13}+4n^{15}\right)\, .\tag{2$^*$}$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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