Permutations all of whose patterns of a given length are distinct

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Hegarty, Peter^1,2 

[1] Chalmers Univ Technol, Dept Math Sci, S-41296 Gothenburg, Sweden

[2] Univ Gothenburg, Dept Math Sci, Gothenburg, Sweden

关键词: Permutation pattern;    k-Separator;    Tilted checkerboard permutation;   

DOI  :  10.1016/j.jcta.2013.06.006

来源: Elsevier

【 摘 要 】

For each integer k >= 2, let F(k) denote the largest n for which there exists a permutation sigma is an element of S-n all of whose patterns of length k are distinct. We prove that F (k) = k + left perpendicular root 2k - 3right perpendicular + epsilon(k), where epsilon(k) is an element of {-1, 0} for every k. We conjecture an even more precise result, based on data for small values of k. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free