1
$\begingroup$

I realize this is a fairly basic combinatorial problem, but I'm still confused.

In how many was can 2 black and 2 white rooks be placed on a standard chessboard such that white and black don't attack each other.

The way I saw it first, there are 2 cases:

Case 1. Both white are on the same row/column. In this case there are $ \frac{64 \times 15}{2} \times \binom{49}{2}$ ways of allocating these pieces.

Case 2. Both white are on different rows and columns. In this case there are $\frac{64 \times 49}{2} \times \binom{34}{2}$

Hence the solution is the sum of Case 1 and Case 2. After some deliberation, I realized that this is probably wrong because the order in which the pieces are placed on the board matter, e.g. WBWB is different to WWBB.

So I came up with a different idea, to use inclusion-exclusion theorem.

First, we find 4 squares: $\binom{64}{4}$ for all pieces, then we have 4 cases: 1w/1b attack each other, 2w/1b attack each other, 1b/2w attack each other and 2w/2b attack each other, but as I started analyzing them, I got stuck (e.g. case 1 depends on the distance between rooks), and not sure this is the correct approach either.

Any suggestions?

$\endgroup$
2
$\begingroup$

I'm copying your own solution:

There are 2 cases:

Case 1. Both white rooks are on the same row/column. In this case there are $ \frac{64 \cdot 14}{2} \cdot \binom{42}{2}$ ways of allocating the four pieces.

Proof. The first white rook may be placed on $64$ squares. Then there are $14$ squares for the second white rook. Since the two white rooks are indistinguishable we have to divide $64\cdot14$ by $2$. Now $2$ rows and $1$ column (or vice versa) are forbidden for the black rooks. There remain $6\cdot7$ allowed squares, and we can freely choose $2$ of them.

Case 2. Both white rooks are on different rows and columns. In this case there are $\frac{64 \cdot 49}{2} \cdot \binom{36}{2}$ ways of allocating the four pieces.

Proof. Essentially the same as in case 1.

$\endgroup$
  • $\begingroup$ (I may be mistaken, but I believe you want 14 instead of 15 in the numerator for case 1.) $\endgroup$ – user84413 Apr 2 '16 at 17:23
  • $\begingroup$ @user84413: Thank you for noticing the slip! $\endgroup$ – Christian Blatter Apr 2 '16 at 17:30
2
$\begingroup$

Here is an alternate, slightly more complicated, solution:

$\textbf{1)}$ If none of the rooks attack each other, there are $\displaystyle\binom{8}{4}\binom{8}{4}\big(4!\big)\binom{4}{2}=\color{blue}{705,600}$ possibilities:

$\hspace{.4 in}\binom{8}{4}$ ways to choose their columns, $\binom{8}{4}$ ways to choose their rows,

$\hspace{.4 in}4!$ ways to place them in this $4\times4$ array, and $\binom{4}{2}$ ways to choose the rooks which are black

$\textbf{2)}$ If only 1 pair of rooks attack each other, there are $\displaystyle16\binom{8}{2}\binom{7}{2}\binom{6}{2}\big(2!\big)\binom{2}{1}=\color{blue}{564,480}$ choices:

$\hspace{.4 in}$ 16 ways to choose the row (or column) for this pair, $\binom{8}{2}$ ways to choose their columns (or rows),

$\hspace{.4 in}\binom{7}{2}$ ways to choose the rows (or columns) for the other two rooks, $\binom{6}{2}$ ways to choose their columns

$\hspace{.4 in}$(or rows), $2!$ ways to place them in this $2\times2$ array, and $\binom{2}{1}$ ways to choose the color for the first pair

$\textbf{3)}$ If two pairs of rooks attack each other, there are $\displaystyle16\binom{8}{2}\left[7\binom{6}{2}+6\binom{7}{2}\right]=\color{blue}{103,488}$ possibilities:

$\hspace{.4 in}$ 16 ways to choose the row (or column) for the black pair, $\binom{8}{2}$ ways to choose their columns (or rows),

$\hspace{.4 in}$ 7 ways to choose the row (or 6 ways to choose the column) for the white pair, and then

$\hspace{.4 in}\binom{6}{2}$ ways to choose their columns (or $\binom{7}{2}$ ways to choose their rows).

This gives a total of $\color{blue}{1,373,568}$ possibilities.

$\endgroup$
  • $\begingroup$ good solution, but I've already accepted a different one $\endgroup$ – Alex Apr 3 '16 at 11:57
  • $\begingroup$ @Alex Thanks for your comment, and the solution you accepted is simpler and shorter. $\endgroup$ – user84413 Apr 3 '16 at 20:14

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.