|
%I #15 Mar 26 2021 12:55:01
%S 1,3,5,9,13,17
%N Minimal length of a permutation containing every permutation of length n as a pattern.
%C These permutations are sometimes called "superpatterns".
%C A upper bound is ceiling((n^2+1)/2), see Engen and Vatter. A simple lower bound is n^2/e^2, which has been improved to 1.000076 n^2/e^2 by Chroman, Kwan, and Singhal.
%H Richard Arratia, <a href="https://doi.org/10.37236/1477">On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern</a>, Electron. J. Combin., 6 (1999), Note 1, 4 pp.
%H Zachary Chroman, Matthew Kwan, and Mihir Singhal, <a href="https://arxiv.org/abs/2004.02375">Lower bounds for superpatterns and universal sequences</a>, arXiv:2004.02375 [math.CO], 2020-2021.
%H Michael Engen and Vincent Vatter, <a href="https://doi.org/10.1080/00029890.2021.1835384">Containing all permutations</a>, Amer. Math. Monthly, 128 (2021), 4-24, section 6; <a href="https://arxiv.org/abs/1810.08252">arXiv preprint</a>, arXiv:1810.08252 [math.CO], 2018-2020.
%H Henrik Eriksson, Kimmo Eriksson, Svante Linusson, and Johan Wästlund, <a href="https://doi.org/10.1007/s00026-007-0329-7">Dense packing of patterns in a permutation</a>, Ann. Comb., 11 (2007), 459-470.
%H Alison Miller, <a href="https://doi.org/10.1016/j.jcta.2008.04.007">Asymptotic bounds for permutations containing many different patterns</a>, J. Combin. Theory Ser. A, 116 (2009), 92-108.
%e For n=3, the permutation 25314 contains all 6 permutations of length 3, but no shorter permutation does, so a(3)=5.
%Y Cf. A180632, A062714.
%K nonn,more
%O 1,2
%A _Vincent Vatter_, Mar 13 2021
|
