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

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:119

Article

Claesson, Anders¹  Jelinek, Vit²  Steingrimsson, Einar¹ 

[1] Univ Strathclyde, Dept Comp & Informat Sci, Glasgow G1 1XH, Lanark, Scotland

[2] Charles Univ Prague, Fac Math & Phys, Inst Comp Sci, Prague 11800 1, Czech Republic

关键词: Pattern avoidance;    Stanley-Wilf limit;    Layered permutations;   

DOI  :  10.1016/j.jcta.2012.05.006

来源: Elsevier

【 摘 要 】

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. (C) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free