6
$\begingroup$

Given an $n \times n$ chessboard from which the squares above the diagonal have been removed, find the number of ways to place $k$ non-attacking rooks on this board.

I believe the answer to be $S(n+1, n-k+1)$, where $S(n,k)$ is the Stirling number of the second kind. Most of the sources I've encountered state this as "a well-known result", and move on to prove more complicated results based on it, but I don't see how this is apparent, nor can I find any proof of it. There are a few details here, but I don't see the correspondence between the details and the eventual result.

There is a hint with the question that suggests finding a bijection between these configurations and placing objects into boxes. Given that the answer above is correct, and appealing to the combinatorial definition of Stirling numbers, this would imply that there are $n+1$ "objects" and $n-k+1$ indistinguishable "boxes" into which we will arrange the objects, with no box left empty. But what are we interpreting as the objects and boxes?

Simple cases:

$k=n$ admits exactly one configuration: all rooks along the diagonal.

$k>n$ admits no valid configurations.

$k=1$ admits $n(n+1)/2$ configurations (corresponding to placing the rook on each square).

$\endgroup$
8
$\begingroup$

Hint. Let $R(n,k)$ be the number you seek. Consider two cases.

  • The bottom row contains no rooks. Then the number of arrangements is $R(n-1,k)$.
  • The bottom row contains one rook. Therefore the rest of the board contains $k-1$ rooks, which can be placed in $R(n-1,k-1)$ ways. Now place the rook in the bottom row: $k-1$ of the columns are no longer available, so there are $n-(k-1)$ options.

This gives the recurrence $$R(n,k)=R(n-1,k)+(n+1-k)R(n-1,k-1)\ ,$$ and you can now use the recurrence $$S(n+1,k)=S(n,k-1)+kS(n,k)$$ to prove inductively that your conjecture is correct.

$\endgroup$
  • $\begingroup$ Welcome to club 20k! Use the resulting superpowers wisely :-) $\endgroup$ – Jyrki Lahtonen Aug 1 '14 at 16:38
  • $\begingroup$ Thanks @Jyrki ! First of all I'll have to look up the superpowers and find out what they are... $\endgroup$ – David Aug 1 '14 at 19:48

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.