paths on differential posets and rooks

Statement

Let $W$ be a walk on a differential poset. Then,

f_{W} = r_{W}

where $f_{W}$ is the number of paths in $P$ that start at end at $\hat{0}$ with the pattern $W$ .
and $r_{W}$ is the number of nonattacking rook placements in the Young diagram of $W$ .

In particular, if $κ_{W} = (κ_{1}, κ_{2}, \dots, κ_{n})$ , then

r_{W} = κ_{n} (κ_{n - 1} - 1) (κ_{n - 2} - 2) \dots (κ_{1} - n + 1)

Proof

The latter statement follows by noting that we may start by choosing a place for the rook in the last row, of which there are $κ_{n}$ options, and then continuing upwards, noting that we are forbidden from previously chosen columns.

Proof sketch: show the same recurrence relation as follows: there is an instance of $U D$ in $W$ . Then, if we write

W = W_{1} U D W_{2}

define $W^{'} = W_{1} D U W_{2}$ and $W^{″} = W_{1} W_{2}$ . Then, one can show that

f_{W} = f_{W^{'}} + f_{W^{″}}

with an analogous statement for the rook placements.