# k non-attacking rooks on a chessboard with forbidden positions

[Barbeau, Polynomials, page 8]

I am trying to understand the equation shaded in the extract below:

Unfortunately the wikipedia entry only has complete boards (all squares allowed)

Now for some handwavy thinking on that equation shaded:

1- if S becomes forbidden, then we have chessboard $$C_1$$ by definition, and the polynomial for that is $$R(C_1,t)$$ , also by definition.

2- if S is allowed, then let us put a rook on it. This means the corresponding row and column becomes off-limits for the remaining rooks (since they must be non-attacking) , effectively giving the reduced $$(m-1)(n-1)$$ chessboard $$C_2$$ on which we have 1 fewer rook to place. The polynomial for chessboard $$C_2$$ with the reduced number of rooks is $$R(C_2,t)$$ by definition.

3- The polynomial $$tR(C_2,t)$$ then corresponds to a $$mn$$ chessboard for which the entire row and column of S is shaded (?)

At this point, I am not so sure:

• about that last statement (3)

• even so, why the two chessboards $$C_1$$ and $$C_2$$ are in distinct union to chessboard $$C$$ (resp. why the 2 polynomials $$tR(C_2,t)$$ and $$R(C_1,t)$$ add up to $$R(C,t)$$ )

• Thinking about this further, i think it is best to initially ignore the polynomial aspect of the question, think in terms of a recurrence relation, in the way this previous question does, and deduce the polynomial relation therefrom : math.stackexchange.com/questions/708523/… – user3203476 Dec 16 '18 at 6:36

## 1 Answer

1- if S becomes forbidden, ...

2- if S is allowed, then let us put a rook on it. ...

IMO this is thinking about it backwards. The forwards reasoning is: either we put a rook on it (and then we delete the row and column because that's easier than forbidding all the squares in the row and column) or we don't put a rook on it (and we mark it as forbidden to ensure that we don't undo that decision later).

Otherwise, points 1 and 2 look fine to me.

3- The polynomial $$tR(C_2,t)$$ then corresponds to a $$mn$$ chessboard for which the entire row and column of S is shaded (?)

At this point, I am not so sure:

about that last statement (3)

I don't even know what you mean by statement (3). What does "shaded" mean?

I would replace statement (3) with

3b - the polynomial $$tR(C_2, t)$$ then gives the polynomial for the chessboard $$C$$ when there is a rook on S.

The key observation is that you multiply the expression from point (2) by $$t$$ as a way of counting the rook.

even so, why the two chessboards C1 and C2 are in distinct union to chessboard C (resp. why the 2 polynomials tR(C2,t) and R(C1,t) add up to R(C,t) )

Because either there is a rook on S or there isn't. The two options are exclusive and exhaustive.