How to compute ROOK Polynomials for NxM Matrices for k objects ?

  • 1
    $\begingroup$ Tuhin, the purpose of this site is not for asisting in homework. I'd say you may look at stackoverflow.com, but you already asked there (stackoverflow.com/questions/4071804/matrix-problem-in-c) $\endgroup$
    – didest
    Nov 3 '10 at 1:44
  • $\begingroup$ Also, "rook" shouldn't be capitalized. It's a chess piece, not an abbreviation. $\endgroup$
    – Jeffε
    Nov 3 '10 at 16:01

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


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