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

1 Answer 1

9
$\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$
2
  • 1
    $\begingroup$ Welcome to club 20k! Use the resulting superpowers wisely :-) $\endgroup$ Aug 1, 2014 at 16:38
  • 1
    $\begingroup$ Thanks @Jyrki ! First of all I'll have to look up the superpowers and find out what they are... $\endgroup$
    – David
    Aug 1, 2014 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .