Nonattacking rooks on a triangular chessboard

Question

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

Answer 1

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.