Rook Polynomials: A Straight-Forward Problem

Rook Polynomials: A Straight-Forward Problem

For an integer $k$, is it possible to place $k$ rooks on a chess board so that no piece sits on the same row or column as any others? We wouldn’t want them stepping on each others’ toes.

Tamsyn Morrill
Trine University

In the game of chess, each of the four rooks move along a row or a column, attacking the first piece they encounter. Chess can be complicated, so let’s ignore everything that isn’t a rook — the pawns, knights, bishops, king and queen, and even the players. How else could we set up the board?

You didn’t have to memorize so many opening moves before the invention of the pawn.

This is the $k$-rook problem: For an integer $k$, is it possible to place $k$ rooks on a chess board so that no piece sits on the same row or column as any others? We wouldn’t want them stepping on each others’ toes. Are there multiple solutions? How many?

There’s enough room for everybody.

We’ll begin our exploration on the ordinary $8 \times 8$ square board, using as many rooks of a single color as necessary. Thinking like a combinatorialist, the easiest case to reason through is not $k=1$, but actually $k=0$: When you attempt to place zero rooks on the chessboard, the job is done before you start. There is exactly one solution to the zero-rook problem.

Next, try to place a single rook on the chess board. There are sixty-four spaces on the board, so there are sixty-four distinct solutions to the one-rook problem.

Two rooks? Just start with a random one-rook board, then place a second rook. Since the first rook blocks out one row and one column, there will be forty-nine legal spaces for the second rook to occupy. Uh-oh, $64 \cdot 49$ would be an over-estimate! Swapping the position of the first and second rooks does not change the arrangement, so we need to divide out by the two different ways of permuting the rooks. The answer is that there are $64 \cdot 49 / 2$ different solutions to the two-rook problem. And $64 \cdot 49 \cdot 36 /6$ solutions to the three-rook problem.

There are $2!$ ways to get this arrangement, but it’s still just one solution.

If we keep at it, we’ll see that for $1 \leq k \leq 8$, there are exactly
$$
\frac{64 \cdot 49 \cdot \cdots \cdot (8 – k + 1)^2}{k!}
$$
solutions to the $k$-rook problem. Does this formula still work for larger values of $k$? Yes! Since there are only eight rows to work with, it is impossible to place nine or more non-attacking rooks on the standard chess board. In these cases, the numerator of our formula will include $(8-9+1)$, rendering the whole quantity equal to zero.

Let’s focus on the eight-rook problem for a moment. Our solution formula suggests there are $8!$ solutions. But why eight factorial? Well, every row and every column must be occupied by a rook. The first row rook can be placed on any of the eight columns. Then the second row rook can be placed on any of the seven remaining columns, and so on. So there are $8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 8!$ solutions.

Now find the other $40319$ solutions.

Let’s apply what we’ve learned to a more general problem. How many solutions are there to the rook problem on an $n \times m$ rectangular board? We’ll rotate any non-square boards so that there are more rows than columns. That is, we’ll assume $m \leq n$. (The rooks won’t be able to tell the difference anyway.) This means there will only be room for up to $m$ rooks before we run out of open columns.

On an $n \times 1$ board, with $n \geq 1$, there is one solution to the zero-rook problem, and $n$ different solutions to the one-rook problem. Easy enough.

On an $n \times 2$ board, with $n \geq 2$, there is one solution to the zero-rook problem, then $2n$ different solutions to the one-rook problem, and $n(n-1)$ solutions to the two-rook problem. Let’s put the data in a table before we forget. For each $k$, we’ll say that $r_k$ is the number of solutions to the $k$-rook problem on whatever board we are currently looking at. These are called the rook numbers of the board.

$k$ $0$ $1$ $2$
$r_k$ $1$ $2n$ $n(n-1)$

The rook numbers for an $n \times 3$ board with $n \geq 3$ are given in the next table.

$k$ $0$ $1$ $2$ $3$
$r_k$ $1$ $3n$ $3 \cdot 2\cdot n (n-1)$ $n(n-1)(n-2)$

