0
$\begingroup$

I’m given a m×n grid-like board and there are some shaded squares in every row of the board. I have to place one or more rooks on the shaded squares in such a way that no two rooks attack each other.

For example, I’m given the following board. I have to find out the number of ways to place one or more rooks on the shaded squares of the board.

enter image description here

By looking at the above figure we can easily find out the number of ways to place one rook in the board. If we denote rk as the number of ways to place k rooks in the board then the value of r1 will be 9.

Similarly, r2=28, r3=35 .

Now my question is that how will I find out the value of r2,r3,………………,rk etc. Is there any way ? If so, please mention the way with better explanation.

$\endgroup$
  • 1
    $\begingroup$ (On the given board)You can't place more than 5 rooks. At most one rook can be placed in each row. So you need to calculate $r_4$ and $r_5$. Its easy to see that $r_5 = 2$. To find $r_4$, first fix the $4$ rows on which the rooks are to be placed, which can be done in $\binom{5}{4}=5$ ways. Once the rows are fixed, try to compute the number of rook arrangements on those rows. For instance if you fix the first 4 rows, then there are 3 ways to place 4 rooks:{S1, K2, W3, F4},{S1,D2,K3,F4},{S1,D2,W3,F4}. This needs to be done for each set of four rows. $\endgroup$ – user183763 Nov 27 '14 at 7:30
1
$\begingroup$

What you are trying to find is Rook Polynomial of that board. Using your notation, the polynomial is denoted $$ R(x) = r_0 + r_1 x + r_2 x^2 + r_3 x^3 + \dotsc $$ This specific board that you proposed is not so big so it still feasible to find directly the coefficients by systematical counting. As $r_k$ is the number of ways to place $k$ rooks on the allowed cells without any conflict, we always have $r_0 = 1$ and $r_1$ as the number of allowed squares, in this case, $r_1 = 9$.


To find $r_2$, you must first place one rook in one of the cells and then place the second on a allowable position.

  • First Rook on S1, 7 options for Second Rook
  • First Rook on K2, 6 options for Second Rook
  • First Rook on D2, 6 options for Second Rook
  • First Rook on K3, 6 options for Second Rook
  • First Rook on W3, 6 options for Second Rook
  • First Rook on F4, 7 options for Second Rook
  • First Rook on S4, 6 options for Second Rook
  • First Rook on D5, 6 options for Second Rook
  • First Rook on W5, 6 options for Second Rook
  • Total: $7\cdot 6 + 2 \cdot 7 = 56$

So there are 56 ways to place two rooks, but they order shoudn't matter, hence we have to divide it by $2!$. Now we get $r_2 = 28$.


We can obtain $r_3$ on a similar fashion, altough we have to look at a lot of cases. What you can do to make it slightly faster, is to consider only configurations that you haven't counted already, so when we place the First Rook on K2, we won't put any of them on the S1 position.

  • First Rook on S1
    • Second Rook on K2, 4 options for Third Rook
    • Second Rook on D2, 4 options for Third Rook
    • Second Rook on K3, 3 options for Third Rook
    • Second Rook on W3, 2 options for Third Rook
    • Second Rook on F4, 2 options for Third Rook
  • First Rook on K2
    • Second Rook on W3, 3 options for Third Rook
    • Second Rook on F4, 2 options for Third Rook
    • Second Rook on S4, 2 options for Third Rook
  • First Rook on D2
    • Second Rook on K3, 3 options for Third Rook
    • Second Rook on W3, 2 options for Third Rook
    • Second Rook on F4, 1 option for Third Rook
    • Second Rook on S4, 1 option for Third Rook
  • First Rook on K3
    • Second Rook on F4, 2 options for Third Rook
    • Second Rook on S4, 2 options for Third Rook
  • First Rook on W3
    • Second Rook on F4, 1 option for Third Rook
    • Second Rook on S4, 1 option for Third Rook
  • First Rook on F4 and further, no options as there are 2 rows.
  • Total: $4 + 4 + 3 + 2 + 2 + 3 + 2 + 2 + 3 + 2 + 1 + 1 + 2 + 2 + 1 + 1 = 35$

    We have already taken care of permutations, hence $r_3 = 35$.


For $r_4$, similarly:

  • First Rook on S1,
    • Second Rook on K2
    • Third Rook on W3, 2 options for Fourth Rook
    • Third Rook on F4, 2 options for Fourth Rook
    • Second Rook on D2
    • Third Rook on K3, 2 options for Fourth Rook
    • Third Rook on W3, 1 option for Fourth Rook
    • Third Rook on F4, 1 option for Fourth Rook
    • Second Rook on K3
    • Third Rook on F4, 2 options for Fourth Rook
    • Second Rook on W3
    • Third Rook on F4, 1 option for Fourth Rook
  • First Rook on K2
    • Second Rook on W3
    • Third Rook on F4, 1 option for Fourth Rook
    • Third Rook on S4, 1 option for Fourth Rook
  • First Rook on D2
    • Second Rook on K3
    • Third Rook on F4, 1 option for Fourth Rook
    • Third Rook on S4, 1 option for Fourth Rook
  • Total: $2 + 2 + 2 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1 = 15$.

    Therefore $r_4 = 15$.


And finally, for $r_5$, we have to use all rows and columns. Hence S1 have to be chosen, implying that F4 also has to be chosen. If K2 is chosen, then we have W3 and D5. If D2 is chosen, then W5 and K3 are chosen. Hence we have only two options, that is, $r_5 = 2$.

Finally, we have the rook polynomial: $$ R(x) = 1 + 9x + 28x^2 + 35x^3 + 15x^4 + 2x^5$$

$\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.