# Harry Potter and the Order of the Symmetric Group: A Problem of Richard Stanley from the 1981 Banff Conference on Ordered Sets

## 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 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 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 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.

Speaker's Contact Info: N/A