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)$
 A: 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).$$
A: 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}.$$
