Harry Potter and the Order of the Symmetric Group: A Problem of Richard Stanley from the 1981 Banff Conference on Ordered SetsJonathan FarleyMIT
September 24,

ABSTRACT


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 zigzagshaped 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 favourite 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 zigzag 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 naturallylabelled 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 $n1rk$ descents. We establish such a bijection, thus solving Stanley's problem. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

