Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.