Number of ways to place $k$ non-attacking rooks on an $m\times n$ chessboard

I need to calculate the number of ways to place $k$ non-attacking rooks on an $m \times n$ table where $k \leq n$ and $k \leq m$. ("Non-attacking" means that no two rooks may share a row or column.) My attempt: Calculate the number of ways to place $k$ rooks on a $k \times k$ board ($k!$), then multiply by the number of ways to select a $k \times k$ board from an $m \times n$ board. (This is the part I can't calculate, if it is correct at all.) My question: Is my approach good and if so, how to calculate the second part?

• Why not just $\binom{mn}{k}$? Without any restriction on how the rooks are to be placed, shouldn't we think of this as placing $k$ things in $mn$ boxes where no box can have two things? – TheNumber23 Mar 11 '14 at 20:56
• I think "placing rooks" is almost always defined as "choosing squares such that no two are on same column or on same row", so one might argue that it is a universal term. – JiK Mar 11 '14 at 21:09

It is a reasonable approach. The columns can be chosen in $\binom{m}{k}$ ways and for each way of selecting columns the rows can be chosen in $\binom{n}{k}$ ways.

• I think that Bamdad has this right... – stuart stevenson May 22 '18 at 13:13
• @stuartstevenson, André is answering the explicit questions in the last sentence of the post body: Bamdad is answering the implicit question in the title, which is not the same. – Peter Taylor May 22 '18 at 15:11

This is not so hard. First, we want to select $n$ rows to place our rooks in (obviously, no repetition in choosing the rows). This can be done in $n\choose{k}$ ways. Similarly, we have to choose $m$ columns for the rooks, which is done in $m\choose{k}$ ways. However, when we choose the $m$ columns, we are not deciding the order they lay in. So we multiply this result by $k!$ and we shall be done. So the general formula for this problem is $n\choose{k}$$m\choose{k}$$k!$.

Try $m = 3$, $n = 2$ and $k = 2$, a small example. If you write down all possibilities, you shall end up with $6$ arrangements of rooks, and $6=$$3\cdot1\cdot2=$$2\choose{2}$$3\choose{2}$$2!$

You are being asked to calculate the rook number of a particular board. This problem is explicitly worked out on the Wikipedia page for Rook Polynomials: http://en.wikipedia.org/wiki/Rook_polynomial#The_rook_polynomial_as_a_generalization_of_the_rooks_problem

I think you can choose $k$ squares out of $nm$ in $\pmatrix{ nm\\k}$ different ways, and for each one of these choices there are $k!$ different ways to set the rooks, so the result is $k!\pmatrix{ nm\\k}$.

• @youall I agree now my answer is utterly wrong, but when I wrote it the clause "non-attacking" was not in the OP question. See the editing history. – alex Apr 17 '14 at 13:20