3
$\begingroup$

I want to color a 3x4 rectangle using 2 colors. The number of squares colored by each color must equal 6. However, we say that two colorings are equal if they can be obtained from each other by permutating rows or by cyclically permutating columns, e.g. $$\matrix{1 & 1 & 0 & 1\\0&1&0&1\\1&0&0&0}=\matrix{0&1&0&1\\0&1&1&1\\0&0&1&0}$$ (we switch the first two rows and then move columns cyclically by two)
The only way I thought of for calculating that was count the total number of such colorings $\binom{12}{6}=924$, and dividing it first by 6 (because each coloring has 6 ways to be permutated), then by 4 (because each coloring has 4 different corresponding cyclic permutations), but that clearly doesn't work, not only because e. g.$$\matrix{0&1&0&0\\1&1&1&1\\0&1&0&0}$$ has only 3 different row permutations, but also because 924 is not divisible by 24. So what is the proper way to solve that (without brute-forcing all 924 colorings)?

$\endgroup$
  • 1
    $\begingroup$ My brute forcing with python gives 48 solutions ['03f', '05f', '077', '07b', '07d', '11f', '12f', '137', '13b', '13d', '13e', '14f', '157', '15b', '15d', '15e', '167', '16b', '16d', '16e', '179', '17a', '17c', '19b', '19d', '19e', '1ab', '1ad', '1ae', '1bc', '1cd', '1ce', '333', '335', '336', '339', '33a', '33c', '355', '356', '359', '35a', '35c', '369', '3aa', '3ac', '555', '55a']. Each digit is the hexadecimal version of a binary row (so f is 15 or 1 1 1 1 for example). $\endgroup$ – Gribouillis Aug 23 '17 at 9:26
4
$\begingroup$

The way to count these is by using Burnside's Lemma.

First you have to work out in what ways you can transform one of your rectangles in general. You can cyclicly permute the columns in 4 ways, and permute the rows in 6 ways. You can combine these (in either order) to get 24 ways in which a rectangle can be transformed. Each of those 24 ways may or may not actually result in a different pattern. I'll denote the transformation by $[r,c]$ where $r$ is the row permutation, and $c$ is the column permutation.

For each of those 24 transformations $[r,c]$ you now have to count how many of the rectangles remain unchanged.

$[i,i]$: This is the identity where the rows/columns are not permuted at all. All $\binom{12}{6}=924$ rectangles stay the same when nothing is permuted.

$[(123),i], [(132),i]$: Here only the rows are cyclicly permuted. This means each column must have a single colour. We need two columns of each colour so there are $\binom{4}{2}=6$ rectangles that stay the same when rows are cyclicly permuted.

$[i,(1234)], [i,(1432)]$: Here only the columns are permuted one step in either direction. Now each row must be of a single colour. This is not possible with 6 cells of each colour, so there are $0$ rectangles that stay the same under this transformation.

$[i,(13)(24)]$: Now the columns are permuted 2 steps, so the left $3\times2$ and right $3\times2$ halves of the rectangle must be the same. Each half must contain 3 of each colour, so there are $\binom{6}{3}=20$ such rectangles.

$[(123),(1234)], [(123),(1432)], [(132),(1234)], [(132),(1432)]$: Applying any of these transformations 3 times is the same as $[i,(1432)]$ or $[i,(1234)]$, so no rectangles remain the same under this transformation.

$[(123),(13)(24)], [(132),(13)(24)]$: Applying any of these transformations 3 times is the same as $(i,(13)(24))$, and applying it twice gives $[(123),i]$ or $[(132),i]$. Therefore it must have alternating columns, for which there are $2$ possibilities.

$[(12),i], [(13),i], [(23),i]$: Here the two swapped rows must be the same. If the other row is all one colour, then there are $2\binom{4}{1}=8$ possibilities. If the other row has two of each colour, then there are $\binom{4}{2}\binom{4}{2}=36$ possibilities. So $44$ in total.

$[(12),(1234)], [(23),(1234)], [(13),(1234)], [(12),(1432)], [(23),(1432)] [(13),(1432)]$: Here the stationary row must have one colour. Those other two rows must consist of two equal halves but this is not possible with only exactly 6 cells of each colour.

$[(12),(13)(24)], [(23),(13)(24)], [(13),(13)(24)]$: The six cells in the left half of the rectangle fully determine the other half. There must be 3 of each colour in each half so there are $\binom{6}{3}=20$ such rectangles.

The 24 numbers we got are therefore $924, 6, 6, 0, 0, 20, 0, 0, 0, 0, 2, 2, 44, 44, 44, 0, 0, 0, 0, 0, 0, 20, 20, 20$.

Burnside's Lemma says that the total number of distinct rectangles is the average of these $24$ numbers, i.e. $(924+2*6+20+2*2+3*44+3*20)/24 = 48$.

