the number of ways in which you can place $m*n$ kings on only the white coloured squares

Question

The number of ways in which you can place $m*n$ kings on only the white coloured squares on a $2m*2n$ chessboard such that no two kings are diagonally adjacent to each other?

My approach: I noticed that if I divide the chessboard into $m*n$,$2*2$ blocks from top left, then each block must contain 1 king.Now since we can only place the kings on the white coloured squares, there two white coloured squares in each 2*2 block, top left and bottom right. Now let us number each block as (i,j) which represents the $i^{th}$ from top and $j^{th}$ block from the right. Then let us consider that i place each king till the (a,b) block at top left and then i place the first king at bottom right on the (a,b) block, then using an inductive argument i can show that for all blocks having $i\geq a$ and $j\geq b$ the king has to be at bottom right.

This gives me the final answer as $m*n$+1 ways since we have choose 1 block out of m*n blocks to have the first occurrence of king on bottom right and 1 case for no occurrence.

I found this to be incorrect, please help me with where i have gone wrong.

Answer 1

Hint

As you noticed, every $2\times 2$ block has a king, in either the lower left or the upper right. Let us label a block "A" if the king is in the upper left, and label the block "B" if the king is in the lower right.

You are correct that, if a block is labeled "B", then all blocks which are below and to the right of it must also be labeled "B." However, there are many more possible placements then the ones you discussed. For example, you could label blocks $(2,3)$ and $(3,2)$ to both be "B", together with all blocks to the right and below of either of them.

A A A
A A B
A B B

Try to think more generally about what the shape of the set of "B" blocks can look like. The set of "B" blocks has the property that whenever $(a,b)$ is included, then so is $(a+i,b+j)$, for all $i,j\ge 0$ such that $(a+i,b+j)$ is in the grid. How many subsets of the grid have this property? Draw all valid sets for small grids, like $2\times 2$, $2\times 3$, etc, and count the number of them, until you see a pattern.

Solution

I encourage you to try to solve this using the hint alone, but in case you get stuck, the solution is below (click to reveal).

A legal placement of kings is equivalent to a labeling of the $m\times n$ grid of blocks with "A" and "B", such that whenever a block is labelled "B", every block below is is labeled "B". A legal subset of "B" blocks is uniquely specified by the set of line segments between the "A" and "B" blocks. This set of line segments will always form a rectilinear path from the lower left corner of the grid to the upper right corner, and every such path determines a legal subset. The number of paths is $\binom{n+m}{n}$ (this is a well-known combinatorics problem; such a path has $m$ upward steps and $n$ rightward steps, so there are $\binom{m+n}n$ ways to place these in sequence). Therefore, there are $\binom{m+n}m$ ways to place the kings.