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?
Best Answer
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