$\endgroup$
  • $\begingroup$ Is the fact that $[i,(1234)], [i,(1432)]$ give no fixed points enough to state that if we replace i with any permutation there will still be no fixed points? $\endgroup$ – Joald Aug 24 '17 at 8:26
  • $\begingroup$ @Joald Not by itself. For example $[(12),(1234)]$ fixes this rectangle: $$ABAB\\BABA\\CCCC$$ So if we did not also have the restriction of having 6 of each colour, then there would have been solutions when a pair of rows were swapped. There are also solutions if there were 3 colours, 4 of each. $\endgroup$ – Jaap Scherphuis Aug 24 '17 at 8:47
  • $\begingroup$ But under the ruleset that accepts such a rectangle $[i,(1234)],[i,(1432)]$ has fixed points. I guess what I was asking would be, given a composition of two groups $G$ and $H$ and a set $X$, if we know that for a certain $ h \in H \ \forall_{x \in X}\ id_G \circ h(x) \not= x$, is it true that $\forall_{g \in G\setminus \{ h^{-1}\}}g\circ h(x) \not= x$? $\endgroup$ – Joald Aug 24 '17 at 11:36
  • $\begingroup$ I see what you mean now. You are right. Considering the 12 cells as distinct items that are permuted, then $[i,(1234)]$ permutes them as three $4$-cycles. If you change the $i$ to some other permutation, then you can get only $4$-cycles, $8$-cycles, or $12$-cycles. If the colouring rules do not allow for the $4$-cycles to be coloured, then clumping them together as $8$- or $12$-cycles will not help. This generalises to larger rectangles. I'm not sure what is needed to generalise it further to a product of 2 groups acting on a set. Maybe cross product only, and that the action is faithful. $\endgroup$ – Jaap Scherphuis Aug 24 '17 at 12:02
  • $\begingroup$ Also, when considering e.g. $[(12),(13)(24)]$ why are we counting all possible placements of 3 colors with $\binom{6}{3}$, when we need the first two to be equal? $\endgroup$ – Joald Aug 24 '17 at 12:02
2
$\begingroup$

Well, one way is to use Burnside's Counting Lemma. There may be easier ways, but I like Burnside's counting lemma.

There are, as you noted, 924 ways to colour the grid if you ignore symmetry.

The symmetries give a group action on those 924 colorings, you want to count the orbits of that action.

Burnside's counting lemma says that to count the orbits, you can average the number of colourings fixed by each element of the group.

The symmetry group is $S_3\times S_4$, which has 144 elements, so that's a lot of work, but you can simplify things a bit as follows.

Instead of counting orbits of the 924 colourings, you realise that the action of $S_4$ preserves the column counts, so a colouring with 3 in one column, 2 in another, 1 in a third column and 0 in a fourth column will always have those counts, no matter how you permute the rows and columns. So, I'll count colourings with those numbers of coloured squares in the first, second, third and fourth columns respectively, and average the number of such colourings fixed by each element of $S_3$.

There's ${}^3C_3$ ways to colour the first column, ${}^3C_2$ ways to colour the second column, ${}^3C_1$ ways to colour the third column and ${}^3C_0$ ways to colour the last column. That's a total of $1\times3\times3\times1$ colourings. But I need to take symmetries into account.

Well, $S_3$ has six elements. All 9 colourings are fixed by the identity $i$.

Three of the elements of $S_3$ are transpositions. Only 1 colouring is fixed by any given transposition.

Two of the elements of $S_3$ are cycles of order $3$, and they don't fix any colouring.

The average number of colourings fixed by the elements of $S_3$ is $(9+1+1+1+0+0)/6$, which is $2$.

Likewise, you can count the colourings whose column totals are (3,3,0,0), (3,1,1,1), (2,2,2,0) and (2,2,1,1) to get the total number of colourings

[the answer, BTW, is 27]

$\endgroup$
  • $\begingroup$ The question allows only cyclicly permuting the rows/columns, so there are only 12 elements in the group, i.e. $C_3\times C_4$ instead of $S_3\times S_4$. $\endgroup$ – Jaap Scherphuis Aug 23 '17 at 7:41
  • $\begingroup$ @JaapScherphuis I read it as $S_3\times C_4$: "by permuting rows or by cyclically permuting columns." $\endgroup$ – bof Aug 23 '17 at 7:59
  • $\begingroup$ I think @bof is right, it's $S_3\times C_4$. So there's a lot more than 27 colourings. $\endgroup$ – Michael Hartley Aug 23 '17 at 8:02
  • $\begingroup$ Ah yes, I misread it too. $\endgroup$ – Jaap Scherphuis Aug 23 '17 at 8:04

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.