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.