MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In a recent talk (in fact today, 26 May 2011) at the W80 conference celebrating the 80th birthday of Herbert Wilf, 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?

share|cite|improve this question
132 is also a zig-zag pattern. What's known about avoiding that one? 13542 is not a zig-zag pattern. Will that one be unsolved in 200 years? By the way, Hilbert thought he would live to see the resolution of the Riemann Hypothesis, but that the irrationality of $2^{\sqrt2}$ was 100 years off. In fact the latter was settled within the decade, while the former.... – Gerry Myerson May 27 '11 at 6:24
Gerry: 132-avoiding permutations are enumerated by the Catalan numbers. – Jonah Ostroff May 27 '11 at 14:35
up vote 13 down vote accepted

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

share|cite|improve this answer
Yes, 'upside down' is also zig-zag. Sorry I was unclear in the definition. Thank you very much for the references! – Stanley Yao Xiao May 27 '11 at 17:17

I tend to think that it is more unusual when we can count permutations that avoid a given pattern than when we can't.

Consider the case of patterns of length 4. Thanks to the work of Stankova [4] and Backelin, West, and Xin [1], we know that there are essentially three different cases: avoiding 1234, avoiding 1342, and avoiding 1324. The permutations that avoid 1234 correspond to standard Young tableau with at most 3 rows, which allowed Gessel [3] to count them. Note that even in this "nice" case, the generating function is not algebraic, which does not bode well for other patterns. In the 1342 case, there was another fortunate accident in that the "indecomposable" 1342-avoiding permutations are in bijection with "β(0,1) trees", which Bóna [2] proved and used to enumerate this class. As for 1324, it appears that there simply isn't a corresponding happy coincidence.

The case for patterns of length 5 or more is even worse. To the best of my knowledge, the only patterns for which we have formulas are the monotone patterns and the patterns equivalent to monotone patterns. In short, it seems that counting pattern avoiding permutations is always hard, except in a very small number of cases.

[1] Backelin, Jörgen; West, Julian; Xin, Guoce (2007), "Wilf-equivalence for singleton classes", Adv. In Appl. Math. 38 (2): 133–149, doi:10.1016/j.aam.2004.11.006, MR2290807.

[2] Bóna, Miklós (1997), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", J. Combin. Theory Ser. A 80 (2): 257–272, doi:10.1006/jcta.1997.2800, MR1485138.

[3] Gessel, Ira M. (1990), "Symmetric functions and P-recursiveness", J. Combin. Theory Ser. A 53 (2): 257–285, doi:10.1016/0097-3165(90)90060-A, MR1041448.

[4] Stankova, Zvezdelina (1994), "Forbidden subsequences", Discrete Math. 132 (1–3): 291–316, doi:10.1016/0012-365X(94)90242-9, MR1297387.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.