23
$\begingroup$

Extra conditions that put a formal solution out of my reach: the centre cell must contain a $0$, and two grids are equal if they have a symmetry, e.g. $$\left( \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1\end{array} \right) = \left( \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array} \right) = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0\end{array} \right) $$ For context, this question is part of an investigation into the number of possible checkmate patterns in chess.

$\endgroup$
  • 1
    $\begingroup$ When you say symmetry, it means "up to a rotation", right ? Do you include "true" symmetries (mirror symmetries wrt an axis, vertical, horizontal, at 45°) ? $\endgroup$ – Jean Marie Oct 23 '17 at 6:30
  • 4
    $\begingroup$ @JeanMarie The example matrices imply that reflections and rotations are considered equivalent. $\endgroup$ – Parcly Taxel Oct 23 '17 at 6:39
  • 7
    $\begingroup$ For this one-time calculation, I wouldn't bother trying to analyze it by hand. Just write a program. The time to write the program shouldn't be that much greater than the time for a by-hand analysis. Also, the code could be reused in the future for similar problems. $\endgroup$ – quasi Oct 23 '17 at 6:39
  • 1
    $\begingroup$ @quasi I fully agree with you. $\endgroup$ – Jean Marie Oct 23 '17 at 6:40
  • 6
    $\begingroup$ @quasi Don't bother with a computer. Burnside's lemma works here. $\endgroup$ – Parcly Taxel Oct 23 '17 at 6:41
46
$\begingroup$

Use Burnside's lemma. The number of symmetries of the matrix is eight:

  • the identity, leaving $2^8$ admissible matrices unchanged (the centre cell being fixed)
  • two 90° rotations leaving $2^2$ matrices unchanged each
  • a 180° rotation leaving $2^4$ matrices unchanged
  • four reflections leaving $2^5$ matrices unchanged each

So the number of possible matrices up to symmetry is $$\frac{2^8+2\cdot2^2+2^4+4\cdot2^5}8=32+1+2+16=51$$

$\endgroup$
  • 13
    $\begingroup$ [+1] Burnside's lemma... what a tool... $\endgroup$ – Jean Marie Oct 23 '17 at 9:26
  • 6
    $\begingroup$ I notice (wiki page) that "..there are 57 rotationally distinct colourings of the faces of a cube in three colours." Same as the number of Heinz ketchup types. Coincidence? Alien influence? $\endgroup$ – Carl Witthoft Oct 23 '17 at 18: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.