2
$\begingroup$

In a $4 \times 4$ square, how many different patterns can be made by shading exactly two of the sixteen squares? Patterns that can be matched by flips and/or turns are not considered different.

How many different patterns can be made for a $5\times5$ square?

Would the answers be $15$ and $36$ respectively?

How about an $n \times n$ square?

Would there be two answers for the $n\times n$ square: an answer for each odd and even dimensions?

Edit: MJD I don't see how to apply the Cauchy-Frobenius-Burnside-Redfield-Pólya lemma. Can you show me how to apply it for a $3 \times 3$ case? I can verify the answer for that case.

$\endgroup$
  • $\begingroup$ How did you derive 15 respectively 36? $\endgroup$ – fgp Apr 7 '14 at 21:22
  • $\begingroup$ Did you get a different answer? $\endgroup$ – Jesse Apr 7 '14 at 21:30
  • $\begingroup$ I expect it to be much larger, but I might be overlooking something. And in any case, you're expected to show your work when positing a question here - just posting a question without any explanation of what you have tried is usually frowned upon... $\endgroup$ – fgp Apr 7 '14 at 21:33
  • $\begingroup$ Forget the part about me expecting it to be much larger - I miss-read, and thought arbitrarily many squares may be shaded, not just two. $\endgroup$ – fgp Apr 7 '14 at 21:37
  • $\begingroup$ I am just looking for confirmation of what I have tried, I don't know why that would be frowned upon. If someone already knows how to do the problem and can let me know if I am in the right direction by confirming my answers that will help. I am not asking someone to write me up a solution to a problem I have not attempted. Anyways, thanks for taking a look at the problem. $\endgroup$ – Jesse Apr 7 '14 at 21:50
3
$\begingroup$

The analysis is different depending on whether $n$ is even or odd. I will do the case of $n$ even, and leave odd $n$ to you.

To use the Cauchy–Frobenius–Burnside–Redfield–Pólya lemma, we first divide the 8 symmetries of the square into five conjugacy classes, and count the number of colorings that are left fixed by each symmetry:

  1. A horizontal or vertical flip divides the squares into $\frac12n^2$ orbits of 2 squares each. For a coloring to be fixed by this reflection, both shaded squares must be in the same orbit, so these symmetries each fix exactly $\frac12n^2$ of the possible colorings.
  2. The two diagonal flips divide the squares into $n$ single-square orbits (along the diagonals) plus $\frac12(n^2-n)$ two-square orbits (elsewhere), Either one of the two-square or two of the one-square orbits must be shaded. There are $\frac12(n^2-n)$ two-square orbits, plus $\frac12(n^2-n)$ ways to color two one-square orbits, for a total of $n^2-n$ colorings fixed by these flips.
  3. A $90^\circ$ clockwise or counterclockwise rotation divides the squares into $\frac14n^2$ orbits of 4 squares each. There is no way to shade two squares that will be fixed by a $90^\circ$ rotation.
  4. A $180^\circ$ rotation divides the squares into $\frac12n^2$ orbits of 2 squares each, so there are $\frac12n^2$ colorings that are fixed by this symmetry.
  5. The identity symmetry divides the squares trivially into $n^2$ orbits of 1 square each. Any two squares can be shaded, so $\frac12n^2(n^2-1)$ colorings are fixed.

By the CFBRP lemma, the number of distinct colorings of the $n\times n$ array, (where $n$ is even) is the average number of colorings left fixed by each symmetry:

$$\frac18\left( \underbrace{2\left(\frac12n^2\right)}_{\text{horiz / vert flip}} + \underbrace{2(n^2-n)}_{\text{diag flip}}+ \underbrace{2\cdot0}_{90^\circ\text{ rot.}}+ \underbrace{\frac12n^2}_{180^\circ\text{ rot.}} + \underbrace{\frac12n^2(n^2-1)}_{\text{identity}} \right).$$

This simplifies to: $$\frac18\left(\frac12n^4+3n^2-2n\right).$$ Taking $n=2$, for example, we get $2$, which is correct: you can color two adjacent squares, or two squares on a diagonal. Taking $n=4$ we get 21, which I check as follows: There are three kinds of squares in a $4×4$ array: corners, edges, and centers.

  • There are 2 ways to shade two center squares.
  • There are 2 ways to shade two corner squares.
  • After shading one of the edge squares, there are 6 ways to shade another edge square. (The seventh, with the two shaded squares separated by a knight's move, is equivalent under $90^\circ$ rotation to one of the others.)
  • After shading a center square, there are 3 ways to shade a corner square.
  • After shading a center square, there are 4 ways to shade an edge square.
  • After shading a corner square, there are 4 ways to shade an edge square.

That's 21 shadings total, which checks.

$\endgroup$
  • $\begingroup$ For readers of both MJDs post and my post, I offer some assistance. Burnside says that we need to count the number of shadings fixed by permutations from the automorphism group and average. That means they need to be constant on the cycles of these permutations. Now use the term orbit instead of cycle and you have a bridge between the two approaches. You are placing the two shaded squares on the cycles of the permutation. This readily shows that the 4-cycles of 90 degree rotations do not contribute. If you have only two markers to put on a 4-cycle they can't be constant on that cycle. $\endgroup$ – Marko Riedel Apr 8 '14 at 1:13
3
$\begingroup$

By way of a more targeted hint there is this MSE post which shows how to solve the general problem. You need to compute the cycle index of the permutation group of the grid acting on the squares.

Here is the (trivial) cycle index for $n=1$: $$ a_{{1}}$$ and for $n=2$ $$ 1/8\,{a_{{1}}}^{4}+3/8\,{a_{{2}}}^{2}+1/4\,{a_{{1}}}^{2}a_{{2}}+1/4\,a_{{4}}$$ for $n=3$ $$1/8\,{a_{{1}}}^{9}+1/2\,{a_{{1}}}^{3}{a_{{2}}}^{3}+1/8\,a_{{1}}{a_{{2}}}^{4}+ 1/4\,a_{{1}}{a_{{4}}}^{2} $$ for $n=4$ $$1/8\,{a_{{1}}}^{16}+3/8\,{a_{{2}}}^{8}+1/4\,{a_{{1}}}^{4}{a_{{2}}}^{6}+1/4\,{ a_{{4}}}^{4} $$ for $n=5$ $$1/8\,{a_{{1}}}^{25}+1/2\,{a_{{1}}}^{5}{a_{{2}}}^{10}+1/8\,a_{{1}}{a_{{2}}}^{ 12}+1/4\,a_{{1}}{a_{{4}}}^{6} $$ and for $n=6$ $$1/8\,{a_{{1}}}^{36}+3/8\,{a_{{2}}}^{18}+1/4\,{a_{{1}}}^{6}{a_{{2}}}^{15}+1/4 \,{a_{{4}}}^{9}. $$ Shading exactly two of the squares you want to compute $$[z^2] Z(G)(1+z)$$ where $Z(G)$ is the appropriate cycle index which gives the sequence $$ 0, 2, 8, 21, 49, 93, 171, 278, 446, 660, \ldots$$ This is OEIS A014409 which seems to match your problem definition so this is probably correct.

Using pen and paper to verify the value $8$ for $n=3$ we get: colorings where a corner is colored and paired: 1 -- with an adjacent square, 2 -- with a square in the same row/column, 3 -- with the opposite corner, 4 -- with the midpoint of the opposite edge and 5 -- with the center square. Then there is 6 -- the center square paired with an adjacent square and 7 -- two opposite middle squares of two opposite sides and finally, 8 -- two side midpoint squares that share a corner.

Addendum. Inspired by MJDs work let me quote the general formula for the cycle index with $n$ even from the post I cited in the introduction, which is $$1/8\,{a_{{1}}}^{{n}^{2}}+3/8\,{a_{{2}}}^{1/2\,{n}^{2}}+1/4\,{a_{{1}}}^{n}{a_{ {2}}}^{1/2\,{n}^{2}-1/2\,n}+1/4\,{a_{{4}}}^{1/4\,{n}^{2}}.$$ Substituting $1+z$ into this cycle index we get $$1/8\,{(1+z)}^{{n}^{2}}+3/8\,{(1+z^2)}^{1/2\,{n}^{2}}+1/4\,{(1+z)}^{n}{(1+z^2)}^{1/2\,{n}^{2}-1/2\,n}+1/4\,{(1+z^4)}^{1/4\,{n}^{2}}.$$ Extracting the coefficient $[z^2]$ from this we see that the last term does not contribute (polynomial in $z^4$). The remaining contributions are (use the binomial theorem) $$1/8 {n^2\choose 2} + 3/8 {1/2\times n^2\choose 1} + 1/4 {n\choose 2} + 1/4 {1/2 \times n^2 - 1/2\times n\choose 1}.$$ Expanding these binomial coefficients which are simple, fortunately, we obtain the formula $$1/16\,{n}^{4}+3/8\,{n}^{2}-1/4\,n$$ which matches the result by MJD.

$\endgroup$
  • $\begingroup$ I have posted a list of these PET/BL examples. I know you often post such analyses, and I would be grateful if you would add to the list any that I left out. $\endgroup$ – MJD Apr 8 '14 at 2:13
  • $\begingroup$ Thanks. That seems like a useful list. As we seem to be editing concurrently I will pause for a moment. $\endgroup$ – Marko Riedel Apr 8 '14 at 2:46
  • $\begingroup$ I think I'm done for the night. Thanks for your contributions. I have enjoyed finding and reading more of your many posts applying the PET. $\endgroup$ – MJD Apr 8 '14 at 2:48
  • $\begingroup$ I am wondering, why is it you put the question on hold after going to the trouble of writing such an excellent answer? $\endgroup$ – Marko Riedel Apr 8 '14 at 17:46
  • $\begingroup$ I mistakenly thought it was a duplicate of math.stackexchange.com/questions/570003/… . Then I wrote the answer, but forgot to retract my close vote. $\endgroup$ – MJD Apr 8 '14 at 17:47

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.