So, there is an exercise in Section 8.3 in Alan Tucker's Applied Combinatorics regarding rook polynomials. The problem is as follow.
- Let $R_{n, m}(x)$ be the rook polynomial for an $n \times m$ chessboard ($n$ rows, $m$ columns, all squares may have rook).
(a) Show that $R_{n,m}(x) = R_{n-1,m} + mxR_{n-1,m-1}(x)$.
(b) Show that $\frac{d}{dx}R_{n,m}(x) = nmR_{n-1, m-1}(x)$.
I was able to solve (a) but got stuck at (b). I tried to reuse the result from (a) by multiplying (b) by $x$ then adding 1: $$\begin{split} x \cdot \frac{d}{dx}R_{n,m}(x) + 1 &= n(mxR_{n-1,m-1}(x)) + 1 \\ &= n(R_{n,m}(x) - R_{n-1,m}(x)) + 1 \end{split}$$
Let $C_{n,m}$ be the $n \times m$ chessboard. Then the left-hand side will evaluate to $\sum_{k=0}^{nm}{k \cdot r_k(C_{n,m})x^k}$.
I was trying to prove the equation by expanding the right-hand side and then prove the equality of each term for $k$ but haven't figured out for now. Am I doing the right way? The exercise gives me a hint, that is to use another identity:
$$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1} $$
How is this even relevant to the problem?