Picture of person typing on laptop with programming code visible on the laptop screen

World class computing and information science research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by researchers from the Department of Computer & Information Sciences involved in mathematically structured programming, similarity and metric search, computer security, software systems, combinatronics and digital health.

The Department also includes the iSchool Research Group, which performs leading research into socio-technical phenomena and topics such as information retrieval and information seeking behaviour.

Explore

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.