Restricted Permutations

Two sequences x,y of the same length are order isomorphic if x i < xj 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).