How to compute the rook polynomial of a Ferrers board?

Question

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

Answer 1

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

Answer 2

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