Finding Gemstones: on the quest for mathematical beauty and truth
< Previous Post Next Post >

Teeter-totter transpositions

In attempting to write problems for the USAMO, I came across an interesting variant of Knuth equivalence whose structure is rather intricate.

Suppose we start with the numbers $1,2,3,\ldots,n$ written in a row. At each step, we may choose three adjacent numbers in the sequence, say $a,b,c$, and if either $a\lt b \lt c$ or $c\lt b\lt a$ then we can switch $a$ and $c$. So for instance, we might start with 12345 and change it to 32145. At this point we cannot use the subsequence 2,1,4 to change the 2 and 4, but we can use 1,4,5 and end up with 32541. The question is, how many possible sequences can we end up with after a sequence of such moves? (I call them `teeter-totter moves’, since you can either change three consecutive elements from increasing to decreasing or vice versa.)

Some quick hand calculations yield the values $1$, $1$, $2$, $3$, $6$, $10$, $20$, $35$, $70$, $126$ for $n=1$ up to $n=10$. But this sequence is quite recognizable: it is the sequence of ``middle elements” in Pascal’s triangle:

So, it appears that the number of permutations of $1,2,\ldots,n$ that can be formed by a sequence of teeter-totter moves is \[\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}.\] But why?

After struggling to answer this for quite a while, I stumbled across a solution in this paper by Linton, Propp, Roby, and West. It is their Theorem 14, and in my opinion one of the most impressive proofs of that paper. They essentially show that any achievable permutation can be decomposed into odd-length blocks of a certain form, and then enumerate these using generating function techniques.

My question is, is there a more direct approach? The quantity $\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$ is too nice for there not to be a slick combinatorial interpretation that proves the result immediately. (It may be hard to prove that the said combinatorial interpretation is correct, but as long as it exists I would be happy.) Any ideas?