In how many ways can we place $8$ identical rooks on a chessboard so that none of them attacks each other and none of them stands on the long diagonal A1 – H8?
I thought about the inclusion-exclusion principle, however, it is hard to determine how many possible movements each of these rooks will have – it depends on the choice of the one to rearrange.
Also, I made some observations on the chessboard and noticed that it is not possible to have an odd number of rooks out of the long diagonal whereas the rest of them occupy it – it may be of some help to the inclusion-exclusion but I can't link it together.
Any hints will be most appreciated.
Best Answer
Let $T$ denote the set of possibilities to place the rooks on the board in such a way that none of them attacks another.
For $L\in\{A,B,C,D,E,F,G,H\}$ let $L$ denote the subset of possibilities characterized by a rook on diagonal $A1-H8$ in row $L$.
Then to be found is:$$|A^{\complement}\cap\cdots\cap H^{\complement}|=|T|-|A\cup\cdots\cup H|=8!-|A\cup\cdots\cup H|$$
Then inclusion/exclusion and symmetry come in and the cardinality of an intersection of $k$ distinct elements from $\{A,B,C,D,E,F,G,H\}$ is $(8-k)!$.
This leads to:$$8!-|A\cup\cdots\cup H|=\sum_{k=0}^{8}\left(-1\right)^{k}\binom{8}{k}\left(8-k\right)!=14833$$possibilities.