Vincent Vatter - cp's OEIS frontend

A342474 Minimal length of a permutation containing every permutation of length n as a pattern.

1, 3, 5, 9, 13, 17

Offset: 1

Vincent Vatter, Mar 13 2021

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.

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

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.

Cf. A180632, A062714.

A256181 The number of permutations of length n sortable by 3 block interchanges.

Original entry on oeis.org

1, 2, 6, 24, 120, 720, 5040, 32256, 169632, 737364, 2731444, 8875868, 25894376, 69053375, 170694383, 395443223, 866147111, 1806459866, 3608498678, 6937282452, 12887902732, 23216767894, 40675018726, 69480583966, 115975600846, 189528370396, 303753983092

Offset: 1

Vincent Vatter, Apr 03 2015

			The shortest permutations that cannot be sorted by 3 block interchanges are of length 8.

Colin Barker, Table of n, a(n) for n = 1..1000
D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 2013-2015.
Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).

Cf. A145126, A228401.

Vec(x*(1-11*x+58*x^2-184*x^3+419*x^4-541*x^5+1608*x^6-270*x^7+567*x^8-217*x^9+66*x^10-12*x^11+x^12)/(1-x)^13 + O(x^30)) \\ Colin Barker, Dec 15 2015

G.f.: -x * (x^12 -12*x^11 +66*x^10 -217*x^9 +567*x^8 -270*x^7 +1608*x^6 -541*x^5 +419*x^4 -184*x^3 +58*x^2 -11*x +1) / (x^13 -13*x^12 +78*x^11 -286*x^10 +715*x^9 -1287*x^8 +1716*x^7 -1716*x^6 +1287*x^5 -715*x^4 +286*x^3 -78*x^2 +13*x -1).

A228396 The number of permutations of length n sortable by 2 reversals.

Original entry on oeis.org

1, 1, 2, 6, 22, 63, 145, 288, 516, 857, 1343, 2010, 2898, 4051, 5517, 7348, 9600, 12333, 15611, 19502, 24078, 29415, 35593, 42696, 50812, 60033, 70455, 82178, 95306, 109947, 126213, 144220, 164088, 185941, 209907, 236118, 264710, 295823, 329601, 366192, 405748

Offset: 0

Vincent Vatter, Aug 21 2013

			There are 2 permutations of length 4 which cannot be sorted by 2 reversals.

C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.
G. A. Watterson, W. J. Ewens, T. E. Hall, and A. Morgan, The chromosome inversion problem, Journal of Theoretical Biology, 99 (1982), 1-7.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000124, A228397.

