3

How many ways to put 8 rooks on the chessboard which satisfy that there is no rook can attack the others rook, and there is no rook place in : 1) One main diagonal. 2) Bot Two main diagonal

My result : 1) One main diagonal The problems is similar to count how many permutation of $(1;2;3;4;5;6;7;8)$ such that $x_i \neq i$ for $i=1$ to $8$

My answere is $8!-\sum_1^8 C_8^i.(8-i)!(-1)^{i+1}=8!-\sum_1^8\frac{8!}{i!}(-1)^{i+1}$ $=14833$ It 's quite right

2) But for the 2 main diagonal: The problems is similar to count how many permutation of $(1;2;3;4;5;6;7;8)$ such that $x_i \neq i$ and $x_i \neq 9-i$ for $i=1$ to $8$

I find the answer that : $8!-\sum_1^8 2^iC_8^i.(8-i)!(-1)^{i+1}=8!-\sum_1^8\frac{2^i.8!}{i!}(-1)^{i+1}$ $=5504$

And i know it 's wrong. Can anyone hefp me, sorry about my bad english

Haruboy15
  • 990

1 Answers1

1

Both problems may be solved using the inclusion-exclusion principle, as the poster has already done for part 1.

Let me first generalise from an $8\times 8$ board to an $2m\times 2m$ board since this can be done without adding any complications.

To summarise the inclusion-exclusion principle, let's consider all $(2m)!$ placements of rooks so that no two are in the same row or column. We'll then consider rooks in illegal positions: (1) on the main diagonal, or (2) on either of the diagonals.

Let $A_k$ be the number of ways to pick one of the $(2m)!$ initial placements and $k$ illegally placed rooks from the placement. Then, the number of placements with no illegally placed rooks is $$\sum_{k=0}^{2m} (-1)^k A_k$$ by the inclusion-exclusion principle. Basically, this holds because any placement without any illegally placed rooks contributes one to the right-hand sum, while any placement with $r>0$ illegally placed rooks contributes $\sum_{k=0}^r (-1)^k\binom{r}{k}=0$.

For case (1) in which illegal rooks are those on the main diagonal, we can select $k$ rooks on the main diagonal in $\binom{2m}{k}$ different ways, and the remaining $2m-k$ rooks in $(2m-k)!$ different ways, which gives us $$ \sum_{k=0}^{2m} (-1)^k\binom{2m}{k}\cdot(2m-k)! =\sum_{k=0}^{2m} (-1)^k\frac{(2m)!}{k!} $$ different placements of the rooks in legal positions, as already found by the poster.

For case (2), we again select $k$ rooks in illegal positions: i.e. on either of the diagonals. However, having both diagonals illegal introduces a kind of dependency between row $i$ and row $2m+1-i$. Consider all $m$ pairs of rows $\{i,2m+1-i\}$ for $i=1,\ldots,m$. I'll group the $k$ illegal rooks by these $m$ pairs to deal with this dependency.

Given $k$ rooks in illegal positions, let $q$ be the number of these that form pairs $\{i,2m+1-i\}$, and $p=k-2q$ the remaining singleton rooks. From the $m$ row-pairs, we can pick the $q$ pairs with both rooks illegal and $p$ pairs with one of the rooks illegal in $\binom{m}{p,q,m-p-q}=m!/p!q!(m-p-q)!$ different ways.

For each of the $q$ illegal pairs, the corresponding rook positions can be chosen in 2 different ways: on the main diagonal, or on the other diagonal. For each of the $p$ pairs with one illegal rook, there are 4 alternatives: which row the illegal rook is in, and which diagonal it is on. Thus, the number of way to select $k=p+2q$ illegal rooks with $q$ pairs and $p$ singles is $\binom{m}{p,q,m-p-q}\cdot 4^p\cdot 2^q$.

Once we have selected these $k=p+2q$ illegal rooks, for counting $A_k$ we allow the remaining $2m-k$ rooks to be places anywhere (still no two on the same row or column), which can be done in $(2m-k)!$ different ways. So, the number of placements with no illegal rooks becomes $$ \sum_{p+q\le m}(-1)^{p+2q}\binom{m}{p,q,m-p-q}\cdot 4^p\cdot 2^q\cdot(2m-p-2q)! $$ which simplifies to $$ \sum_{p+q\le m}(-1)^p\frac{m!\,(2m-p-2q)!}{p!\,q!\,(m-p-q)!}\cdot 2^{2p+q}. $$

Plugging in $m=4$ gives the sum $4752$.