Say we have an nxn chessboard from which the squares below the diagonal are removed to obtain a new board $C_n$. The board $C_3$ is shown below.
Let the number of ways to place k non-attacking rooks on board $C_n$ is given by $r_k(C_n)$. What I want to prove is that:
$$\sum_{k=0}^{n} r_k(C_n)x^k = \sum_{k=0}^{n} S(n+1, n+1-k)x^k$$ where $S(n,k)$ is a stirling number of second kind.
So far I have the bijective proof for recurrence relation for the rook placement:
$$r_k(C_n) = r_k(C_{n-1}) + (n-(k-1))r_{k-1}(C_{n-1}) $$
Proof I have goes as follow:
Either: Place k rooks on the board $C_{n-1}$, there are $r_k(C_{n-1})$ ways to do so where $C_{n-1}$ is obtained by deleting top row of $C_n$
Or: Place $k-1$ rooks on the board $C_{n-1}$ and place the last rook on the top row of $C_n$. Placing $k-1$ rooks on the board $C_{n-1}$ implies that we cannot place the last rook on $k-1$ columns. Hence we can place the last rook on $n-(k-1)$ squares in the top row of $C_n$. there are $(n-(k-1))r_{k-1}(C_{n-1})$ ways to do this. Using BCP2 we add either and or case to give:
$$r_k(C_n) = r_k(C_{n-1}) + (n-(k-1))r_{k-1}(C_{n-1})$$
The recursion for Stirling number is:
$S(n+1, n+1-k) = S(n, n - k) + (n+1-k)S(n, n+1-k)$
They both satisfy the same initial conditions:
When $k = 0$ we have $r_0(C_n) = 1$ and $S(n+1, n+1) = 1$
and when $k=n$ we have $r_n(C_n) = 1$ and $S(n+1, 1) = 1$
I also know that e.g. rook placement for 2 rooks on board $C_3$:
corresponds to the set partition {{4,3,2}, {1}}
I don't understand what to do after this to complete the proof. Am I even on the right track? Ultimately, what I want is a bijective proof for:
$$\sum_{k=0}^{n} r_k(C_n)x^k = \sum_{k=0}^{n} S(n+1, n+1-k)x^k$$
Let $C_n$ be the triangular board of side length $n$ with squares in positions $(i,j)$ for $i \le j$, so $C_3$ is as shown in the question.
Given a non-attacking placement of $k$-rooks on $C_n$, there is a corresponding function $f : \{1,2,\ldots,n,n+1\} \rightarrow \{2,\ldots,n,n+1\} \cup \{ \star\}$ defined by
$$f(i) = \begin{cases} j+1 &\text{if there is a rook in square $(i,j)$} \\ \star & \text{if there is no rook on row $i$.} \end{cases} $$
(In particular, $f(n+1) = \star$ for any placement, since row $n+1$ is empty.)
Bijection. Let $Y = f(\{1,2,\ldots,n,n+1\}) \backslash \{\star\}$. Let $Y' = \{1,2,\ldots,n,n+1\} \backslash Y$. Since $|Y| = k$, we have $|Y'| = n+1-k$. For each $i \in Y'$ let
$$A_{i} = \{i,f(i),f(f(i)), \ldots \} \backslash \{ \star \}.$$
If $i \in Y'$ then $i$ is not in the range of $f$, so the sets $A_i$ for $i \in Y'$ form a set partition of $\{1,2,\ldots,n,n+1\}$ into $n+1-k$ parts.
Inverse. Conversely given such a set partition, take $Y'$ to be the $(n+1-k)$-set of minimum elements of the parts. For each $i \in Y'$, define $f$ so that the displayed equation above holds for elements in the part containing $i$, setting $f(i^\star) = \star$ if $i^\star$ is the biggest element in this part. Then take the corresponding rook placement.
For example, if $n=5$ and $k=3$ then the set partition $\bigl\{ \{1,4,6\}, \{2\}, \{3,5\} \bigr\}$ corresponds to the function $f$ defined by $f(1)=4$, $f(4) = 6$, $f(6) = \star$, $f(2) = \star$, $f(3) = 5$, $f(5) = \star$, and so to the rook placement with rooks in positions $(1,4-1)= (1,3)$, $(4,6-1) = (4,5)$, $(3,5-1) = (3,4)$.
This is essentially the same as the bijection outlined on pages 77 and 78 of Loehr's textbook Bijective combinatorics.