The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A342474 Minimal length of a permutation containing every permutation of length n as a pattern. 0
1, 3, 5, 9, 13, 17 (list; graph; refs; listen; history; text; internal format)



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.


Table of n, a(n) for n=1..6.

Richard Arratia, On the Stanley-Wilf 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], 2020-2021.

Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 4-24, section 6; arXiv preprint, arXiv:1810.08252 [math.CO], 2018-2020.

Henrik Eriksson, Kimmo Eriksson, Svante Linusson, and Johan Wästlund, Dense packing of patterns in a permutation, Ann. Comb., 11 (2007), 459-470.

Alison Miller, Asymptotic bounds for permutations containing many different patterns, J. Combin. Theory Ser. A, 116 (2009), 92-108.


For n=3, the permutation 25314 contains all 6 permutations of length 3, but no shorter permutation does, so a(3)=5.


Cf. A180632, A062714.

Sequence in context: A187569 A181557 A286058 * A076052 A340377 A050556

Adjacent sequences:  A342471 A342472 A342473 * A342475 A342476 A342477




Vincent Vatter, Mar 13 2021



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 09:22 EDT 2021. Contains 348074 sequences. (Running on oeis4.)