Configurations of N tiles on MxM grid, up to rotation/translation?

Question

Suppose we have N identical 1x1 tiles to place on an MxM chess board:

Example:

N = 5, M = 4

.X..
X...
..X.
.XX.

We call this a configuration. (Clearly there are $M^2$ choose $N$ configurations.)

We say two configurations, A and B, are similar if by rotating and/or translating all the tiles of A together they can be placed in B configuration.

For example the following three configurations are similar:

....
.XXX
..X.
..X.

XXX.
.X..
.X..
....

....
X...
XXX.
X...

A configuration class is a maximal set of configurations that are similar to each other. (Clearly the configuration class of any configuration is simply the closure under rotation and translation. Further each configration class is obviously disjoint from every other.)

How many configuration classes are there in terms of N and M?

Any ideas for how to approach this?

(Background: I'm looking at the Game Of Life, and thinking about how to eliminate searching starting configurations that result in similar progressions)

Answer 1

My solution to the problem requires some basic group theory; the group $D_4$ of symmetries of the square, group action, and Burnside's lemma. If you are not familiar with these, I recommend you take an introduction to group theory, or at least look up Burnside's lemma.

---

Let $X$ denote the set of all configurations of $N$ tiles on an $M\times M$ grid, so that $|X|=\binom{M^2}{N}$. Then $D_4$ acts naturally on $X$, and your configuration classes are what then called orbits under this action. We denote the elements of $D_4$ as follows: $$D_4=\{\operatorname{id},\rho,\rho^2,\rho^3,\sigma,\sigma\rho,\sigma\rho^2,\sigma\rho^3\},$$ where $\rho$ denotes the rotation over $\tfrac{\pi}{2}$ radians, and $\sigma$ the reflection in whichever diagonal you prefer. Then $\rho^2$ and $\rho^3$ are the rotations over $\pi$ and $-\tfrac{\pi}{2}$ radians, respectively, $\sigma\rho^2$ is the reflection in the other diagonal. The remaining two reflections are $\sigma\rho$ and $\sigma\rho^3$, and $\operatorname{id}$ is the identity, i.e. "doing nothing". We can count the number of configuration classes or orbits (denoted by $|X/D_4|$) with Burnside's lemma, which tells us that $$|X/D_4|=\frac{1}{|D_4|}\sum_{x\in D_4}|X^x|,$$ where $X^x$ denotes the set of fixed points of $x$. That is, $|X^x|$ is the number of configurations that is invariant under $x$. Note that $|D_4|=8$.

Every configuration is invariant under $\operatorname{id}$, so $|X^{\operatorname{id}}|=\binom{M^2}{N}$. Computing $|X^x|$ for the other $x\in D_4$ is more work:

First, let's compute $|X^{\rho}|$. If $M$ is even, then the $M\times M$ grid can be divided into four $\tfrac{M}{2}\times\tfrac{M}{2}$ squares. If a configuration is invariant under $\rho$, then the configuration in the top-right $\tfrac{M}{2}\times\tfrac{M}{2}$ square determines the entire configuration. Conversely, any configuration of the top-right $\tfrac{M}{2}\times\tfrac{M}{2}$ square determines a unique configuration that is invariant under $\rho$, and in particular the number of tiles must be a multiple of $4$, i.e. we must have $N\equiv0\pmod4$. We conclude that $$|X^{\rho}|=\left\{\begin{array}{cc}\tbinom{M^2/4}{N/4}&\text{ if }N\equiv0\pmod4\\0&\text{ otherwise}\end{array}\right.,$$ if $M$ is even. If $M$ is odd, then the $M\times M$ grid can be divided into four $\tfrac{M-1}{2}\times\frac{M+1}{2}$ rectangles, leavin a single tile in the center. Again, any configuration is invariant under $\rho$ is determined by the configuration of the top-right rectangle, and any configuration of the top-right rectangle determines a configuration invariant under $\rho$. In particular either $N\equiv0\pmod4$ or $N\equiv1\pmod4$, depending on whether the center tile is used or not. We conclude that $$|X^{\rho}|=\left\{\begin{array}{cc}\tbinom{(M^2-1)/4}{N/4}&\text{ if }N\equiv0\pmod4\\\tbinom{(M^2-1)/4}{(N-1)/4}&\text{ if }N\equiv1\pmod4\\0&\text{ otherwise}\end{array}\right.,$$ if $M$ is odd. I will leave the values of $|X^x|$ for the other $x\in D_4$ as an exercise, but here are some expressions for them in case $M$ is even: \begin{eqnarray*} |X^{\rho^2}|&=&\left\{\begin{array}{cl}\tbinom{M^2/2}{N/2}&\text{ if }N\equiv0\pmod2\\0&\text{ otherwise}\end{array}\right.,\\ |X^{\rho^3}|=|X^{\rho}|&=&\left\{\begin{array}{cl}\tbinom{M^2/4}{N/4}&\text{ if }N\equiv0\pmod4\\0&\text{ otherwise}\end{array}\right.,\\ |X^{\sigma\rho}|=|X^{\sigma\rho^3}|&=&\left\{\begin{array}{cl}\tbinom{M^2/2}{N/2}&\text{ if }N\equiv0\pmod2\\0&\text{ otherwise}\end{array}\right., \end{eqnarray*} The expressions for the number of fixed points of $\sigma$ and $\sigma\rho^2$, the reflections in the diagonals, are not as pretty. Let $l=\min\{m,n,m-n\}/2$. Then $$|X^{\sigma}|=|X^{\sigma\rho^2}|=\left\{\begin{array}{cl}\sum_{K=0}^l\binom{M}{2K}\cdot\binom{M(M-1)/2}{N/2-K}&\text{ if }N\equiv0\pmod2\\\sum_{K=0}^{l-1}\binom{M}{2K+1}\cdot\binom{M(M-1)/2}{(N-1)/2-K} &\text{ if }N\equiv1\pmod2\end{array}\right.,$$ still assuming that $M$ is even. For $M$ odd the remaining values give slightly more elaborate expressions, which I will leave as an exercise, as the length of this answer is already making it difficult to continue typing.

As an example, for $M=N=4$ as in your example, we find that \begin{eqnarray*} |X/D_4|&=&\frac{1}{|D_4|}\left(|X^{\operatorname{id}}|+|X^{\rho}|+|X^{\rho^2}|+|X^{\rho^3}|+|X^{\sigma}|+|X^{\sigma\rho}|+|X^{\sigma\rho^2}|+|X^{\sigma\rho^3}|\right)\\ &=&\frac{1}{8}\left(|X^{\operatorname{id}}|+2|X^{\rho}|+3|X^{\rho^2}|+2|X^{\sigma}|\right)\\ &=&\frac{1}{8}\left(\binom{4^2}{4}+2\binom{4^2/4}{4/4}+3\binom{4^2/2}{4/2}+2\sum_{k=0}^2\binom{4}{2k}\binom{4(4-1)/2}{2-k}\right)\\ &=&\frac{1}{8}\left(1820+2\cdot4+3\cdot28+2\cdot(15+36+1)\right)=252 \end{eqnarray*}

EDIT: I just noticed that your example takes $M=4$, $N=5$, in which case the expressions simplify significantly. As before we find $$|X/D_4|=\frac{1}{8}\left(\binom{16}{5}+2\left(\binom{4}{1}\binom{6}{2}+\binom{4}{3}\binom{6}{1}\right)\right)=567.$$

Answer 2

I get the impression the first answer does not treat the question's intent. The action of the dihedral group $D_4$ on the board does not accomplish all the symmetries shown in the example. I would guess that we should rather think of the board as an $M\times M$ torus, where the configurations may move horizontally and vertically (i.e., be translated) as well as rotate.

The following Maple program computes the cycle index of the group of symmetries of the $M\times M$ torus for use with the Polya Enumeration Theorem.

with(combinat):


pet_autom2cycles :=
proc(src, aut)
        local numa, numsubs;
        local marks, pos, cycs, cpos, clen;

        numsubs := [seq(src[k]=k, k=1..nops(src))];
        numa := subs(numsubs, aut);

        marks := [seq(true, pos=1..nops(aut))];

        cycs := []; pos := 1;

        while pos <= nops(aut) do
              if marks[pos] then
                 clen := 0; cpos := pos;

                 while marks[cpos] do
                       marks[cpos] := false;
                       cpos := numa[cpos];
                       clen := clen+1;
                 od;

                 cycs := [op(cycs), clen];
              fi;

              pos := pos+1;
        od;

        return mul(a[cycs[k]], k=1..nops(cycs));
end;



pet_torus_cind :=
proc(M, rot_on)
        option remember;
        local A, rot, rmx, tx, ty, i, j, x, y, xx, yy, res, r;

        if M=1 then return a[1] fi;
        if M=2 then rmx := 1 else rmx := 3 fi;

        if not rot_on and M>1 then rmx := 0 fi;

        res := 0;

        for rot from 0 to rmx do
            for tx from 0 to M-1 do
                for ty from 0 to M-1 do
                    A := [];

                    for i from 0 to M-1 do
                        for j from 0 to M-1 do
                            x := (i+tx) mod M;
                            y := (j+ty) mod M;

                            for r to rot do
                                xx := x; yy := y;
                                x := M-1-yy; y := xx;
                            od;

                            A := [op(A), x*M+y];
                        od;
                    od;

                    res := res+
                    pet_autom2cycles([seq(k, k=0..M*M-1)], A);
                od;
            od;
        od;

        return res/(rmx+1)/M^2;
end;


pet_varinto_cind :=
proc(poly, ind)
        local subs1, subs2, polyvars, indvars, v, pot, res;

        res := ind;

        polyvars := indets(poly);
        indvars := indets(ind);

        for v in indvars do
            pot := op(1, v);

            subs1 :=
            [seq(polyvars[k]=polyvars[k]^pot,
                 k=1..nops(polyvars))];

            subs2 := [v=subs(subs1, poly)];

            res := subs(subs2, res);
        od;

        res;
end;

pet_torus_count :=
proc(M, C, rot_on)
        local ind, gf, vs, k;

        ind := pet_torus_cind(M, rot_on);
        vs := add(cat(`X`, k), k=1..C);
        gf := pet_varinto_cind(vs, ind);

        subs([seq(cat(`X`, k)=1, k=1..C)], gf);
end;

The above program can compute cycle indices when 90 degree rotations of the board are allowed or not allowed. This gives the following two cycle indices for the case $M=4,$ first, without rotations using translations only: $$1/16\,{a_{{1}}}^{16}+3/4\,{a_{{4}}}^{4}+3/16\,{a_{{2}}}^{8}$$ and including rotations: $${\frac {1}{64}}\,{a_{{1}}}^{16}+{\frac {7}{16}}\,{a_{{4}}}^{4}+{\frac {15}{64}} \,{a_{{2}}}^{8}+1/4\,{a_{{4}}}^{3}{a_{{1}}}^{2}a_{{2}}+1/16\,{a_{{2}}}^{6}{a_{{1 }}}^{4}.$$ Substituting into these cycle indices we obtain the two generating functions $${z}^{16}+{z}^{15}+9\,{z}^{14}+35\,{z}^{13}+122\,{z}^{12}+273\,{z}^{11}\\+511\,{z}^ {10}+715\,{z}^{9}+822\,{z}^{8}+715\,{z}^{7}+511\,{z}^{6}+273\,{z}^{5}+122\,{z}^{ 4}+35\,{z}^{3}+9\,{z}^{2}+z+1$$ and $${z}^{16}+{z}^{15}+5\,{z}^{14}+11\,{z}^{13}+41\,{z}^{12}+75\,{z}^{11}\\+147\,{z}^{ 10}+189\,{z}^{9}+231\,{z}^{8}+189\,{z}^{7}+147\,{z}^{6}+75\,{z}^{5}+41\,{z}^{4}+ 11\,{z}^{3}+5\,{z}^{2}+z+1.$$ This means that there are $273$ resp. $75$ different configurations when $M=4$ and $N=5$.

We can also use this program to compute the total count of toroidal configurations having $C$ colors. For two colors with translations only we get the sequence $$2, 7, 64, 4156, 1342208, 1908897152, 11488774559744, 288230376353050816, \\ 29850020237398264483840, 12676506002282327791964489728,\ldots$$ which is A179043 from the OEIS. Including rotations we get $$2, 6, 28, 1171, 337664, 477339616, 2872202032640, 72057595967392816, \\7462505059899322983424, 3169126500571074529242309120,\ldots$$ For three colors we get the two sequences $$3, 27, 2211, 2691711, 33891544611, 4169295457320267, 4883659780216684279491, \\53651309692070594433108320631, 5474401089420219382077156686715199875,\ldots$$ and $$3, 21, 627, 678051, 8473285827, 1042324154944641, 1220914945265994019395, \\13412827423019038373526335841, 1368600272355054854637538271201673171,\ldots$$ Finally for the special case of $M$ marks placed on an $M\times M$ board we get the two sequences $$1, 3, 12, 122, 2130, 54192, 1753080, 69160548, 3220837758, 173103158180,\ldots$$ and $$1, 2, 4, 41, 552, 13786, 438776, 17300202, 805232382, 43276368018,\ldots$$