"Counting pattern avoiding permutations via integral operators"

Richard Ehrenborg
University of Kentucky

Monday, September 12, 2005
3:00 pm, 845 Patterson Office Tower

Abstract:

A consecutive 123-avoiding (respectively 213-avoiding) permutation is a permutation &pi = (&pi(1),...,&pi(n)) in the symmetric group on n-elements with the property that no sequence of the form &pi(i) < &pi(i+1) < &pi(i+2) (respectively &pi(i+1) < &pi(i) < &pi(i+2)) occurs. The goal is to obtain asymptotics for the number of 123- and 213-avoiding permutations (and other classes of pattern-avoiding permutations) as n tend to infinity. We develop a general method which solves this counting problem using the spectral theory of integral operators on L^{2}[0,1]^{m} where m+1 is the length of the pattern. Our methods give detailed asymptotic expansions and allow for explicit computation of leading terms in many cases.

This is work in progress and joint work with Sergey Kitaev and Peter Perry.