2
$\begingroup$

Say I want to place 8 rooks onto a chess board such that none of them are attacking each other. Trivially, there can only be one rook per row and column, implying that there are $8! = 40320$ solutions in total.

However, some of these solutions are identical, as in rotational, or reflectively symmetrical, so I was wondering just how many unique solutions exist, such that you cannot create another one from one.

Thank you!

$\endgroup$
  • $\begingroup$ you can solve this by using burnside on the 8 symmetries $\endgroup$ – Jorge Fernández Hidalgo Jan 11 '18 at 2:25
3
$\begingroup$

To solve this problem we can use Burnsides lemma.

the acting group is clearly $D_8$. Lets count how many elements are fixed by the $8$ symmetries.

The identity clearly fixes all $8!$ symmetries

The horizontal and vertical reflections clearly dont fix any solutions because all of the orbits are contained in one row/column.

The rotations by $90$ degrees have orbits of $4$ squares each. So clearly a solution must consist of exactly $2$ orbits. Every orbit can be described in the form $(x,y)$ with $1\leq x,y \leq 4$ (because every orbit has exactly $1$ element in the bottom left corner) and clearly we want our two orbits to cover all $4$ numbers. Hence there are $12$ different such solutions. ( there are $\binom{4}{2}$ ways to select the $x$ coordinates and $2$ ways to match up the remaining coordinates)

The rotation by $180$ degrees splits the board into orbits of $2$ squares each. A solution can be represented by the $4$ elements that are on the left side of the board. These $4$ elements must cover the $4$ columns and the rows they occupy must be distinct, it is also forbidden two have two ocuppied rows that are in symmetry with respect to the horizontal line of symmetry. Thus there are $4!2^4$ such solutions.

Finally we work with the diagonal reflections, these are in bijection with the number of involutions in $S_8$ which is $764$ (see telephone numbers for more info)

In conclusion the number of distinct solutions is $\frac{8!+ 2(0)+2(12)+(4!2^4)+2(764)}{8}=5282$ as desired.

$\endgroup$
  • $\begingroup$ I think you mean $\binom{4}{2}$, not $\binom{3}{2}$. $\endgroup$ – Nishant Jan 11 '18 at 3:26
  • $\begingroup$ indeed${}{}{}{}$ $\endgroup$ – Jorge Fernández Hidalgo Jan 11 '18 at 3:27

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.