# Constructing permutations avoiding a pattern

See here for some theory.

It is fairly easy to explicitly generate all permutations of $$n$$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but can I do the same for pattern-avoiding? E.g. consider all permutations that avoid both $$[1,2,3]$$ and $$[3,2,1]$$, then the set even for any $$n$$ is finite, as already for $$n=5$$ none exists. But it's probably not that easy in general...

Note that I don't care for an enumeration for arbitrarily large $$n$$ (haaaard, see link) but for an effective algorithm for medium $$n$$ (say, directly creating $$<10^9$$ permutations that avoid the pattern[s] for $$n=20$$, instead of checking $$20!$$ permutations for validity). A partial result (like "combining pattern foo and bar makes the set empty for large $$n$$") would be nice too.

• Look up "generating trees". For an early reference on this topic, see e.g. "Generating trees and forbidden subsequences" by Julian West. – Alexander Burstein Apr 7 at 16:39

As far as "combining pattern foo and bar makes the set empty for large $$n$$", there is an answer and it is fairly trivial. There are no permutations of length longer than $$(k-1)(\ell-1)+1$$ that avoid both $$12\cdots k$$ and $$\ell\cdots 21$$ by the Erdős–Szekeres theorem. On the other hand, given any set $$B$$ of patterns, if $$B$$ does not contain an increasing pattern, then all decreasing permutations will avoid every pattern in $$B$$. Similarly, if $$B$$ does not include a decreasing pattern, then all increasing permutations will avoid every pattern in it. Thus there are arbitrarily long $$B$$-avoiding permutations if and only if $$B$$ doesn't contain both an increasing pattern and a decreasing pattern.
As for constructing all pattern-avoiding permutations of "reasonable" length, there has been some thought spent on this. Alex points out that there is an approach called "generating trees" that was used in the 90s, both for constructing these permutations and for counting them. The very basic idea is that if you have a list of all pattern-avoiding permutations of length $$n-1$$, then you can get the pattern-avoiding permutations of length $$n$$ by inserting $$n$$ somewhere in those. The less basic version is that you can keep track of which insertions "failed" earlier on, and not try them again. The advanced version is that for certain sets of patterns, there is a pattern to the allowable places for insertions, and this can let you construct those permutations quickly, or even enumerate them without constructing them. But that's only if you get lucky and there is a nice pattern.
• The approach used in PermLab and in all the other bits of software that I'm aware of focus on generating all the permutations of a given length avoiding a pattern. The problem of course is that this can only work so long as that number is reasonably small. The main question is whether you store all the permutations of length $k$ to generate those of $k+1$ (much quicker in time, but memory-expensive) which is Kuszmaul's approach or use a tree (which with depth-first traversal requires very little memory). – Michael Albert Apr 8 at 19:21