In a recent talk (in fact today, 26 May 2011) at the W80 conference celebrating the 80th birthday of Herbert Wilf <http://www.cargo.wlu.ca/W80/>, Doron Zeilberger gave a talk on pattern avoiding permutations. Given a permutation $\sigma \in \mathfrak{S}\_n$, the symmetric group on $n%$ letters, we say $\sigma$ avoids a pattern $\tau$ if no substring of $\sigma$is configured in the order of $\tau$. For example, if $\tau = 123$, then $35421$ avoids $123$ since no substring of $a\_1 a\_2 a\_3$ of $35421$ satisfies $a\_1 < a\_2 < a\_3$. On the contrary, $13254$ does not avoid $123$ since for $a\_1 = 1, a\_2 = 2, a\_3 = 5$ we have $a\_1a\_2a\_3$hits the pattern $123$. Zeilberger mentioned that this is an enormously difficult problem even for simple patterns like short cycles. Explicit answers are known for the pattern $1432$ and $1342$, but Zeilberger claimed that enumerating the permutations avoiding $1324$ is an incredibly difficult problem that will still be completely unknown in 200 years (he also claimed that in 200 years the Riemann Hypothesis and the P vs. NP problem will both be exercises in undergraduate textbooks, as to illustrate the relative difficulty of the problem).


I remarked to him that $1324$ is a zig-zag pattern, namely a pattern $a\_1a\_2\cdots a\_n$ such that $a\_1 < a\_2, a\_2 > a\_3, a\_3 < a\_4, \cdots$ I asked if the fact that $1324$ is a zig-zag pattern is what makes it difficulty. He couldn't answer; but thought the remark was worthy of pursuit.


And so I turn the question back to MO: Does anyone have any results on avoiding any zig-zag patterns? If that is not available, does anyone have a heuristic as to why enumerating permutations avoiding zig-zag patterns would be difficult, or is it just completely unknown?



Pattern avoiding permutations and zig-zags
For involutions, 3412-avoiding involutions are counted by the Motzkin numbers, and there is a nice bijection to Motzkin paths [1].


Would you still call the upside-down version of this pattern zig-zag? If so, then 2143-avoiding permutations are called vexillary, and there are several results about them. They are Wilf equivalent (by a bijection) to permutations avoiding 2134, 3421, 1243, and 1234 [2]. The last one tells us that we have a map to the usual pairs of three-column tableaux.


2143-avoiding involutions are also counted by the Motzkin numbers. The Barnabei reference will lead you to most of the relevant papers for this collection of patterns that I know of.


[1] M. Barnabei et al., Restricted involutions and Motzkin paths, Adv. in Appl. Math. (2010), doi:10.1016/j.aam.2010.05.002


[2] J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, 1990


