Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question

closed as off topic by Karolina Sołtys, Aaron Sterling, Lev Reyzin, Kaveh, Peter Shor Nov 3 '10 at 3:35

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
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) –  Diego de Estrada Nov 3 '10 at 1:44
    
Also, "rook" shouldn't be capitalized. It's a chess piece, not an abbreviation. –  JɛffE Nov 3 '10 at 16:01

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

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