Two rooks shall attack each other on a chess board

Question

Assume you have 8 undistinguishable rooks. How many ways are there to place the 8 rooks on the board so that at least two rooks can attack each other?

My approach so far:

$\frac{64*14}{2}* {62 \choose 6}$. But if I compare this with the total number of all possible positions ${64 \choose 8}$ my approach seems wrong.

Any ideas where my mistake is?

Answer 1

8 is getting big, but I think you can evaluate the problem for a 3x3 with 3 rooks.

Options are to count the number of ways that work, which appears to be your approach or count the number of ways that don't work.

I make a logical leap as to the derivation of your formula in that it should be: Pick an arbitrary square then pick the squares that would ensure an attack. Finally we don't care about the rest so: $$ \frac{n^2 2(n-1)}{2}\binom{n^2-2}{n-2}$$ For $n=3$ we get 126 ways from this, but there are $\binom{9}{2}=36$ possible states! What happened?

Well let's start working out the different states. Start with something that should work: (1,1);(1,2);(3,3)

Now on to the error: (1,1);(1,2);(1,3) We are double counting here since we will visit the (1,1);(1,3);(1,2) state without realizing we already counted it.

The resolution isn't as simple as a factor since we double count some states, but not others.

If we want to continue down this vein we would need to figure out number of states with exactly 2, then exactly 3, etc. For larger $n$ this seems to be much more difficult than simply counting that number of states where no two rooks attack and subtracting that from the total. This path leads us to realize that there can only be one rook per row/column and thus the rook in the first row has $n$ spots it can take up without attacking another. The next will have $n-1$ etc giving $\binom{n^2}{n}-n!$

For exactly two rooks attacking it's $n^2 (n-1) \binom{n^2-3n+2}{n-2}$

Answer 2

If I understood correctly your approach:

1. You take two rooks. You allow first one to stand anywhere ($64$ places)
2. You restrict the second one to stand either on the same vertical or row ($14$ places)
3. You account that you calculate the configurations of rooks twice ($64\times14/2)$
4. You allow for all other 6 rooks to take any of $62$ places left ($\times {62 \choose 6}$).

However, the problem of this method is that since you distinguish between 2 first rooks and 6 rest rooks, you count a lot of positions more than once. For example, position (A1,A2,A3,A4,A5...) is the same as (A3,A4,A1,A2,A5...).

The only viable solution is to calculate positions when no rook attack another rook and to subtract this number from the total possible placements.

Notice, that when no rook is attacking other rook, they occupy all 8 rows. Thus, this position can be uniquely defined as 8 numbers $(a_1,a_2,\ldots)$ where $a_i$ is the position of rook in $i$-th row. All these numbers should be different (otherwise, two rooks are in the same vertical). Thus we need to calculate the number of permutations of 8 elements, which is $8!$. Finally the answer is ${64\choose8} - 8!$