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?
Great post! One of the entries on the OEIS for this sequence is the number of ordered trees with $n+1$ edges having nonroot vertices of outdegree $0$ and $2$.
If you label the nonroot vertices $1$ through $n$, such that restricting to each level is increasing and that (left child < parent < right child), then the vertices of outdegree $2$ are the centers of "teeter-totters", and starting with the last generation and moving towards the root tells you in what order to implement the permutations.
Ooh, Zvi, I like this interpretation. The trees you mentioned are not hard to enumerate using generating functions, and that’s a really nice bijection you have there.
Now what would really be nice is a further bijection from these trees to Anders’ Dyck paths below; then we can directly get the binomial coefficient without the use of generating functions. Hmm…
Aha, here’s what it is: Take an ordered rooted tree for which every non-root vertex has out-degree 0 or 2. Then the second-level vertices, namely, the children of the root, each correspond to an “up” or “down” section of the path in Anders’ diagram below. The sections in between are Dyck paths, which are counted by the Catalan numbers. But the ordered rooted strictly binary trees are also enumerated by the same Catalan numbers, and we’re done. Now I’m satisfied!
(n – 1 choose floor((n – 1)/2)) is the number of staircase walks from (0, 0) to (floor((n – 1)/2), floor(n/2)). Slicing such a walk along the diagonal y – x = 1/2 yields a sequence of one or more Dyck paths (alternating upwards and downwards) such that the sum, over their orders k, of 2k + 1 is n.
So we just need to correspond the Dyck paths of order k to the plus-indecomposable 321-avoiding permutations of order k + 1. The k = 0 case is trivial. For k ≥ 1, any such permutation decomposes uniquely into two increasing subsequences {(i, f(i))} and {(j, g(j))} such that $f(i) < i$, $g(j) > j$. Either subsequence uniquely determines the other, and indeed, the points in either subsequence constitute the valleys of a unique Dyck path.
To put this a little more visually:
http://web.mit.edu/andersk/Public/teeter.png
Oh look: every teeter-totter move in the permutation corresponds to a UR ↦ RU or RU ↦ UR switch in the staircase walk!
(Not every such switch is valid—you’re only allowed to change the total number of corners when crossing the diagonal, or something—but there are still plenty of switches to generate all walks.)
Er, actually, an R may be switched a sequence of one or more Us.
Ah, very nice. I like this, though it’s unclear to me why the Dyck paths uniquely correspond to the permutation, other than using the difficult arguments in the paper I linked to in the post. Nice picture, though!
You get a unique permutation because the “floating blocks” in the picture can be located by intersecting the vertical through the kth RR with the horizontal through the kth UU.