Picture of a sphere with binary code

Making Strathclyde research discoverable to the world...

The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs. It exposes Strathclyde's world leading Open Access research to many of the world's leading resource discovery tools, and from there onto the screens of researchers around the world.

Explore Strathclyde Open Access research content

Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns

Claesson, Anders and Jelínek, Vít and Steingrimsson, Einar (2012) Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. Journal of Combinatorial Theory Series A, 119 (8). pp. 1680-1691. ISSN 0097-3165

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

We prove that the Stanley-Wilf limit of any layered permutation pattern of length l is at most 4l(2), and that the Stanley-Wilf limit of the pattern 1324 is at most 16. These bounds follow from a more general result showing that a permutation avoiding a pattern of a special form is a merge of two permutations, each of which avoids a smaller pattern. We also conjecture that, for any k >= 0, the set of 1324-avoiding permutations with k inversions contains at least as many permutations of length n + 1 as those of length n. We show that if this is true then the Stanley-Wilf limit for 1324 is at most e(pi root 2/3) similar or equal to 13.001954.