Some products have shown up which resemble the binomial coefficient. Recall, the binomial coefficient $\binom{n}{k}$ counts the number of ways to choose $k$ objects from a set of $n$ objects, and it may be calculated as
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}.
$$
Let’s clean up a bit by using the falling factorial
$$
n^{\underline{k}} = n (n-1) \cdots (n-k+1),
$$
so that $n^{\underline{k}}$ is a product of $k$ terms starting at $n$ and stopping at $n-k+1$. Let’s say that $n^{\underline{0}} = 1$, just to keep the pattern consistent. It looks like the rook numbers for a general $n \times m$ board with $m \leq n$ should be $r_k = \binom{m}{k} n^{\underline{k}}$. Can we prove this? Yes!

Fix $0 \leq k \leq m \leq n$. We need $k$ columns to work on, and there are $\binom{m}{k}$ ways to choose those. Similarly, we need $k$ rows, and there are $\binom{n}{k}$ ways to choose those. Placing rooks on the intersections of these $k$ rows and $k$ columns is equivalent to solving the $k$-rook problem on a $k\times k$ square board. From our work on the $8\times 8$ board earlier, we know that there are $k!$ ways to place these rooks.

There are $\binom{5}{3}$ ways to choose three rows, $\binom{4}{3}$ ways to choose three columns, and $3!$ ways to arrange three rooks in the shaded sub-board.

All together, we have
$$
\binom{m}{k} \binom{n}{k} k! = \binom{m}{k} \frac{n!k!}{k!(n-k)!}=\binom{m}{k} n^{\underline{k}}
$$
solutions to the $k$-rook problem on this board. In fact, the $\binom{m}{k}$ term sets this formula to zero if we try to place more rooks than we have columns for. Fancy!

Could we make a more complicated board? Let’s start with an $n \times n$ square board and mark some of the spaces as being out of bounds. Whatever is left is the board $\mathcal{B}$. How do we find the rook numbers now?

Out of room.

Like before, there is always one solution to the zero-rook problem. Going further, the number of solutions to the one-rook problem will be equal to the number of spaces in bounds.

Just to keep things clear, we’ll decorate our rook numbers $r_k^\mathcal{B}$ with the letter $\mathcal{B}$ to indicate that the number of solutions to the $k$-rook problem depends on which board we have picked. This will be important when we work with more than one board at the same time. The $\mathcal{B}$ is not an exponent!

Now, it may be tempting to start a new table to hold these numbers. Before we get too carried away, I suggest we use a different data structure instead — a polynomial.

What, you don’t think we could store data in a polynomial? All we need is a safe place to write down the rook numbers $r_k^\mathcal{B}$ for later. We’ll write
$$
\begin{align}
R_\mathcal{B}(x)= r_0^\mathcal{B} + r_1^\mathcal{B} x + r_2^\mathcal{B} x^2 + \cdots \\ = \sum_{k=0}^n r_k^\mathcal{B} x^k.
\end{align}
$$
Because $\mathcal{B}$ only has room for at most $n$ rooks, this sum only goes up to $k=n$. This means each board $\mathcal{B}$ has a rook polynomial $R_\mathcal{B}(x)$, which we can use to explore relationships amongst the rook numbers $r_k^\mathcal{B}$.

Let’s see how this helps. Start with some non-empty board $\mathcal{B}$, and choose one of the squares. Any $k$-rook solution either places a rook on the chosen square, or it doesn’t. The solutions that don’t place a rook there correspond to $k$-rook solutions on the sub-board $\mathcal{B}_1$, which is $\mathcal{B}$ with the chosen square removed. The solutions that do place a rook on the chosen square correspond to $(k-1)$-rook solutions of the sub-board $\mathcal{B}_2$, which is $\mathcal{B}$ with both the row and column of the chosen square removed.

This three-rook solution corresponds to a three-rook solution on the shaded board $\mathcal{B}_1$.

 

This three-rook solution corresponds to a two-rook solution on the shaded board $\mathcal{B}_2$.

This means that $r_k^{\mathcal{B}} = r_k^{\mathcal{B}_1} + r_{k-1}^{{\mathcal{B}_2}}$. We can encode this relationship using the rook polynomials for all three boards, namely
$$
R_\mathcal{B}(x) = R_{\mathcal{B}_1}(x) + x R_{\mathcal{B}_2}(x).
$$
This can be a useful tool for calculating rook polynomials by hand. Just keep subdividing your boards into smaller pieces until you get to a board you know.

Let’s think a bit harder about what the subdivisions tell us.
We can gather information about the rook problem by methodically removing spaces from our board and trying to solve the rook problem again. But each of these boards are square board with spaces marked as out of bounds. Shouldn’t we be able to get the rook numbers for the in-bounds spaces by looking at the spaces which are are out of bounds?

A two-rook solution on $\overline{\mathcal{B}}$. What does this tell us about solutions to the board in Figure 6?

For a given board $\mathcal{B}$ cut out of an $n\times n$ square board, let’s take a look at the spaces which were removed. This is called the complement board, $\overline{\mathcal{B}}$.
The complement board has its own rook numbers, $r_k^{\overline{\mathcal{B}}}$, which have a fascinating relationship with the numbers $r_k^\mathcal{B}$:

$$
\sum_{k=0}^n r_k^\mathcal{B} (n-k)! x^ k = \sum_{k=0}^n (-1)^k r_k^{\overline{\mathcal{B}}} (n-k)! x^k (x+1)^{n-k}.
$$

This fascinating, non-obvious result is known as the Rook Reciprocity Theorem.
In short, the equation states that the rook numbers for $\mathcal{B}$ determine the rook numbers for $\overline{\mathcal{B}}$.
Notice that both sides of the equation are polynomials, meaning that expanding the sums and distributing the products will produce the same coefficients on either side of the equation. Sounds complicated.

Remember, though, that the polynomials are just a data structure to us. They are a means to an end. These particular polynomials are equal to each other, but it is the relationship between the rook numbers that we are after. So instead, we will consider a simpler statement of the Rook Reciprocity Theorem. Rather than write our polynomials with powers of $x$
$$
a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n,
$$
let’s use falling factorials, as in
$$
a_0 + a_1 x^{\underline{1}} + a_2 x^{\underline{2}} + \cdots + a_n x^{\underline{n}}.
$$
We never said that the falling factorial required integer valued inputs!
The same coefficients now produce a different polynomial, and hopefully one that is more accommodating to our problem. With a little sleight of hand, let’s consider rook polynomials like
$$
\tilde{R}_\mathcal{B}(x) = \sum_{k=0}^n r_k^\mathcal{B} x^{\underline{n-k}}.
$$
And here is the Rook Reciprocity Theorem stated in its more elegant form:
For any sub-board $\mathcal{B}$ of an $n\times n$ square board, we have
$$
\tilde{R}_{\mathcal{\overline{B}}}(x) = (-1)^n \tilde{R}_\mathcal{B}(-x-1).
$$
Brilliant.

Let’s walk through a proof for this result originally developed by Timothy Chow. Starting on the right-hand side, we have
$$
(-1)^n \tilde{R}_\mathcal{B}(-x-1) = (-1)^n \sum_{k=0}^n r_k^\mathcal{B} (-x-1)^{\underline{n-k}}
$$
When we distribute the $(-1)^n$ into the summation, we can combine $n-k$ powers of $-1$ with the terms of the falling factorial; this can be rewritten as
$$
\sum_{k=0}^n (-1)^{k} r_k^\mathcal{B} (x+n-k)^{\underline{n-k}}.
$$

For the next part of the argument, let’s fix $x$ to be some positive integer, so that $r_k^\mathcal{B} (x+n-k)^{\underline{n-k}}$ is a nonnegative integer. What could it be counting?

Embed the board $\mathcal{B}$ into an $n\times n$ square board. Then, append $x$ more rows to the bottom of board, producing an $(x + n) \times n$ board. Now, there are still $r_k^\mathcal{B}$ ways to place $k$ rooks onto $\mathcal{B}$. Each of these arrangements leaves $x+n-k$ rows unoccupied and $n-k$ columns unoccupied, too.

We can then place $n-k$ more rooks on the board in $(x+n-k)^{\underline{n-k}}$ different ways. So together, $r_k^\mathcal{B} (x+n-k)^{\underline{n-k}}$ is the number of ways to place $n$ rooks on the $(x+n) \times n$ board by first placing $k$ rooks on $\mathcal{B}$ and then another $n-k$ rooks anywhere else.

