Intereting Posts

$m$ is a perfect square iff $m$ has an odd number of divisors?
On convergence of nets in a topological space
Clarification regarding little n-discs operads
Prove that if $n$ is composite, then $(n-1)! \equiv 0 \pmod n$
EigenValues and EigenVectors in PCA?
Is there no formula for $\cos(x^2)$?
What does recursive cosine sequence converge to?
Godel's pairing function and proving c = c*c for aleph cardinals
Show $S = f^{-1}(f(S))$ for all subsets $S$ iff $f$ is injective
Number of ways of reaching a point from origin
Complex Analysis Book
Finding an orthonormal basis for the space $P_2$ with respect to a given inner product
Taking seats on a plane: probability that the last two persons take their proper seats
Are rank of T and T^* equal?
Need help with $\int_0^1 \frac{\ln(1+x^2)}{1+x} dx$

Suppose we have N identical 1×1 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.)

- Coloring the faces of a hypercube
- An unexpected application of non-trivial combinatorics
- Permutations with k inversions. Combinatorial proof.
- count the ways to fill a $4\times n$ board with dominoes
- Nicer expression for the following differential operator
- A mouse leaping along the square tile

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)

- Strange combinatorial identity $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$
- Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)
- A probability interview questions on pen type
- Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
- A question on calculating probabilities for the random walk
- Expected size of subset forming convex polygon.
- Question involving chess master (combinatorics)
- What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?
- Tiling of regular polygon by rhombuses
- Number of relations that are both symmetric and reflexive

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

$$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.$$

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$$

- Solving $a^2+3b^2=c^2$
- A proof for Landau inequality and similar cases
- How else can we be nauty?
- Matrix exponential of a skew symmetric matrix
- for each $\epsilon >0$ there is a $\delta >0$ such that whenever $m(A)<\delta$, $\int_A f(x)dx <\epsilon$
- Compactness and sequential compactness
- Free Schroedinger equation
- Confounding Lagrange multiplier problem
- Irrational numbers to the power of other irrational numbers: A beautiful proof question
- Strictly convex Inequality in $l^p$
- If the dot product between two vectors is $0$, are the two linearly independent?
- Curve on a sphere
- Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square
- Is the function $f(x)=x$ on $\{\pm\frac1n:n\in\Bbb N\}$ differentiable at $0$?
- How prove this $\prod_{1\le i<j\le n}\frac{a_{j}-a_{i}}{j-i}$ is integer