# How to compute the rook polynomial of a Ferrers board?

Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's shown the identity: $$\sum_k r_k (x)_{m-k} = \prod_i (x+s_i)$$ where $s_i = b_i-i+1$, but I don't know if I can invert this formula or make an efficient algorithm to compute the $r_k$'s.

If this isn't possible, I would be satisfied if I can compute them efficiently in the following shapes:

$(2,2,4,4,\ldots,2n-2,2n-2,2n)$

$(2,2,4,4,\ldots,2n,2n)$

$(1,1,3,3,\ldots,2n-1,2n-1,2n+1)$

-
Have you tried computing some small cases by hand to see if there is an obvious pattern? –  Dan Petersen Apr 5 '10 at 22:03
Just curious, what does $(x)_{m-k}$ mean? –  Sergei Ivanov Apr 5 '10 at 22:09
Sergei, usually $(x)_n = x(x-1) \cdots (x-n+1) = n! \binom x n$ and is called the Pochhammer symbol or falling factorial. –  Sammy Black Apr 5 '10 at 22:39
As for converting the monomial basis $x^k$ to the falling factorial basis $(x)_n$, are you familiar with the Stirling numbers? en.wikipedia.org/wiki/Stirling_number I don't know if that would be a useful idea for what you're trying to do though. –  Steven Sam Apr 5 '10 at 22:46
@dan, this is the sequence for the first shape: research.att.com/~njas/sequences/A088960 (number of configurations of $k$ non-attacking bishops on the white squares of an $n\times n$ chessboard, for $n$ even.) The other two are the same with odd $n$, one on black squares and the other on white squares. –  Diego de Estrada Apr 6 '10 at 0:45

You can retrieve the coefficients of a polynomial written in the falling factorial basis by computing finite differences, as follows.

Let $f : \mathbb{Z} \to \mathbb{Z}$ be a function, and let $\Delta f(n) = f(n+1) - f(n)$. Let $\Delta^{r+1} f = \Delta(\Delta^r f)$.

Lemma 1: $\displaystyle \Delta {n \choose k} = {n \choose k-1}$.

Corollary: If $\displaystyle f(n) = \sum_{i=0}^d a_i {n \choose i}$, then $\Delta^i f(0) = a_i$.

Lemma 2: $\displaystyle \Delta^i f(0) = \sum_{j=0}^{i} (-1)^{i-j} {i \choose j} f(j)$.

Note the similarity to how the Taylor coefficients of a polynomial in the usual basis are extracted, and note that $\displaystyle {n \choose k} = (n)_k k!$. For the sake of having a final answer, this gives

$$r_k = \frac{1}{(m-k)!} \sum_{j=0}^{m-k} (-1)^{m-k-j} {m-k \choose j} \prod_i (j + s_i).$$

-
Thank you very much, Qiaochu! –  Diego de Estrada Apr 6 '10 at 3:27

Although the closed formula is what I wanted, a dynamic programming approach behaves better algorithmically:

Define $M_{i,j}$ as the number of ways to place $j$ non-attacking rooks on the Ferrers board of shape $(b_1,\ldots,b_i)$. So we want $M_{m,k}$, which can be computed using the relations: $M_{i,0}=1$, $M_{0,j}=0$ if $j>0$, and if $i,j>0$: $$M_{i,j} = M_{i-1,j} + (b_i-j+1) M_{i-1,j-1}.$$

-