3
$\begingroup$

We're presented with the following chessboard, and we aim to determine the number of arrangements in which 6 rooks can be placed without threatening each other. It's crucial to note that rooks cannot be placed on squares of the hashed squares. How many such arrangements are possible?

enter image description here

I'm trying to determine the coefficient of $x^6$ in the rook polynomial. However, solving it directly seems overly complex. I attempted to apply the inclusion-exclusion principle, but unfortunately, my efforts were unsuccessful

$\endgroup$
2
  • $\begingroup$ Are rooks considered to attack each other if the line of attack would be over one or more hashed squares (regardless of whether it's also over at least one that isn't hashed)? $\endgroup$
    – J.G.
    Feb 22 at 8:40
  • $\begingroup$ yes they attack each other when they are in a same row or column . they can attack each other over an hashed square too. $\endgroup$
    – Ariana
    Feb 22 at 8:51

2 Answers 2

3
$\begingroup$

There are $6!$ ways to arrange rooks so that none beat each other. But we must subtract the number of arrangements where rooks take prohibited spots. Using inclusion-exclusion I got the following expression:

$$6!-8*5!+(6+5+4+3+3+1)*4!-(11+7+4+1+1)*3!+(3+2+1+2+1)*2!-1.$$

The number of arrangements where $k$ rooks take the prohibited squares can be calculated manually, looking at the picture. So the answer is $$161.$$

$\endgroup$
6
  • $\begingroup$ Why $7*5!$? According to test answer must be in $[160,200)$ $\endgroup$
    – Ariana
    Feb 22 at 11:01
  • $\begingroup$ Can you explain more how did you count prohibited ones with inclusion exclusion? $\endgroup$
    – Ariana
    Feb 22 at 11:04
  • 1
    $\begingroup$ There are $8$ prohibited squares, so $8$ arrangements where a rook is on a prohibited square, the rest $5$ rooks are arranged in $5!$ ways. Then we calculate the number of arrangements where a pair of rooks that don’t beat each other take the prohibited spots. Assume the first rook is in the left top square, then the second rook can take $6$ squares. If the first rook is one square to the right, $5$ squares for the second rook are left. And so on. Rather tedious process $\endgroup$
    – Aig
    Feb 22 at 11:14
  • $\begingroup$ shouldn't answer be 167? $\endgroup$
    – Ariana
    Feb 22 at 14:20
  • $\begingroup$ Well, the other answer and the online rook calculator give $161$, too. $\endgroup$
    – Aig
    Feb 22 at 14:23
3
$\begingroup$

There is a standard result for rook polynomials with restricted squares, see for example Rook Polynomials for Chessboards of Two and Three Dimensions. If $R(B)=\sum{r_k(B)x^k}$ is a rook polynomial for a set of forbidden squares $B$, then the total number of arrangements of $n$ rooks is given by inclusion-exclusion as $$ n!-r_1(B)(n-1)!+r_2(B)(n-2)!+\dots+(-1)^nr_n(B)0!. $$

To compute $R(B)$ you can decompose $B$ into disjoint regions - sets that do not share a row or column. In your example you have a clear choice of the upper-left and lower-right regions $B_1$ and $B_2$, respectively, then you can compute by hand that $R(B_1)=1+5x+6x^2+x^3$ and $R(B_2)=1+3x+x^2$. So you have $$ R(B)=(1+5x+6x^2+x^3)(1+3x+x^2)=1+8x+22x^2+24x^3+9x^4+x^5. $$ The total number of arrangements is then $$ 6!-8\cdot 5!+22\cdot 4!-24\cdot 3!+9\cdot 2!-1\cdot 1!=161. $$

For more details, see the linked paper. You might also want to check this rook polynomial calculator.

Note: On a generic board, swapping any two rows or columns can be helpful in finding disjoint regions, since swapping does not change the original problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .