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.

Board $C_3$

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.


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.