2
$\begingroup$

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

For N = 8, the chessboard would look like:

cornerless_chessboard

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?

$\endgroup$
  • $\begingroup$ Just to check: Does there have to be $N$ rooks on an $N\times N$ chessboard with corners removed or $N$ rooks on an $M\times M$ chessboard with corners removes (where $0\le N\le M$ for $N,M\in \mathbb{N}$)? I am leaning towards the former but the latter is more interesting. $\endgroup$ – N. Shales Mar 24 '17 at 14:37
  • $\begingroup$ Well, if you manage so solve for the latter you will, necessarily, solve the former. So feel free to solve it in any ways. $\endgroup$ – Daniel M Mar 24 '17 at 14:44
  • $\begingroup$ Well, I believe a general solution counting $N$ rooks on a $M\times M$ chessboard with corners removed is $$\binom{M}{N}^2N!-4\binom{M-1}{N-1}^2(N-1)!+2\binom{M-2}{N-2}^2(N-2)!$$ but I will double check and post a full answer when I have a little more time. $\endgroup$ – N. Shales Mar 24 '17 at 14:53
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you manage to solve this in another way, using area instead of rows? $\endgroup$ – Daniel M Mar 24 '17 at 14:39
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

This problem can be conveniently solved using rook polynomials. We can pairwise exchange rows and columns without changing the number of possible arrangements of non-attacking rooks. An equivalent board is shown below.

                                                                enter image description here

The rook polynomial of the four forbidden squares in the top left corner is \begin{align*} 1+4x+2x^2\tag{1} \end{align*} where the coefficient of $x^k$ gives the number of ways to place $k$ non-attacking rooks on the forbidden squares. The number of valid arrangements to place eight non-attacking rooks on the $(8\times 8)$ board respecting the forbidden squares is given by (1) using the inclusion-exclusion principle as \begin{align*} 1\cdot 8!-4\cdot 7!+2\cdot 6!\color{blue}{=21\,600} \end{align*} We can place eight non-attacking rooks in $8!$ ways, subtract $4\cdot7!$ ways having at least one rook on one of the four forbidden squares and add as compensation for double counting $2\cdot6!$ ways having two non-attacking rooks on the four forbidden squares.

| cite | improve this answer | |
$\endgroup$

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.