A062714 Minimal length of a sequence with terms from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

1, 3, 7, 12, 19, 28, 39

Offset

1,2

Comments

For n >= 7, a(n) <= ceiling(n^2 - (7/3)*n + 19/3) as proved by Radomirovic (2012).

From Jon E. Schoenfield, Jul 27 2009: (Start)

For n > 2, a(n) <= (n-1)^2 + 3, and an easy solution at this upper bound can be obtained by cycling n-3 times through the digits 2 through n and appending the digits 2 and 3 once at the end, inserting a 1 at the beginning and after every n-2 digits thereafter until the last digit is reached, and finally prepending the digits 1 through n. For example:

n=3 (7 digits): 123 1 2 1 3

n=4 (12 digits): 1234 1 23 1 42 1 3

n=5 (19 digits): 12345 1 234 1 523 1 452 1 3

n=6 (28 digits): 123456 1 2345 1 6234 1 5623 1 4562 1 3

n=7 (39 digits): 1234567 1 23456 1 72345 1 67234 1 56723 1 45672 1 3

Equivalently, for n > 2, the i-th digit can be computed as

i for i <= n,

1 for i > n and (i-2) == 0 (mod (n-1)), and

(floor((i-1)*(n-2)/(n-1)) mod (n-1)) + 2 otherwise.

However, the above approach is not always optimal; e.g., at n = 16, it gives a valid solution in (16-1)^2 + 3 = 228 digits, but the following (using the letters a through g for the numbers 10 through 16) is an example of a 227-digit solution:

123456789a bcdefg1234 56789abcde f1g2345678 9abcde1f2g

3456789abc d1e2f3g456 789abc1d2e 3f4g56789a b1c2d3e4f5

g6789a1b2c 3d4e5f6g78 91a2b3c4d5 e6f7g8192a 3b4c5d6e7f

18g293a4b5 c6d17ef82g 394a5b16cd 7ef283g491 56abcd7e2f

3814569abc dg72e13456 89abcdf

(End)

Oliver Tan (2022) proves that for any integer s >= 2, there are infinitely many integers n for which there exists a sequence of length ceiling(n^2 - (5s-3)/(2s-1)*n + (2s^2+9s-7)/(2s-1)) which contains, as a subsequence, all permutations of a set of n symbols. In particular, if s=2, the above yields Radomirovic's expression. With s > 2, it produces shorter sequences than Radomirovic's for larger n. As s approaches infinity, the length approaches ceiling(n^2 - (5/2)*n + C). Formally, for any epsilon > 0, there is a constant C_epsilon such that there are infinitely many integers n for which there exists a sequence of length ceiling(n^2 - (5/2-epsilon)*n + C_epsilon). - Oliver Tan, Jan 22 2022

Links

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

Václav Chvátal, David A. Klarner, and Donald E. Knuth, Selected Combinatorial Research Problems, Stanford University Computer Science Department report STAN-CS-72-292, June 1972, page 26, problem 36 due to R. M. Karp.

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

David Galvin, The n-Part Trilogy Problem

D. J. Kleitman and D. J. Kwiatkowski, A Lower Bound On the Length of a Sequence Containing All Permutations as Subsequences, Journal of Combinatorial Theory, series A, volume 21, number 2, September 1976, pages 129-136.

P. J. Koutas and T. C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.

Malcolm Newey, Notes on a problem involving permutations as subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973.

Sasa Radomirovic, A Construction of Short Sequences Containing All Permutations of a Set as Subsequences, Electronic Journal of Combinatorics 19(4), 2012, P31.

Oliver Tan, Skip Letters for Short Supersequence of All Permutations, arXiv preprint arXiv:2201.06306 [math.CO], 2022.

Przemysław Uznański, All Permutations Supersequence is coNP-complete, arXiv preprint arXiv:1506.05079 [cs.CC], 2015.

Formula

Conjecture: a(n) = Sum_{k=1..n} A049039(k) = A337300(n). - Gerald Hillier, Jun 18 2016

Example

