
COMMENTS

These permutations are sometimes called "superpatterns".
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.


LINKS

Table of n, a(n) for n=1..6.
Richard Arratia, On the StanleyWilf conjecture for the number of permutations avoiding a given pattern, Electron. J. Combin., 6 (1999), Note 1, 4 pp.
Zachary Chroman, Matthew Kwan, and Mihir Singhal, Lower bounds for superpatterns and universal sequences, arXiv:2004.02375 [math.CO], 20202021.
Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 424, section 6; arXiv preprint, arXiv:1810.08252 [math.CO], 20182020.
Henrik Eriksson, Kimmo Eriksson, Svante Linusson, and Johan Wästlund, Dense packing of patterns in a permutation, Ann. Comb., 11 (2007), 459470.
Alison Miller, Asymptotic bounds for permutations containing many different patterns, J. Combin. Theory Ser. A, 116 (2009), 92108.
