How to compute ROOK Polynomials for NxM Matrices How to compute ROOK Polynomials for NxM Matrices for k objects ?
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$.