How to compute ROOK Polynomials for NxM Matrices for k objects ?
How to compute ROOK Polynomials for NxM Matrices
co.combinatorics;polynomials;permutations
See the answers of this question.Your case is a lot easier, just choose $k$ of the $m$ columns and then you have$n (n-1)\ldots (n-k+1)$ ways to put the $k$ rooks. So the coefficient of $x^k$ is$\displaystyle r_k = \binom{m}{k} n (n-1)\ldots (n-k+1) = \binom{m}{k}\binom{n}{k}k!$.The provided link also gives a dynamic programming approach to compute $r_k$.