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?