Linear Extensions of a Ranked Poset, Enumerated by Descents: A problem of Richard P. Stanley from 1981

Jonathan Farley
Massachusetts Institute of Technology

Let ``Fred" be a finite partially ordered set, labelled by the numbers 1, 2, 3, up to $n$ so that, whenever an element $p$ is below an element $q$ in the poset, the label of $p$ (a natural number) is less than the label of $q$. (The permutation $123...n$ is a ``linear extension" of the poset Fred.)

For example, consider the zig-zag-shaped poset with four elements $1,2,3,4$, whose partial ordering is given by $1<3>2<4$.

Look at the linear extensions, that is, the permutations in $S_n$ that respect the partial ordering of Fred, by which we mean the following: If the element labelled $i$ in Fred is below the element labelled $j$ in Fred, then the number $i$ must come before the number $j$ in the permutation. In our example, there are 5 linear extensions: $1234$, $2134$, $1243$, $2143$, and $2413$.

Now take your favorite linear extension and count the number of descents, the number of places where a bigger number comes immediately before a smaller number. In our example, the number of descents in the linear extensions is given by 0, 1, 1, 2, and 1, respectively. Let $H_k$ be the set of linear extensions with $k$ descents and let $h_k$ be the number of such extensions. The zig-zag has $h_0=1$, $h_1=3$, and $h_2=1$.

The $h$-vector in this case---(1,3,1)---is symmetric. Around 1971 Stanley proved that the $h$-vector of a ranked poset is symmetric. At the 1981 Banff Conference on Ordered Sets, Stanley asked for a bijective proof of this fact. To wit, if a naturally-labelled poset of size $n$ is ranked (all maximal chains have the same number of elements $r+1$), Stanley wanted to find a bijection between the set of linear extensions with $k$ descents and the set of linear extensions with $n-1-r-k$ descents.

We establish such a bijection, thus solving Stanley's problem.