5
$\begingroup$

You have a 6x6 square grid. You have 18 black and 18 white pieces. How many ways can you fill the board (one piece per square) such that there are 3 black and 3 white pieces per column, and such that there are 3 black and 3 white pieces per row?

I've tried to do it purely combinatorally , just looking row by row, but it gets confusing very fast. Is there perhaps some way to do it utilizing symmetries, like how a solution translated horizontally or vertically is a solution, or how the 90 degree rotation around the center of a solution is a solution?

$\endgroup$

2 Answers 2

4
$\begingroup$

By considering the case of a $2 \times 2$ grid with $1$ black piece and $1$ white piece for each row and each column you can count $2$ ways (i.e. BW-WB and WB-BW). It is not too difficult to count patiently all cases for a $4 \times 4$ grid, totalling $90$ ways.

Searching OEIS with $2,90$, you can find OEIS sequence A058527 and, for the $6 \times 6$ grid the value $297200$.

$\endgroup$
1
$\begingroup$

There is an action of the group $G=S_6\times S_6$ on the set of all configurations satisfying these conditions. One copy of $S_6$ permutes the rows and the other permutes the columns. If you write down representatives for each of the orbits under this action, then you can apply the orbit-stabilizer theorem to determine the size of the orbit. I would do this by writing down representatives that have black boxes as close to the top of the grid and as far to the left as possible. So, the top row will always have the three left-most tiles filled in black because this can always be obtained by permuting columns. Also, the top three tiles in the first column will be black because you can obtain this by permuting rows. Then, you go from there placing a black tile as far up and to the left as possible without repeating a previously studied case. The key issue, then, is determining the size of the stabilizer subgroup of $G$.

Let's make the count in the case of a $4\times 4$ grid (which I'll typeset as tic-tac-toe boards). In this case, there is an action of $G=S_4\times S_4$ and $|G|=(24)^2$ (Convention: the first copy acts on rows and the second acts on columns). There are two orbits: $$\begin{array}{|c|c|c|c|}\hline X&X&O&O\\\hline X&X&O&O\\\hline O&O&X&X\\\hline O&O&X&X\\\hline \end{array}\;\;\;\;\;\;\;\;(1) $$ and $$ \begin{array}{|c|c|c|c|}\hline X&X&O&O\\\hline X&O&X&O\\\hline O&X&O&X\\\hline O&O&X&X\\\hline \end{array}\;\;\;\;\;\;\;\;(2) $$ The stabilizer of configuration (1) is $$H=\langle A, (w_0,w_0)\rangle\leq S_4\times S_4$$ where $w_0=(14)(23)$ and $$A=\langle((12),1),((34),1),(1,(12)),(1,(34))\rangle\cong (S_2\times S_2)\times(S_2\times S_2).$$ Since $\langle (w_0,w_0)\rangle$ normalizes $A$, $|A|=16$, $|w_0|=2$, and $\langle (w_0,w_0)\rangle\cap A=\{1\}$, this group has order $|H|=32$ (you can represent this subgroup as a semi-direct product). Therefore, the size of the orbit is $$|G|/|H| = (24)^2/32 = 18.$$ The stabilizer of configuration (2) is $$ K=\langle B,(w_0,w_0)\rangle, $$ where $B=\langle ((1342),(1243))\rangle$ and $w_0$ is as above. Again, $\langle(w_0,w_0)\rangle$ normalizes $B$ and $B\cap\langle (w_0,w_0)\rangle=\{1\}$. This time $|B|=4$, so $|K|=8$. Therefore the size of the orbit is $|G|/|K| = (24)^2/8 =72.$

This gives a count of $18+72 = 90$ configurations.

$\endgroup$
1
  • $\begingroup$ I keep fussing around to get the definition of $B$ right. Note that acting on the conguration with the element $((14),(23))$ induces $$\begin{array}{|c|c|c|c|}\hline X&X&O&O\\\hline X&O&X&O\\\hline O&X&O&X\\\hline O&O&X&X\\\hline \end{array}\longrightarrow \begin{array}{|c|c|c|c|}\hline O&X&O&X\\\hline X&X&O&O\\\hline O&O&X&X\\\hline X&O&X&X\\\hline \end{array}$$ Now, apply the element $((12)(34),(12)(34))$ to get back to the original configuration. $\endgroup$
    – David Hill
    Commented Dec 15, 2020 at 18:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .