0
$\begingroup$

[Barbeau, Polynomials, page 8]

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

enter image description here

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)$ )

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – user3203476 Dec 16 '18 at 6:36
0
$\begingroup$

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.

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