Let's assume we put 8 rooks on a chess board but we are not allowed to place them on the main diagonal with the white squares. In how many ways can I arrange them so that they cannot attack each other.
My approach is:
You can put the first rook in 8 different rows of the chess board and you can combine them with 7 columns. The second rook can be placed in 7 different rows and you can choose out of 6 columns and so on. This leads to $8!7!$ different possibilities. You then have to eliminate $8!$-many possibilities as the rooks are not distinguishable. So I get $7!$ possibilities.
I think this must be wrong although the reasoning seems legit to me?!
Where is my mistake?
Best Answer
The flaw in the reasoning is because you write "the second rook can be placed in $7$ different rows and you can choose $6$ different columns and so on" which is not actually correct - and should stand out as a red flag because no justification is given to a pretty non-obvious and important fact in your argument. Also, your "and so on" hides what happens to the last rook in your argument, which you would say can be put into $1$ row and $0$ columns - which is clearly wrong!
Suppose we put the coordinates on the grid ranging from $(1,1)$ to $(8,8)$ where the diagonal in question is those points of the form $(n,n)$. If you put the first rook at $(1,2)$, your claim is that there are $42$ valid positions for the second rook - but this is not so! More specifically, you claim that we can fix the first coordinate in $7$ ways and then will have $6$ choices for the second coordinate - but this does not hold. In particular, if we choose the first coordinate for the second rook to be $2$, we find that all positions $(2,x)$ are legal except for $(2,2)$ - which is both attacked by the the first rook and on the main diagonal. Oops - so there are actually $43$ valid positions for the second rook!
Patching this argument turns out to be really hard because the number of valid positions for the next rook will, in general, depend on the placement of the previous rooks - so finding another approach is warranted. (For instance, one can count the number of arrangements of rooks that do include the diagonal and also the total number of arrangements of rooks, then subtract. It's also to get a recurrence relation by considering that each square on the diagonal is attacked by two rooks - which then means you have some sort of relation on the rooks which is useful to counting the number of possible placements)