Ah, but that second batch of rooks might have been placed on the extra rows, on the complement board $\overline{\mathcal{B}}$, or even on some unoccupied space of $\mathcal{B}$. When we sum over $0 \leq k \leq n$, the same configurations will be counted multiple times with differing signs from the $(-1)^{k}$ term. What gets cancelled out, and what remains?

Consider one of these arrangements without knowing how the two steps were performed. Each arrangement has some number of rooks on $\mathcal{B}$, which we’ll call $j$. In the summation, the same arrangement will be counted once for each of the $2^j$ subsets of the rooks on $\mathcal{B}$.

Set $x=2$. This arrangement is counted once by $r_0^\mathcal{B}(x+4)^{\underline{4}}$, three times by $-r_1^\mathcal{B}(x+3)^{\underline{3}}$, three times by $r_2^\mathcal{B}(x+2)^{\underline{2}}$, and once by $-r_3^\mathcal{B}(x+1)^{\underline{1}}$, all together $1-3+3-1 = 0$ times.

There is only one way rooks not on $\mathcal{B}$ could have been placed, step two. However, both steps in this process could have put a rook on $\mathcal{B}$. And the parity of $k$ in step one controls the minus sign! So if $j > 0$, these solution counts will cancel each other out in the sum. However, if $j=0$, the only subset of the empty solution on $\mathcal{B}$ is itself, and there is no cancellation.

That means, only arrangements in which there are no rooks on $\mathcal{B}$ will remain in the count. The only solutions we see have all the rooks placed on $\overline{\mathcal{B}}$ or on the $x$ extra rows. We can count those solutions directly: If there are $j$ rooks on $\overline{\mathcal{B}}$ and $n-j$ rooks on the extra rows, then there are $r_j^{\overline{\mathcal{B}}} x^{\underline{n-j}}$ ways to place them.

So, by summing over all the possible values of $j$, we have that
$$
(-1)^n \sum_{k=0}^n r_k^\mathcal{B} (-x-1)^{\underline{k}}
=\sum_{j=0}^n r_j^{\overline{\mathcal{B}}} x^{\underline{n-j}},
$$
or rather,
$$
(-1)^n \tilde{R}_\mathcal{B}(-x-1) = \tilde{R}_\mathcal{\overline{B}}(x).
$$

Now, this equation is describing the outputs of the two polynomials for some integer $x > 0$. Ah, but the size of $x$ was arbitrary during our argument. The only way that two polynomials can output the same value for all positive integers is that they are in fact the same polynomial.
Done.

Now, there are many other directions that the rook problem can lead to. When can two different boards have the same rook polynomials? Which polynomials are rook polynomials for some board? Can we pursue the rook problem in three or more dimensions? Could we have used a different chess piece?

I encourage you to think about the way we have used polynomials to organize our solution to this problem. We are not using polynomials as single objects in a vacuum. The insight here was to attach our counting problem to an algebraic structure. This technique is more broadly known as a generating function. When we are interested in some sequence of numbers, we can think of them as the coefficients of a polynomial or a power series, and manipulate the larger objects according to whatever algebraic rules they follow. The trick is to find the function that counts.

References

  • Timothy Chow. A short proof of the rook reciprocity theorem. Electron. J.
    Combin.
    , 3(1):Research Paper 10, approx. 2, 1996.
  • Jay R. Goldman, J. T. Joichi, and Dennis E. White. Rook theory. I. Rook
    equivalence of Ferrers boards. Proc. Amer. Math. Soc., 52:485–492, 1975.
  • John Riordan. An introduction to combinatorial analysis. Dover Publications,
    Inc., Mineola, NY, 2002. Reprint of the 1958 original [Wiley, New York;
    MR0096594 (20 #3077)].
  • Herbert S. Wilf. generatingfunctionology. A K Peters, Ltd., Wellesley, MA, third
    edition, 2006.

Leave a Reply

Your email address will not be published. Required fields are marked *

HTML tags are not allowed.

43,852 Spambots Blocked by Simple Comments