4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – TheNumber23 Mar 11 '14 at 20:56
  • $\begingroup$ 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. $\endgroup$ – JiK Mar 11 '14 at 21:09
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think that Bamdad has this right... $\endgroup$ – stuart stevenson May 22 '18 at 13:13
  • $\begingroup$ @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. $\endgroup$ – Peter Taylor May 22 '18 at 15:11
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – alex Apr 17 '14 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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