CoefficientList[Series[(1/x) (-1 - (x^7 - x^6 - 3 x^5 + 7 x^4 - 4 x^3 + 7 x^2 - 4 x + 1)/(x - 1)^5), {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)
LinearRecurrence[{5,-10,10,-5,1},{1,2,6,22,63,145,288},40] (* Harvey P. Dale, Mar 08 2019 *)

G.f.: -(x^7 - x^6 - 3*x^5 + 7*x^4 - 4*x^3 + 7*x^2 - 4*x + 1)/(x - 1)^5.

a(n) = 8 + n*(n^3 -2*n^2 +2*n -19)/6 for n>2, a(1)=1, a(2)=2. [Bruno Berselli, Aug 22 2013]

a(0)=1 prepended by Alois P. Heinz, Mar 31 2025

A228398 The number of permutations of length n sortable by 3 prefix reversals (in the pancake sorting sense).

Original entry on oeis.org

1, 2, 6, 21, 52, 105, 186, 301, 456, 657, 910, 1221, 1596, 2041, 2562, 3165, 3856, 4641, 5526, 6517, 7620, 8841, 10186, 11661, 13272, 15025, 16926, 18981, 21196, 23577, 26130, 28861, 31776, 34881, 38182, 41685, 45396, 49321, 53466, 57837, 62440, 67281, 72366

Offset: 1

Vincent Vatter, Aug 21 2013

Essentially the same as A069778.

			There are only 3 permutations of length 4 which cannot be sorted by 3 pancake reversals.

H. Dweighter, Elementary problems and solutions, problem E2569. Amer. Math. Monthly 82 (1975), 1010.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.

Cf. A000027, A002522.

CoefficientList[Series[(1/x) (-1 + (x^6 - 3 x^5 + 6 x^4 + 4 x^2 - 3 x + 1)/(x - 1)^4), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *)

G.f.: -1 + (x^6 - 3*x^5 + 6*x^4 + 4*x^2 - 3*x + 1)/(x - 1)^4.

a(n) = (n-1)*(n^2-3*n+3) for n>2, a(1)=1, a(2)=2. [Bruno Berselli, Aug 22 2013]

A228394 The number of permutations of length n sortable by 2 prefix block transpositions.

Original entry on oeis.org

1, 2, 6, 21, 61, 146, 302, 561, 961, 1546, 2366, 3477, 4941, 6826, 9206, 12161, 15777, 20146, 25366, 31541, 38781, 47202, 56926, 68081, 80801, 95226, 111502, 129781, 150221, 172986, 198246, 226177, 256961, 290786, 327846, 368341, 412477, 460466, 512526, 568881

Offset: 1

Vincent Vatter, Aug 21 2013

			There are 3 permutations of length 4 that cannot be sorted by 2 prefix block transpositions.

Z. Dias and J. Meidanis, Sorting by prefix transpositions, In Proceedings of the 9th International Symposium on String Processing and Information Retrieval (London, UK, UK, 2002), SPIRE 2002, Springer-Verlag, pp. 65-76.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A000124, A228395.

CoefficientList[Series[(1/x) (-1 - (x^2 + 1) (6 x^2 - 4 x + 1)/(x - 1)^5), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *)
LinearRecurrence[{5,-10,10,-5,1},{1,2,6,21,61},40] (* Harvey P. Dale, May 28 2018 *)

G.f.: -1 -(x^2 + 1)*(6*x^2 - 4*x + 1)/(x - 1)^5.

a(n) = 1 + (n-1)*n*(3*n^2-11*n+16)/12. [Bruno Berselli, Aug 22 2013]

A228397 The number of permutations of length n sortable by 3 reversals.

Original entry on oeis.org

1, 2, 6, 24, 118, 534, 1851, 5158, 12264, 25943, 50214, 90656, 154758, 252304, 395793, 600894, 886936, 1277433, 1800644, 2490168, 3385574, 4533066, 5986183, 7806534, 10064568, 12840379, 16224546, 20319008, 25237974, 31108868, 38073309, 46288126, 55926408

Offset: 1

Vincent Vatter, Aug 21 2013

			There are 2 permutations of length 5 which cannot be sorted by 3 reversals.

C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.
G. A. Watterson, W. J. Ewens, T. E. Hall, and A. Morgan, The chromosome inversion problem, Journal of Theoretical Biology, 99 (1982), 1-7.

Cf. A000124, A228396.

CoefficientList[Series[(1/x) (-1 - (2 x^10 + 5 x^9 + 12 x^8 - 75 x^7 + 58 x^6 + 20 x^5 + 24 x^4 - 22 x^3 + 16 x^2 - 6 x + 1)/(x - 1)^7), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *)

G.f.: -1 -(2*x^10 + 5*x^9 + 12*x^8 - 75*x^7 + 58*x^6 + 20*x^5 + 24*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.

a(n) = n! for 0 < n < 4; for n > 3, a(n) = 318 + n*(7*n^5 -21*n^4 -125*n^3 -819*n^2 +12862*n -42720)/144. [Bruno Berselli, Aug 22 2013]

A228399 The number of permutations of length n sortable by 2 cut-and-paste moves.

Original entry on oeis.org

1, 2, 6, 24, 120, 577, 2208, 6768, 17469, 39603, 81272, 154225, 274802, 464985, 753556, 1177362, 1782687, 2626731, 3779196, 5323979, 7360972, 10007969, 13402680, 17704852, 23098497, 29794227, 38031696, 48082149, 60251078, 74880985, 92354252, 113096118

Offset: 1

Vincent Vatter, Aug 21 2013

			The shortest permutations which cannot be sorted by 2 cut-and-paste moves are of length 6.

D. W. Cranston, I. H. Sudborough, and D. B. West, Short proofs for cut-and-paste sorting of permutations, Discrete Math. 307, 22 (2007), 2866-2870.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.

Cf. A060354, A228400.

CoefficientList[Series[(1/x) (-1 + (x^11 - 5 x^10 - 2 x^9 + 44 x^8 - 23 x^7 - 87 x^6 - 22 x^5 - 24 x^4 + 22 x^3 - 16 x^2 + 6 x - 1)/(x - 1)^7), {x,
   0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)

G.f.: -1 + (x^11 - 5*x^10 - 2*x^9 + 44*x^8 - 23*x^7 - 87*x^6 - 22*x^5 - 24*x^4 + 22*x^3 - 16*x^2 + 6*x - 1)/(x - 1)^7.

a(n) = n! for 0 < n < 5; for n > 4, a(n) = -18 + n*(107*n^5 -1077*n^4 +2225*n^3 +12345*n^2 -61732*n +80532)/720. [Bruno Berselli, Aug 22 2013]

A228393 The number of permutations of length n that can be sorted by 3 block transpositions.

Original entry on oeis.org

1, 2, 6, 24, 120, 675, 3527, 15484, 56917, 179719, 500864, 1260117, 2913132, 6274230, 12726573, 24521243, 45190897, 80108200, 137224138, 228026582, 368765112, 581994117, 898492563, 1359625566, 2020220021, 2952034021, 4247907652, 6026690971, 8439053564

Offset: 1

Vincent Vatter, Aug 21 2013

			The shortest permutations which cannot be sorted by 3 block transpositions are of length 6.

V. Bafna and P.A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11, 2 (1998), 224-240.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv:1410.2657 [math.CO], 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv:1308.4946 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).

Cf. A000292, A228392.

CoefficientList[Series[-(x^9 - 9 x^8 - 17 x^7 - 263 x^6 - 3 x^5 - 120 x^4 + 66 x^3 - 31 x^2 + 8 x - 1)/(x - 1)^10, {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)

G.f.: -x*(x^9 - 9*x^8 - 17*x^7 - 263*x^6 - 3*x^5 - 120*x^4 + 66*x^3 - 31*x^2 + 8*x - 1)/(x - 1)^10.

A228392 The number of permutations of length n sortable by 2 block transpositions.

Original entry on oeis.org

1, 2, 6, 23, 89, 295, 827, 2017, 4405, 8812, 16424, 28887, 48413, 77897, 121045, 182513, 268057, 384694, 540874, 746663, 1013937, 1356587, 1790735, 2334961, 3010541, 3841696, 4855852, 6083911, 7560533, 9324429, 11418665, 13890977, 16794097, 20186090, 24130702, 28697719, 33963337, 40010543

Offset: 1

Vincent Vatter, Aug 21 2013

			The shortest permutation which cannot be sorted by 2 block transpositions is of length 4.

V. Bafna and P.A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11, 2 (1998), 224-240.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv:1410.2657 [math.CO], 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv:1308.4946 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A000292, A228393.

Vec(-1-(x^6-2*x^5+23*x^4-22*x^3+16*x^2-6*x+1)/(x-1)^7 + O(x^50)) \\ Michel Marcus, Apr 03 2015

G.f.: -1 -(x^6 - 2*x^5 + 23*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.

A228401 The number of permutations of length n sortable by 2 block interchanges.

Original entry on oeis.org

1, 2, 6, 24, 120, 540, 1996, 6196, 16732, 40459, 89519, 184185, 356721, 656475, 1156443, 1961563, 3219019, 5130856, 7969228, 12094622, 17977422, 26223198, 37602126, 53082966, 73872046, 101457721, 137660797, 184691431, 245213039, 322413765, 420086085, 542715141

Offset: 1

Vincent Vatter, Aug 21 2013

			The shortest permutations that cannot be sorted by 2 block interchanges are of length 7.

Matthew House, Table of n, a(n) for n = 1..10000
D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A145126, A256181.

CoefficientList[Series[-(x^8 - 8 x^7 + 28 x^6 - 54 x^5 + 78 x^4 - 42 x^3 + 24 x^2 - 7 x + 1)/(x - 1)^9, {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)
LinearRecurrence[{9,-36,84,-126,126,-84,36,-9,1},{1,2,6,24,120,540,1996,6196,16732},40] (* Harvey P. Dale, Dec 31 2019 *)

G.f.: -x*(x^8 -8*x^7 +28*x^6 -54*x^5 +78*x^4 -42*x^3 +24*x^2 -7*x +1)/(x-1)^9.

a(n) = 1 + n*(n-1)*(n+1)*(n+2)*(3*n^4-10*n^3-11*n^2+50*n+216)/5760. [Bruno Berselli, Aug 22 2013]

cp's OEIS Frontend

User: Vincent Vatter

A342474 Minimal length of a permutation containing every permutation of length n as a pattern.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A256181 The number of permutations of length n sortable by 3 block interchanges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A228396 The number of permutations of length n sortable by 2 reversals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A228398 The number of permutations of length n sortable by 3 prefix reversals (in the pancake sorting sense).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A228394 The number of permutations of length n sortable by 2 prefix block transpositions.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A228397 The number of permutations of length n sortable by 3 reversals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A228399 The number of permutations of length n sortable by 2 cut-and-paste moves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A228393 The number of permutations of length n that can be sorted by 3 block transpositions.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs