A 4 × 4 grid is filled in, with each of the 16 squares colored either black or white. Two colorings are regarded as identical if one can be converted to each other by performing any combination of flipping, rotating, or swapping the two colors (flipping all the black squares to white and vice versa). How many non-identical colorings are there?
I've figured out the number of invariances for each individual transformation but the combinations are a little confusing. Is there an easier way of solving this than just looking at each combination?
Best Answer
This is a case of Power Group Enumeration with the group permuting the slots being the eight symmetries $G_N$ of the $N\times N$ square and the group acting on the $Q$ colors being the symmetric group $S_Q$.
The cycle indices for $G_N$ were carefully documented and computed at the following MSE link I.
The cycle index of the symmetric group can be computed from the classical recurrence by Lovasz.
It then remains to apply the Power Group Enumeration formula / algorithm as documented at the following MSE link II.
We get for the case of coloring a square with at most two interchangeable colors $$1, 4, 51, 4324, 2105872, 4295327872, 35184441295872, \\ 1152921514807410688,\ldots$$ which is [OEIS A182044](https://oeis.org/A182044) where a closed formula can be found.
For at most three colors we get the sequence $$1, 6, 490, 901012, 17653123147, 3126972103187548, \\ 4985402694248850150928, 71535079589434063488162675274, \\ 9238051838396620455005158025879826301,\ldots $$
Finally for at most four colors we get the sequence $$1, 7, 1555, 22396971, 5864091026091, 24595658827938966187, \\ 1650586719048786316922366635, 1772303994379887884341412962742479531, \\ 30447950777727144129269702965544605972525918891,\ldots$$
The sequence of colorings using any number of available interchangeable colors is also quite interesting and starts $$1, 7, 2966, 1310397193, \\ 579823814813639193, 477464341236883456112705749206, \\ 1340767144321669800049265230788088027597024910, \\ 21516767919669856366796245458194341840929552797762722429430679631, \ldots$$
An implementation of this algorithm is included below.