1, 2, 3, 1, 2, 3, 1 contains as a subsequence all of 123, ..., 321 and is minimal, so a(3) = 7.
From John W. Layman, Aug 29 2008: (Start)
The following is a sequence of length a(5)=19 with terms from 1,2,...,5 that contains as subsequences all of the 120 permutations of 1,2,...,5:
{1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,2,3,5,1}
The proof is shown here:
{1,2,3,4,5,-,-,-,-,-,-,-,-,-,-,-,-,-,-}
{1,2,3,-,5,-,-,-,4,-,-,-,-,-,-,-,-,-,-}
{1,2,-,4,-,-,-,3,-,-,5,-,-,-,-,-,-,-,-}
{1,2,-,4,5,-,-,3,-,-,-,-,-,-,-,-,-,-,-}
{1,2,-,-,5,-,-,3,4,-,-,-,-,-,-,-,-,-,-}
{1,2,-,-,5,-,-,-,4,-,-,-,3,-,-,-,-,-,-}
{1,-,3,-,-,-,2,-,4,-,5,-,-,-,-,-,-,-,-}
{1,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,-}
{1,-,3,4,-,-,2,-,-,-,5,-,-,-,-,-,-,-,-}
{1,-,3,4,5,-,2,-,-,-,-,-,-,-,-,-,-,-,-}
{1,-,3,-,5,-,2,-,4,-,-,-,-,-,-,-,-,-,-}
{1,-,3,-,5,-,-,-,4,-,-,2,-,-,-,-,-,-,-}
{1,-,-,4,-,-,2,3,-,-,5,-,-,-,-,-,-,-,-}
{1,-,-,4,-,-,2,-,-,-,5,-,3,-,-,-,-,-,-}
{1,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,-}
{1,-,-,4,-,-,-,3,-,-,5,2,-,-,-,-,-,-,-}
{1,-,-,4,5,-,2,3,-,-,-,-,-,-,-,-,-,-,-}
{1,-,-,4,5,-,-,3,-,-,-,2,-,-,-,-,-,-,-}
{1,-,-,-,5,-,2,3,4,-,-,-,-,-,-,-,-,-,-}
{1,-,-,-,5,-,2,-,4,-,-,-,3,-,-,-,-,-,-}
{1,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,-}
{1,-,-,-,5,-,-,3,4,-,-,2,-,-,-,-,-,-,-}
{1,-,-,-,5,-,-,-,4,-,-,2,3,-,-,-,-,-,-}
{1,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,-}
{-,2,-,-,-,1,-,3,4,-,5,-,-,-,-,-,-,-,-}
{-,2,-,-,-,1,-,3,-,-,5,-,-,-,4,-,-,-,-}
{-,2,-,-,-,1,-,-,4,-,-,-,3,-,-,-,-,5,-}
{-,2,-,-,-,1,-,-,4,-,5,-,3,-,-,-,-,-,-}
{-,2,-,-,-,1,-,-,-,-,5,-,3,-,4,-,-,-,-}
{-,2,-,-,-,1,-,-,-,-,5,-,-,-,4,-,3,-,-}
{-,2,3,-,-,1,-,-,4,-,5,-,-,-,-,-,-,-,-}
{-,2,3,-,-,1,-,-,-,-,5,-,-,-,4,-,-,-,-}
{-,2,3,4,-,1,-,-,-,-,5,-,-,-,-,-,-,-,-}
{-,2,3,4,5,1,-,-,-,-,-,-,-,-,-,-,-,-,-}
{-,2,3,-,5,1,-,-,4,-,-,-,-,-,-,-,-,-,-}
{-,2,3,-,5,-,-,-,4,1,-,-,-,-,-,-,-,-,-}
{-,2,-,4,-,1,-,3,-,-,5,-,-,-,-,-,-,-,-}
{-,2,-,4,-,1,-,-,-,-,5,-,3,-,-,-,-,-,-}
{-,2,-,4,-,-,-,3,-,1,5,-,-,-,-,-,-,-,-}
{-,2,-,4,-,-,-,3,-,-,5,-,-,1,-,-,-,-,-}
{-,2,-,4,5,1,-,3,-,-,-,-,-,-,-,-,-,-,-}
{-,2,-,4,5,-,-,3,-,1,-,-,-,-,-,-,-,-,-}
{-,2,-,-,5,1,-,3,4,-,-,-,-,-,-,-,-,-,-}
{-,2,-,-,5,1,-,-,4,-,-,-,3,-,-,-,-,-,-}
{-,2,-,-,5,-,-,3,-,1,-,-,-,-,4,-,-,-,-}
{-,2,-,-,5,-,-,3,4,1,-,-,-,-,-,-,-,-,-}
{-,2,-,-,5,-,-,-,4,1,-,-,3,-,-,-,-,-,-}
{-,2,-,-,5,-,-,-,4,-,-,-,3,1,-,-,-,-,-}
{-,-,3,-,-,1,2,-,4,-,5,-,-,-,-,-,-,-,-}
{-,-,3,-,-,1,2,-,-,-,5,-,-,-,4,-,-,-,-}
{-,-,3,-,-,1,-,-,4,-,-,2,-,-,-,-,-,5,-}
{-,-,3,-,-,1,-,-,4,-,5,2,-,-,-,-,-,-,-}
{-,-,3,-,-,1,-,-,-,-,5,2,-,-,4,-,-,-,-}
{-,-,3,-,-,1,-,-,-,-,5,-,-,-,4,2,-,-,-}
{-,-,3,-,-,-,2,-,-,1,-,-,-,-,4,-,-,5,-}
{-,-,3,-,-,-,2,-,-,1,5,-,-,-,4,-,-,-,-}
{-,-,3,-,-,-,2,-,4,1,5,-,-,-,-,-,-,-,-}
{-,-,3,-,-,-,2,-,4,-,5,-,-,1,-,-,-,-,-}
{-,-,3,-,-,-,2,-,-,-,5,-,-,1,4,-,-,-,-}
{-,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,1}
{-,-,3,4,-,1,2,-,-,-,5,-,-,-,-,-,-,-,-}
{-,-,3,4,-,1,-,-,-,-,5,2,-,-,-,-,-,-,-}
{-,-,3,4,-,-,2,-,-,1,5,-,-,-,-,-,-,-,-}
{-,-,3,4,-,-,2,-,-,-,5,-,-,1,-,-,-,-,-}
{-,-,3,4,5,1,2,-,-,-,-,-,-,-,-,-,-,-,-}
{-,-,3,4,5,-,2,-,-,1,-,-,-,-,-,-,-,-,-}
{-,-,3,-,5,1,2,-,4,-,-,-,-,-,-,-,-,-,-}
{-,-,3,-,5,1,-,-,4,-,-,2,-,-,-,-,-,-,-}
{-,-,3,-,5,-,2,-,-,1,-,-,-,-,4,-,-,-,-}
{-,-,3,-,5,-,2,-,4,1,-,-,-,-,-,-,-,-,-}
{-,-,3,-,5,-,-,-,4,1,-,2,-,-,-,-,-,-,-}
{-,-,3,-,5,-,-,-,4,-,-,2,-,1,-,-,-,-,-}
{-,-,-,4,-,1,2,3,-,-,5,-,-,-,-,-,-,-,-}
{-,-,-,4,-,1,2,-,-,-,5,-,3,-,-,-,-,-,-}
{-,-,-,4,-,1,-,3,-,-,-,2,-,-,-,-,-,5,-}
{-,-,-,4,-,1,-,3,-,-,5,2,-,-,-,-,-,-,-}
{-,-,-,4,-,1,-,-,-,-,5,2,3,-,-,-,-,-,-}
{-,-,-,4,-,1,-,-,-,-,5,-,3,-,-,2,-,-,-}
{-,-,-,4,-,-,2,-,-,1,-,-,3,-,-,-,-,5,-}
{-,-,-,4,-,-,2,-,-,1,5,-,3,-,-,-,-,-,-}
{-,-,-,4,-,-,2,3,-,1,5,-,-,-,-,-,-,-,-}
{-,-,-,4,-,-,2,3,-,-,5,-,-,1,-,-,-,-,-}
{-,-,-,4,-,-,2,-,-,-,5,-,-,1,-,-,3,-,-}
{-,-,-,4,-,-,2,-,-,-,5,-,3,1,-,-,-,-,-}
{-,-,-,4,-,-,-,3,-,1,-,2,-,-,-,-,-,5,-}
{-,-,-,4,-,-,-,3,-,1,5,2,-,-,-,-,-,-,-}
{-,-,-,4,-,-,-,3,-,-,-,2,-,1,-,-,-,5,-}
{-,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,1}
{-,-,-,4,-,-,-,3,-,-,5,-,-,1,-,2,-,-,-}
{-,-,-,4,-,-,-,3,-,-,5,2,-,1,-,-,-,-,-}
{-,-,-,4,5,1,2,3,-,-,-,-,-,-,-,-,-,-,-}
{-,-,-,4,5,1,-,3,-,-,-,2,-,-,-,-,-,-,-}
{-,-,-,4,5,-,2,-,-,1,-,-,3,-,-,-,-,-,-}
{-,-,-,4,5,-,2,3,-,1,-,-,-,-,-,-,-,-,-}
{-,-,-,4,5,-,-,3,-,1,-,2,-,-,-,-,-,-,-}
{-,-,-,4,5,-,-,3,-,-,-,2,-,1,-,-,-,-,-}
{-,-,-,-,5,1,2,3,4,-,-,-,-,-,-,-,-,-,-}
{-,-,-,-,5,1,2,-,4,-,-,-,3,-,-,-,-,-,-}
{-,-,-,-,5,1,-,3,-,-,-,2,-,-,4,-,-,-,-}
{-,-,-,-,5,1,-,3,4,-,-,2,-,-,-,-,-,-,-}
{-,-,-,-,5,1,-,-,4,-,-,2,3,-,-,-,-,-,-}
{-,-,-,-,5,1,-,-,4,-,-,-,3,-,-,2,-,-,-}
{-,-,-,-,5,-,2,-,-,1,-,-,3,-,4,-,-,-,-}
{-,-,-,-,5,-,2,-,-,1,-,-,-,-,4,-,3,-,-}
{-,-,-,-,5,-,2,3,-,1,-,-,-,-,4,-,-,-,-}
{-,-,-,-,5,-,2,3,4,1,-,-,-,-,-,-,-,-,-}
{-,-,-,-,5,-,2,-,4,1,-,-,3,-,-,-,-,-,-}
{-,-,-,-,5,-,2,-,4,-,-,-,3,1,-,-,-,-,-}
{-,-,-,-,5,-,-,3,-,1,-,2,-,-,4,-,-,-,-}
{-,-,-,-,5,-,-,3,-,1,-,-,-,-,4,2,-,-,-}
{-,-,-,-,5,-,-,3,-,-,-,2,-,1,4,-,-,-,-}
{-,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,1}
{-,-,-,-,5,-,-,3,4,1,-,2,-,-,-,-,-,-,-}
{-,-,-,-,5,-,-,3,4,-,-,2,-,1,-,-,-,-,-}
{-,-,-,-,5,-,-,-,4,1,-,2,3,-,-,-,-,-,-}
{-,-,-,-,5,-,-,-,4,1,-,-,3,-,-,2,-,-,-}
{-,-,-,-,5,-,-,-,4,-,-,2,-,1,-,-,3,-,-}
{-,-,-,-,5,-,-,-,4,-,-,2,3,1,-,-,-,-,-}
{-,-,-,-,5,-,-,-,4,-,-,-,3,1,-,2,-,-,-}
{-,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,1}
(End)

