0
$\begingroup$

I have this example from a discrete mathematics book and I can not understand the principle by which the chessboard in the example is being divided to smaller parts. The image is attached.

By reading the text before the example on "Rook Polynomials", I expected to see the chessboard will be divided to disjoint parts. It turns out I am wrong. For example, in the first attempt, it divides the original chessboard to one with a 2squares column at left and a 3squares column at right, with a star on top-most cell of the right column. When this new chessboard is recursively divided, I expect that it gets divided to its 2 columns and they would be disjoints. But it seems that it omits that cell with star, and keeps 1 column of 2 cells and a 4-cell square. I can not understand the division principle at all! Please explain.

Rook Polynomial example

$\endgroup$
3
$\begingroup$

It has nothing to do with dividing the chessboard. It's counting the number of ways to put non-attacking rooks on the chessboard. Either you put a rook in the starred cell, in which case you can't put another rook in that row of column, or you don't put a rook in that cell, in which case any rooks must go in the other cells. In the first case, where we place a rook in the cell, we multiply by $x$ to account for that rook.

What may be confusing you is that the starred cell is not the same from one step to the next; it just indicates which cell will be used for expansion at the next step. Indeed, the starred cell is always removed in both cases.

EDIT

Reading your comments, I suspect you have gotten hold of the idea that we are dividing the board into two pieces; this is not the case. As I tried to indicate above, we are just considering the cases of putting a rook in the starred cell, or not putting a rook there.

Let me try to explain with an $3\times3$ chessboard as an example. I claim that the rooks polynomial is $$1+9x+18x^2+6x^3.$$ There is only way way to place $0$ rooks on the board. Clearly we can place one rook in any of the $9$ cells. For two rooks, we can place the first rook in $9$ ways. This will strike out one row and one column, so we'll be left with a $2\times2$ chessboard on which to place the second rook, though it may be in more than one piece. That gives $4$ ways to place the second rook, but the the order doesn't matter, and we have to divide by $2$. Finally, there are clearly $3!$ ways to place $3$ rooks.

To construct this with the method given in the text, we pick any cell, say the upper left-hand corner. There are two cases: place a rook in that cell or don't. In the first case, any remaining rooks we place will have to be in the $2\times2$ board in the lower right-hand corner. The rook polynomial of the smaller chessboard is $$1+4x+2x^2,$$ by simply counting the possibilities. We multiply it by $x$ to get $$x+4x^2+2x^3.$$ The significance of this is that there are:

  • $0$ ways to place no rooks on the board if we place a rook in the upper left-hand corner;
  • $1$ way to place $1$ rook on the board if we place a rook in the upper left-hand corner;
  • $4$ ways to place $2$ rooks on the board if we place a rook in the upper left-hand corner;
  • $2$ ways to place $3$ rooks on the board if we place a rook in the upper left-hand corner.

We have multiplied by $x$ because on the $3\times3$ board there will be one more rook than there is on the $2\times2$ board, namely the rook in the upper left-hand corner.

We still have to account for the case where we don't place a rook in the upper-left hand corner. That is, we have to add in the rook polynomial for the board with the upper left-hand cell removed. It's tedious to try to describe the process with no way of drawing pictures, but I imagine you can go on from here. See if you can finish the computation. If you still have questions, let me know, and I'll try to explain further.

$\endgroup$
  • $\begingroup$ @higraphs Any way you divide the board will give the same rook polynomial. I need to think for a bit about how best to explain this. I find Grimaldi to be an excellent textbook, and in the meantime, I suggest you read his explanation again. Sometimes you have to read math several times before it sinks in. $\endgroup$ – saulspatz Apr 21 at 0:57
  • $\begingroup$ Thank you very much for this detail answer! I do as you instructed and post my results back here. Thank you again. $\endgroup$ – higraphs Apr 21 at 2:38
  • $\begingroup$ @higraphs It was my pleasure. $\endgroup$ – saulspatz Apr 21 at 3:17
  • $\begingroup$ @ Saulspatz, After a day of back and forth between your answer and Grimaldi's text book, I could finally solve Grimaldi's example on my own, which was impossible without your help! I also deleted my unrelated comments so the future reader of this post will not waste time. Thank you again for helping me! $\endgroup$ – higraphs Apr 21 at 23:31

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.