Journal of Combinatorics

Volume 2 (2011)

Number 3

A spectral approach to consecutive pattern-avoiding permutations

Pages: 305 – 353



Richard Ehrenborg (Department of Mathematics, University of Kentucky, Lexington, Ky., U.S.A.)

Sergey Kitaev (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Peter Perry (Department of Mathematics, University of Kentucky, Lexington, Ky., U.S.A.)


We consider the problem of enumerating permutations in the symmetricgroup on $n$ elements which avoid a given set of consecutive patterns$S$, and in particular computing asymptotics as $n$ tends toinfinity. We develop a general method which solves this enumerationproblem using the spectral theory of integral operators on$L^{2}([0,1]^{m})$, where the patterns in $S$ have length $m+1$.Kre\u{\i}n and Rutman’s generalization of the Perron–Frobeniustheory of non-negative matrices plays a central role. Our methodsgive detailed asymptotic expansions and allow for explicitcomputation of leading terms in many cases.As a corollary to our results,we settle a conjecture of Warlimont on asymptotics for the number ofpermutations avoiding a consecutive pattern.

Full Text (PDF format)