Mathematica

NextTuple[x_, n_, l_] := Module[{i, x0 = x},
   If[x0 == ConstantArray[n, l], Return[{}]];
   For[i = l, i >= 1, i--,
    If[x0[[i]] < n, x0[[i]]++; Return[x0], x0[[i]] = 1]]];
Join[{1}, Table[p = Permutations[Range[n], {n}];
  For[tl = n + 1, tl <= 50, tl++,
   tup = ConstantArray[1, tl];
   While[tup = NextTuple[tup, n, tl]; tup != {},
    If[Product[Count[tup, i], {i, 1, n}] == 0, Continue[]];
    For[j = 1, j <= Length[p], j++,
     perm = p[[j]]; lst = tup; fnd = True;
     For[k = 1, k <= Length[perm], k++,
      If[lst == {}, fnd = False; Break[]];
      p1 = Position[lst, perm[[k]], 1, 1];
      If[Length[p1] == 0, fnd = False; Break[]];
      p1 = First@First@p1;
      If[! IntegerQ[p1], fnd = False; Break[]];
      lst = Drop[lst, p1];
      ]; If[! fnd, Break[]]]; If[fnd, Break[]]]; If[fnd, Break[]]];
tl, {n, 2, 5}]](* Robert Price, Oct 13 2019 *)

Crossrefs

Cf. A136094 (smallest sequences), A351468 (Newey's sequences).

Cf. A337300 (conjectured values).

Cf. A180632 (superpermutations), A348574 (subset substrings).

Sequence in context: A022791 A025742 A122793 * A337300 A039677 A011899

Adjacent sequences: A062711 A062712 A062713 * A062715 A062716 A062717

Keyword

nonn,nice,more

Author

N. J. A. Sloane, Jul 14 2001

Extensions

a(5) = 19 from John W. Layman, Aug 29 2008

a(5)-a(7) are computed by Newey 1973, added by Max Alekseyev, Apr 16 2013

Status

approved