6
$\begingroup$

Let's say we have a $3×3$ square where $3$ of the cells are labeled $a$, $b$, $c$ and the rest are blank. Two such squares are considered "equivalent" if one square can be obtained from another square by 1) rotation on 90, 180, and 270 degrees, 2) reflection (through the horizontal, vertical, or either diagonal axis).

I need to find equivalence classes of squares (maybe groups or patterns?).

My attempt is: 1) put the $a$, $b$ and $c$ in the 1-st row: $A=\left(% \begin{array}{ccc} a & b & c \\ .. & .. & .. \\ .. & .. & .. \\ \end{array} \right)$, then we can rotate the square $A$ on 90, 180 and 270 degrees: $A_{90}=\left(% \begin{array}{ccc} .. & .. & a \\ .. & .. & b\\ .. & .. & c \\ \end{array} \right)$, $A_{180}=\left(% \begin{array}{ccc} .. & .. & .. \\ .. & .. & ..\\ c & b & a \\ \end{array} \right)$, $A_{270}=\left(% \begin{array}{ccc} c & .. & .. \\ b & .. & ..\\ a & .. & .. \\ \end{array}. \right)$.

Four square $A$, $A_{90}$, $A_{180}$ and $A_{270}$ are equvalent. This is the first equivalence class.

2) put the $a$, $b$ and $c$ in the main diagonal: $$A=\left(% \begin{array}{ccc} a & .. & .. \\ .. & b & .. \\ .. & .. & c \\ \end{array}% \right) $$ and rotate on 90 degree $$A_{90}=\left(% \begin{array}{ccc} .. & .. & a \\ .. & b & .. \\ c & .. & .. \\ \end{array}% \right) $$ Two square $A$ and $A_{90}$ are equvalent. This is the second equivalence class.

Edit 2. Here I have found the 16 patterns.

enter image description here

Question. How many equivalence classes for three elements in a square are there?

$\endgroup$
  • 1
    $\begingroup$ 7*8*9 is the number of combinations without symmetry property of the table. $\endgroup$ – Nick Feb 26 at 3:39
  • 4
    $\begingroup$ This is a burnside’s lemma type problem; to count the number of labelings up to symmetry, you compute the average number of labelings which are fixed by each symmetry of the table. $\endgroup$ – Mike Earnest Feb 26 at 4:23
  • 1
    $\begingroup$ "the number of different combinations of three integers a, b and c in the 3×3 table " does not have any meaning to me. What is a combination of integers in a table? $\endgroup$ – miracle173 Feb 26 at 10:27
  • 2
    $\begingroup$ Can I propose the following re-wording? Consider the $8$ symmetries of the square, as in the reference wikidot link. Now consider a $3 \times 3$ square where $3$ of the cells are labeled $a, b, c$ and the rest are blank. Two such squares are considered "equivalent" if they are related by one of the $8$ symmetries. So the problem becomes: how many "different" squares are there (i.e. how many equivalence classes)? If this interpretation is what you want, then (1) your $5$ examples are confusing, and (2) consider @MikeEarnest comment re: burnside lemma. $\endgroup$ – antkam Feb 26 at 14:33
  • 1
    $\begingroup$ wait... only rotations are equivalent? i.e. two squares which are mirror images (reflections) of each other are considered different? $\endgroup$ – antkam Feb 26 at 16:13
2
$\begingroup$

It is unclear whether you want to count

  1. Placements, or

  2. Labelings.

up to symmetry. The two grids below have the same placement, but different labelings. The number of labelings without symmetry is $9\times 8\times 7$. The number of placements is $(9\times 8\times 7)/(3!)$.

a b c     a c b
. . .     . . .
. . .     . . .

Placements

There are $8$ symmetries of array:

  • The identity symmetry.

  • Three rotations, by $90,180$ and $270$ degrees.

  • Four reflections, through the horizontal, vertical, or either diagonal axis.

In order to count the number of placements up to symmetry, we add up, for each symmetry, the number of placements which invariant under that symmetry, then divide by $8$.

  • Each of the $\binom{9}3$ placements is invariant under the identity.

  • There are no placements with three numbers which are invariant under $90^\circ$ rotation.

  • There are $4 $ placements which are invariant under $180^\circ$ rotation. These are placements which have a three in a row through the center.

  • For the horizontal reflection, there are $10$ placements with that symmetry. There are two cases; either two of the numbers are symmetric about the vertical axis, going in spots A, B or C, or they are all on the vertical axis. In the first case, there are $3$ choices for A, B or C, ,and three choices for where the last number goes. The second case has one option, for $3\cdot 3+1=10$ total.

A 1 A
B 2 B
C 3 C
  • The same answer is true for the other three reflections.

Therefore, the number of placements up to symmetry is

$$ \frac18\left(\binom{9}3+4+4\cdot 10\right)=\frac18(84+44)=16 $$

Labelings

I leave the details to the reader, but the answer is

$$ \frac18(9\cdot 8\cdot 7+3\cdot 0+4\cdot (3\cdot 2\cdot 1))=66 $$

$\endgroup$
  • 1
    $\begingroup$ As a side note; I was confused for a long time because I though that you should have # Labelings = 6$\times$ # Placements. This is not the case. $\endgroup$ – Mike Earnest Feb 26 at 16:25

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.