C5. Given a permutation of $1,2,3, \ldots, n$, with consecutive elements $a, b, c$ (in that order), we may perform either of the moves:
- If $a$ is the median of $a, b$, and $c$, we may replace $a, b, c$ with $b, c, a$ (in that order).
- If $c$ is the median of $a, b$, and $c$, we may replace $a, b, c$ with $c, a, b$ (in that order).

What is the least number of sets in a partition of all $n$ ! permutations, such that any two permutations in the same set are obtainable from each other by a sequence of moves?
(Milan Haiman)
The number of equivalence classes turns out to be
$$
n^{2}-3 n+4=2\left[\binom{n-1}{2}+1\right]
$$

First we show that at least $2\binom{n-1}{2}+2$ sets are required.
Define the disorder of a permutation to be the number of pairs $(i, j)$ such that $1 \leq i<j \leq n$ but $i$ occurs after $j$ in the permutation. We will also refer to these pairs as pairs that are out of order. We will refer to other such pairs with $i$ occurring before $j$ as in order.

Note that disorder is invariant under moves, as the only pairs whose relative orders change are the ones involved in the move. We can easily check that the number of pairs out of order does not change.

Consider the pair $(1, n)$. Notice that a move cannot change the relative order of this pair, as neither 1 nor $n$ can be the median of three elements of a permutation of $1,2,3, \ldots, n$

Lemma 1
There exists a permutation of $1,2,3, \ldots, n$ with disorder $d$, if $0 \leq d \leq\binom{ n}{2}$.

Proof. Start with the identity permutation $1,2,3, \ldots, n$, which has disorder 0 . Now repeatedly swap two adjacent elements that are in order. We may do this until all adjacent elements are out of order, which occurs only with the reverse permutation $n, \ldots, 3,2,1$. Notice that each swap increases the disorder by exactly 1 , and that this process takes us from disorder 0 to disorder $\binom{n}{2}$. Thus disorder $d$ must have been attained after exactly $d$ moves.

Consider $\binom{n-1}{2}+1$ permutations of $2,3,4, \ldots, n$, with one of each disorder from 0 to $\binom{n-1}{2}$, by Lemma 1. Putting the element 1 at the beginning of each of these permutations gives $\binom{n-1}{2}+1$ permutations of $1,2,3, \ldots, n$ with distinct disorders. Now consider the reverses of each of these permutations. They will all have the pair $(1, n)$ out of order, and thus cannot be obtained from the original permutations by moves. Furthermore they all have distinct disorders, from $\binom{n}{2}-\binom{n-1}{2}=n-1$ to $\binom{n}{2}-0=\binom{n}{2}$. Thus these $2\binom{n-1}{2}+2$ permutations all cannot be obtained from each other by moves. This proves the lower bound.
Now we show that $2\binom{n-1}{2}+2$ sets are attainable. We will categorize permutations into sets by their disorder and whether the pair $(1, n)$ is in order or not. Note that if $(1, n)$ is in order we must have a disorder of at most $\binom{n-1}{2}$, since at most one of the pairs
$(1, k)$ and $(k, n)$ can be out of order for each $1<k<n$. Similarly if $(1, n)$ is out of order we must have a disorder of at least $n-1$. Thus we are using only $2\binom{n-1}{2}+2$ sets. It remains to show that any two permutations in the same set are obtainable from each other by a sequence of moves.
Lemma 2
Given a permutation of $1,2,3, \ldots, n$ we can perform a sequence of moves to obtain
a permutation with $n$ either at the beginning or the end.

Proof. If $n$ is at the beginning or end of the permutation we are done. Otherwise suppose that $k$ and $l$ are the two elements adjacent to $n$, in some order. Without loss of generality, $k<l<n$. Then $l$ is the median of the three elements $k, l$, and $n$. So we may perform a move on these three elements (as $n$, not $l$, is the middle term).

We will repeat this process. As we do so, consider the ordered pair $(x, y)$, where $x$ is the minimum of the elements adjacent to $n$, and $y$ is the number of elements on the other side of $n$ from $x$. Note that if $y$ ever reaches 0 then we are done.

We claim that this ordered pair is lexicographically monotonically decreasing. Suppose that this ordered pair is $\left(x_{0}, y_{0}\right)$ before a move (as described above) and ( $\left.x_{1}, y_{1}\right)$ after. Notice that the move will keep $x_{0}$ adjacent to $n$. Thus if $x_{1} \neq x_{0}$ then $x_{1}=\min \left(x_{0}, x_{1}\right)<$ $x_{0}$. Now if $x_{1}=x_{0}$ then one number has moved from the other side of $n$ from $x$ to the same side of $n$ as $x$. In this case $y_{1}=y_{0}-1<y_{0}$. This proves our claim. Now note that, by the claim, we must eventually obtain an ordered pair $(x, y)$ with $y=0$, as desired.

Now we will show by induction on $n$ that given two permutations $\sigma$ and $\pi$ of $1,2,3, \ldots, n$ with the same disorder and with $(1, n)$ in the same relative order, $\sigma$ and $\pi$ are obtainable from each other by a sequence of moves.
It is easy to check values of $n \leq 4$.
WLOG assume that both $\sigma$ and $\pi$ have $(1, n)$ in order. By Lemma 2 we can perform a sequence of moves to obtain $n$ at the end of both permutations (it cannot be at the beginning since that would put $(1, n)$ out of order). Now no pairs with $n$ are out of order in either permutation. Thus looking at only the first $n-1$ terms of the permutations we see that they still have the same disorder. Then if the pair $(1, n-1)$ has the same relative order in both permutations we are done by induction.

Now suppose $(1, n-1)$ does not have the same relative order in both permutations. Consider the disorder $d$ of both permutations. On one hand, since we have $(1, n-1)$ in order $d \leq\binom{ n-1}{2}-(n-1)$. Similarly, since we have $(1, n-1)$ out of order, $d \geq n-1$.

Note that we can choose a permutation of $1,2,3, \ldots, n-1$ with the last three terms being $x, 1, n-1$ and having disorder $d$, such that $x \neq n-2$. Similarly, we can choose a permutation with the last two terms being $n-1,1$ and having disorder $d$. By induction, we can perform a sequence of moves on the first $n-1$ terms (leaving $n$ in place) of $\sigma$ and $\pi$ to obtain two permutations of the form $\ldots, x, 1, n-1, n$ and $\ldots, n-1,1, n$. It is sufficient to show that we can also perform a sequence of moves to obtain the latter from the former. We perform the following moves:
$$
x, 1, n-1, n \rightarrow \ldots, 1, n-1, x, n \rightarrow \ldots, 1, x, n, n-1
$$

Now by Lemma 2 on the first $n-2$ terms we may perform a sequence of moves to move 1 to the beginning or to the end of the first $n-2$ terms. Since $x \neq n-2,1$ must be at the end of the first $n-2$ terms, otherwise the relative order of $(1, n-2)$ would change. Thus we now have a permutation of the form $\ldots, 1, n, n-1$ from which we
obtain a permutation of the form $\ldots, n-1,1, n$. Then applying induction again we obtain specifically the desired permutation of the form $\ldots, n-1,1, n$.
Remark. We can also prove Lemma 2 quite easily with induction. However the proof given more explicitly shows the actual moves we make. That is, we "attach" $n$ to a "small" element and slide it around with that element until it hits an even "smaller" element repeatedly.
Remark. Result is known: https://arxiv.org/pdf/0706 . 2996.pdf.