Colloquium

The patterns of permutations

by Herbert S. Wilf, Thomas A. Scott Professor of Mathematics, University of Pennsylvania, Philadelphia

Abstract

Permutation patterns are a very active research area just now. Ifg is a fixed permutation of k letters, then a permutation f, of n letters,is said to contain the pattern g is there is a subsequence of k values of fwhose pairwise size comparisons all agree with the corresponding ones of g.The main problems are counting the permutations that avoid a given pattern,or the maximum number of times a pattern can be contained in ann-permutation, etc. We'll survey some recent progress, present some newresults and raise some questions for study.