In how many different ways can we place N identical rooks on a chess board WITHOUT CORNERS so that no two of them attack each other (for N > 3)?

Question

I'm trying, unsuccessfully, to figure it out for a moment now

For N = 8, the chessboard would look like:

Just for reference here is a similar question without the corner restriction and with N = 8 : In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other?

Answer 1

The first observation is that there is exactly one rook on each row. So let us count the number of ways to place rooks on the first and last row. There are $N-2$ squares to choose from and once we place the first rook it takes away exactly one option for the placement of the second rook so there are $(N-2)(N-3)$ choices. Now delete the rows and columns these rooks occupy and we are left to place $N-2$ rooks on a square board of size $N-2$. There are $(N-2)!$ ways to do this (argue this by placing rooks row by row). So in total there are $(N-2)(N-3)[(N-2)!]$ ways to place the rooks.

When N=8, this gives 6*5*(6!) = 21600 ways.

Answer 2

Let $A_{(x,y)}$ be the number of placements of $N$ rooks on an $M\times M$ chessboard with a rook in square $(x,y)$ then we want to count rook placements that belong to none of $A_{(1,1)}$, $A_{(1,M)}$, $A_{(M,1)}$ or $A_{(M,M)}$ so we can use $\xi$ to represent the set of all placements of $N$ rooks on our $M\times M$ board then

$$|\xi|= \binom{M}{N}^2N!$$

because we choose $N$ rows from $M$ in which to place our rooks in $\binom{M}{N}$ then make an ordered selection of $N$ columns from $M$ in $\binom{M}{N}N!$ ways.

Next we have

$$|A_{(x,y)}|=\binom{M-1}{N-1}^2(N-1)!$$

by the same argument, only this time we have placed a rook in cell $(x,y)$ which leaves $M-1$ rows and columns in which to place the remaining $N-1$ rooks. There are $4$ such sets, one for each corner of the $M\times M$ board.

Then we have

$$|A_{(x_1,y_1)}\cap A_{(x_2,y_2)}|=\begin{cases}& 0\qquad &x_1= x_2,\, \text{or}\, y_1= y_2\\& \dbinom{M-2}{N-2}^2(N-2)!\qquad &\text{else}\end{cases}$$

Since there are only $2$ non-zero intersections $A_{(1,1)}\cap A_{(M,M)}$ and $A_{(1,M)}\cap A_{(M,1)}$ and there can be no $3$-intersections then we have by the principle of inclusion-exclusion

$$\begin{align}\text{Desired count}&=|\xi|-(|A_{(1,1)}|+|A_{(1,M)}|+|A_{(M,1)}|+|A_{(M,M)}|) + (|A_{(1,1)}\cap A_{(M,M)}|+|A_{(1,M)}\cap A_{(M,1)}|)\\ &=\binom{M}{N}^2N!-4\binom{M-1}{N-1}^2(N-1)!+2\binom{M-2}{N-2}^2(N-2)!\end{align}$$

As required.

It is also possible to use rook polynomials for this but is perhaps unknown to many hence the above approach.