## Restricted Permutations

Two sequences *x,y* of the same length are order isomorphic if *x
*_{i}
< x_{j} if and only if *y
*_{i} < y
_{j}.
If *u* and *v* are permutations then
*u* is said to be *involved* in *v* if *v* has a
subsequence order isomorphic to *u*. If *u* is not involved in
*v* then *v* is said to *avoid* *u*.

This partial order on permutations arises in many contexts.
The natural objects of study are *pattern classes*, classes
of permutations which are closed downwards with respect to involvement. The archetypal example of a pattern
class is the set of all *stack permutations* -- those permutations
which can be generated by the operations `push` and
`pop`
of a stack.

Every pattern class defines and is defined by a unique
*basis*:- a set of permutations which are minimal with respect
to not belonging to the class. A fundamental question about any
pattern class is: does it have a finite basis? For example, the
class of stack permutations does have a finite basis, viz {312}.

My colleagues and I have found a large number of finite basis results and
developed a set of techniques that provide a framework for finding others.

The other fundamental question is an enumerative one:
finding formulae for the number of permutations of each length
in a pattern class. We have developed a number of generating function
techniques that allow this to be done for many pattern classes.
If you want to know the number of permutations that avoid a given
set of restrictions try this Java 1.2 applet. If your browser supports it then this Java 1.5 applet is much better.

Restricted permutations were first studied by Computer Scientists
in the 1960s and 1970s. After a decade of neglect their study was
revived by combinatorialists and has now become very active. The
first of an annual series of conferences on permutation patterns
was held here at Otago in 2003. Subsequent conferences were held at Nanaimo in Canada (2004), Gainesville, Florida (2005), Reyjavik (2006), St Andrews (2007), Otago (2008), Florence (2009), Dartmouth (2010), San Luis Obispo (2011) and Strathclyde (2012).