|
%I #112 Mar 09 2022 21:15:55
%S 1,3,7,12,19,28,39
%N 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.
%C For n >= 7, a(n) <= ceiling(n^2 - (7/3)*n + 19/3) as proved by Radomirovic (2012).
%C From _Jon E. Schoenfield_, Jul 27 2009: (Start)
%C 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:
%C n=3 (7 digits): 123 1 2 1 3
%C n=4 (12 digits): 1234 1 23 1 42 1 3
%C n=5 (19 digits): 12345 1 234 1 523 1 452 1 3
%C n=6 (28 digits): 123456 1 2345 1 6234 1 5623 1 4562 1 3
%C n=7 (39 digits): 1234567 1 23456 1 72345 1 67234 1 56723 1 45672 1 3
%C Equivalently, for n > 2, the i-th digit can be computed as
%C i for i <= n,
%C 1 for i > n and (i-2) == 0 (mod (n-1)), and
%C (floor((i-1)*(n-2)/(n-1)) mod (n-1)) + 2 otherwise.
%C 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:
%C 123456789a bcdefg1234 56789abcde f1g2345678 9abcde1f2g
%C 3456789abc d1e2f3g456 789abc1d2e 3f4g56789a b1c2d3e4f5
%C g6789a1b2c 3d4e5f6g78 91a2b3c4d5 e6f7g8192a 3b4c5d6e7f
%C 18g293a4b5 c6d17ef82g 394a5b16cd 7ef283g491 56abcd7e2f
%C 3814569abc dg72e13456 89abcdf
%C (End)
%C 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
%H Václav Chvátal, David A. Klarner, and Donald E. Knuth, <a href="http://infolab.stanford.edu/TR/CS-TR-72-292.html">Selected Combinatorial Research Problems</a>, Stanford University Computer Science Department report STAN-CS-72-292, June 1972, page 26, problem 36 due to R. M. Karp.
%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 4; <a href="https://arxiv.org/abs/1810.08252">arXiv preprint</a>, arXiv:1810.08252 [math.CO], 2018-2020.
%H David Galvin, <a href="http://web.archive.org/web/20031012174723/http://www.rci.rutgers.edu/~dgalvin/research/sequences.html">The n-Part Trilogy Problem</a>
%H D. J. Kleitman and D. J. Kwiatkowski, <a href="https://doi.org/10.1016/0097-3165(76)90057-1">A Lower Bound On the Length of a Sequence Containing All Permutations as Subsequences</a>, Journal of Combinatorial Theory, series A, volume 21, number 2, September 1976, pages 129-136.
%H P. J. Koutas and T. C. Hu, <a href="http://dx.doi.org/10.1016/0012-365X(75)90004-7">Shortest String Containing All Permutations</a>, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.
%H Malcolm Newey, <a href="http://infolab.stanford.edu/TR/CS-TR-73-340.html">Notes on a problem involving permutations as subsequences</a>, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973.
%H Sasa Radomirovic, <a href="https://doi.org/10.37236/2859">A Construction of Short Sequences Containing All Permutations of a Set as Subsequences</a>, Electronic Journal of Combinatorics 19(4), 2012, P31.
%H Oliver Tan, <a href="https://arxiv.org/abs/2201.06306">Skip Letters for Short Supersequence of All Permutations</a>, arXiv preprint arXiv:2201.06306 [math.CO], 2022.
%H Przemysław Uznański, <a href="http://arxiv.org/abs/1506.05079">All Permutations Supersequence is coNP-complete</a>, arXiv preprint arXiv:1506.05079 [cs.CC], 2015.
%F Conjecture: a(n) = Sum_{k=1..n} A049039(k) = A337300(n). - _Gerald Hillier_, Jun 18 2016
%e 1, 2, 3, 1, 2, 3, 1 contains as a subsequence all of 123, ..., 321 and is minimal, so a(3) = 7.
%e From _John W. Layman_, Aug 29 2008: (Start)
%e 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:
%e {1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,2,3,5,1}
%e The proof is shown here:
%e {1,2,3,4,5,-,-,-,-,-,-,-,-,-,-,-,-,-,-}
%e {1,2,3,-,5,-,-,-,4,-,-,-,-,-,-,-,-,-,-}
%e {1,2,-,4,-,-,-,3,-,-,5,-,-,-,-,-,-,-,-}
%e {1,2,-,4,5,-,-,3,-,-,-,-,-,-,-,-,-,-,-}
%e {1,2,-,-,5,-,-,3,4,-,-,-,-,-,-,-,-,-,-}
%e {1,2,-,-,5,-,-,-,4,-,-,-,3,-,-,-,-,-,-}
%e {1,-,3,-,-,-,2,-,4,-,5,-,-,-,-,-,-,-,-}
%e {1,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,-}
%e {1,-,3,4,-,-,2,-,-,-,5,-,-,-,-,-,-,-,-}
%e {1,-,3,4,5,-,2,-,-,-,-,-,-,-,-,-,-,-,-}
%e {1,-,3,-,5,-,2,-,4,-,-,-,-,-,-,-,-,-,-}
%e {1,-,3,-,5,-,-,-,4,-,-,2,-,-,-,-,-,-,-}
%e {1,-,-,4,-,-,2,3,-,-,5,-,-,-,-,-,-,-,-}
%e {1,-,-,4,-,-,2,-,-,-,5,-,3,-,-,-,-,-,-}
%e {1,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,-}
%e {1,-,-,4,-,-,-,3,-,-,5,2,-,-,-,-,-,-,-}
%e {1,-,-,4,5,-,2,3,-,-,-,-,-,-,-,-,-,-,-}
%e {1,-,-,4,5,-,-,3,-,-,-,2,-,-,-,-,-,-,-}
%e {1,-,-,-,5,-,2,3,4,-,-,-,-,-,-,-,-,-,-}
%e {1,-,-,-,5,-,2,-,4,-,-,-,3,-,-,-,-,-,-}
%e {1,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,-}
%e {1,-,-,-,5,-,-,3,4,-,-,2,-,-,-,-,-,-,-}
%e {1,-,-,-,5,-,-,-,4,-,-,2,3,-,-,-,-,-,-}
%e {1,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,-}
%e {-,2,-,-,-,1,-,3,4,-,5,-,-,-,-,-,-,-,-}
%e {-,2,-,-,-,1,-,3,-,-,5,-,-,-,4,-,-,-,-}
%e {-,2,-,-,-,1,-,-,4,-,-,-,3,-,-,-,-,5,-}
%e {-,2,-,-,-,1,-,-,4,-,5,-,3,-,-,-,-,-,-}
%e {-,2,-,-,-,1,-,-,-,-,5,-,3,-,4,-,-,-,-}
%e {-,2,-,-,-,1,-,-,-,-,5,-,-,-,4,-,3,-,-}
%e {-,2,3,-,-,1,-,-,4,-,5,-,-,-,-,-,-,-,-}
%e {-,2,3,-,-,1,-,-,-,-,5,-,-,-,4,-,-,-,-}
%e {-,2,3,4,-,1,-,-,-,-,5,-,-,-,-,-,-,-,-}
%e {-,2,3,4,5,1,-,-,-,-,-,-,-,-,-,-,-,-,-}
%e {-,2,3,-,5,1,-,-,4,-,-,-,-,-,-,-,-,-,-}
%e {-,2,3,-,5,-,-,-,4,1,-,-,-,-,-,-,-,-,-}
%e {-,2,-,4,-,1,-,3,-,-,5,-,-,-,-,-,-,-,-}
%e {-,2,-,4,-,1,-,-,-,-,5,-,3,-,-,-,-,-,-}
%e {-,2,-,4,-,-,-,3,-,1,5,-,-,-,-,-,-,-,-}
%e {-,2,-,4,-,-,-,3,-,-,5,-,-,1,-,-,-,-,-}
%e {-,2,-,4,5,1,-,3,-,-,-,-,-,-,-,-,-,-,-}
%e {-,2,-,4,5,-,-,3,-,1,-,-,-,-,-,-,-,-,-}
%e {-,2,-,-,5,1,-,3,4,-,-,-,-,-,-,-,-,-,-}
%e {-,2,-,-,5,1,-,-,4,-,-,-,3,-,-,-,-,-,-}
%e {-,2,-,-,5,-,-,3,-,1,-,-,-,-,4,-,-,-,-}
%e {-,2,-,-,5,-,-,3,4,1,-,-,-,-,-,-,-,-,-}
%e {-,2,-,-,5,-,-,-,4,1,-,-,3,-,-,-,-,-,-}
%e {-,2,-,-,5,-,-,-,4,-,-,-,3,1,-,-,-,-,-}
%e {-,-,3,-,-,1,2,-,4,-,5,-,-,-,-,-,-,-,-}
%e {-,-,3,-,-,1,2,-,-,-,5,-,-,-,4,-,-,-,-}
%e {-,-,3,-,-,1,-,-,4,-,-,2,-,-,-,-,-,5,-}
%e {-,-,3,-,-,1,-,-,4,-,5,2,-,-,-,-,-,-,-}
%e {-,-,3,-,-,1,-,-,-,-,5,2,-,-,4,-,-,-,-}
%e {-,-,3,-,-,1,-,-,-,-,5,-,-,-,4,2,-,-,-}
%e {-,-,3,-,-,-,2,-,-,1,-,-,-,-,4,-,-,5,-}
%e {-,-,3,-,-,-,2,-,-,1,5,-,-,-,4,-,-,-,-}
%e {-,-,3,-,-,-,2,-,4,1,5,-,-,-,-,-,-,-,-}
%e {-,-,3,-,-,-,2,-,4,-,5,-,-,1,-,-,-,-,-}
%e {-,-,3,-,-,-,2,-,-,-,5,-,-,1,4,-,-,-,-}
%e {-,-,3,-,-,-,2,-,-,-,5,-,-,-,4,-,-,-,1}
%e {-,-,3,4,-,1,2,-,-,-,5,-,-,-,-,-,-,-,-}
%e {-,-,3,4,-,1,-,-,-,-,5,2,-,-,-,-,-,-,-}
%e {-,-,3,4,-,-,2,-,-,1,5,-,-,-,-,-,-,-,-}
%e {-,-,3,4,-,-,2,-,-,-,5,-,-,1,-,-,-,-,-}
%e {-,-,3,4,5,1,2,-,-,-,-,-,-,-,-,-,-,-,-}
%e {-,-,3,4,5,-,2,-,-,1,-,-,-,-,-,-,-,-,-}
%e {-,-,3,-,5,1,2,-,4,-,-,-,-,-,-,-,-,-,-}
%e {-,-,3,-,5,1,-,-,4,-,-,2,-,-,-,-,-,-,-}
%e {-,-,3,-,5,-,2,-,-,1,-,-,-,-,4,-,-,-,-}
%e {-,-,3,-,5,-,2,-,4,1,-,-,-,-,-,-,-,-,-}
%e {-,-,3,-,5,-,-,-,4,1,-,2,-,-,-,-,-,-,-}
%e {-,-,3,-,5,-,-,-,4,-,-,2,-,1,-,-,-,-,-}
%e {-,-,-,4,-,1,2,3,-,-,5,-,-,-,-,-,-,-,-}
%e {-,-,-,4,-,1,2,-,-,-,5,-,3,-,-,-,-,-,-}
%e {-,-,-,4,-,1,-,3,-,-,-,2,-,-,-,-,-,5,-}
%e {-,-,-,4,-,1,-,3,-,-,5,2,-,-,-,-,-,-,-}
%e {-,-,-,4,-,1,-,-,-,-,5,2,3,-,-,-,-,-,-}
%e {-,-,-,4,-,1,-,-,-,-,5,-,3,-,-,2,-,-,-}
%e {-,-,-,4,-,-,2,-,-,1,-,-,3,-,-,-,-,5,-}
%e {-,-,-,4,-,-,2,-,-,1,5,-,3,-,-,-,-,-,-}
%e {-,-,-,4,-,-,2,3,-,1,5,-,-,-,-,-,-,-,-}
%e {-,-,-,4,-,-,2,3,-,-,5,-,-,1,-,-,-,-,-}
%e {-,-,-,4,-,-,2,-,-,-,5,-,-,1,-,-,3,-,-}
%e {-,-,-,4,-,-,2,-,-,-,5,-,3,1,-,-,-,-,-}
%e {-,-,-,4,-,-,-,3,-,1,-,2,-,-,-,-,-,5,-}
%e {-,-,-,4,-,-,-,3,-,1,5,2,-,-,-,-,-,-,-}
%e {-,-,-,4,-,-,-,3,-,-,-,2,-,1,-,-,-,5,-}
%e {-,-,-,4,-,-,-,3,-,-,-,2,-,-,-,-,-,5,1}
%e {-,-,-,4,-,-,-,3,-,-,5,-,-,1,-,2,-,-,-}
%e {-,-,-,4,-,-,-,3,-,-,5,2,-,1,-,-,-,-,-}
%e {-,-,-,4,5,1,2,3,-,-,-,-,-,-,-,-,-,-,-}
%e {-,-,-,4,5,1,-,3,-,-,-,2,-,-,-,-,-,-,-}
%e {-,-,-,4,5,-,2,-,-,1,-,-,3,-,-,-,-,-,-}
%e {-,-,-,4,5,-,2,3,-,1,-,-,-,-,-,-,-,-,-}
%e {-,-,-,4,5,-,-,3,-,1,-,2,-,-,-,-,-,-,-}
%e {-,-,-,4,5,-,-,3,-,-,-,2,-,1,-,-,-,-,-}
%e {-,-,-,-,5,1,2,3,4,-,-,-,-,-,-,-,-,-,-}
%e {-,-,-,-,5,1,2,-,4,-,-,-,3,-,-,-,-,-,-}
%e {-,-,-,-,5,1,-,3,-,-,-,2,-,-,4,-,-,-,-}
%e {-,-,-,-,5,1,-,3,4,-,-,2,-,-,-,-,-,-,-}
%e {-,-,-,-,5,1,-,-,4,-,-,2,3,-,-,-,-,-,-}
%e {-,-,-,-,5,1,-,-,4,-,-,-,3,-,-,2,-,-,-}
%e {-,-,-,-,5,-,2,-,-,1,-,-,3,-,4,-,-,-,-}
%e {-,-,-,-,5,-,2,-,-,1,-,-,-,-,4,-,3,-,-}
%e {-,-,-,-,5,-,2,3,-,1,-,-,-,-,4,-,-,-,-}
%e {-,-,-,-,5,-,2,3,4,1,-,-,-,-,-,-,-,-,-}
%e {-,-,-,-,5,-,2,-,4,1,-,-,3,-,-,-,-,-,-}
%e {-,-,-,-,5,-,2,-,4,-,-,-,3,1,-,-,-,-,-}
%e {-,-,-,-,5,-,-,3,-,1,-,2,-,-,4,-,-,-,-}
%e {-,-,-,-,5,-,-,3,-,1,-,-,-,-,4,2,-,-,-}
%e {-,-,-,-,5,-,-,3,-,-,-,2,-,1,4,-,-,-,-}
%e {-,-,-,-,5,-,-,3,-,-,-,2,-,-,4,-,-,-,1}
%e {-,-,-,-,5,-,-,3,4,1,-,2,-,-,-,-,-,-,-}
%e {-,-,-,-,5,-,-,3,4,-,-,2,-,1,-,-,-,-,-}
%e {-,-,-,-,5,-,-,-,4,1,-,2,3,-,-,-,-,-,-}
%e {-,-,-,-,5,-,-,-,4,1,-,-,3,-,-,2,-,-,-}
%e {-,-,-,-,5,-,-,-,4,-,-,2,-,1,-,-,3,-,-}
%e {-,-,-,-,5,-,-,-,4,-,-,2,3,1,-,-,-,-,-}
%e {-,-,-,-,5,-,-,-,4,-,-,-,3,1,-,2,-,-,-}
%e {-,-,-,-,5,-,-,-,4,-,-,-,3,-,-,2,-,-,1}
%e (End)
%t NextTuple[x_, n_, l_] := Module[{i, x0 = x},
%t If[x0 == ConstantArray[n, l], Return[{}]];
%t For[i = l, i >= 1, i--,
%t If[x0[[i]] < n, x0[[i]]++; Return[x0], x0[[i]] = 1]]];
%t Join[{1}, Table[p = Permutations[Range[n], {n}];
%t For[tl = n + 1, tl <= 50, tl++,
%t tup = ConstantArray[1, tl];
%t While[tup = NextTuple[tup, n, tl]; tup != {},
%t If[Product[Count[tup, i], {i, 1, n}] == 0, Continue[]];
%t For[j = 1, j <= Length[p], j++,
%t perm = p[[j]]; lst = tup; fnd = True;
%t For[k = 1, k <= Length[perm], k++,
%t If[lst == {}, fnd = False; Break[]];
%t p1 = Position[lst, perm[[k]], 1, 1];
%t If[Length[p1] == 0, fnd = False; Break[]];
%t p1 = First@First@p1;
%t If[! IntegerQ[p1], fnd = False; Break[]];
%t lst = Drop[lst, p1];
%t ]; If[! fnd, Break[]]]; If[fnd, Break[]]]; If[fnd, Break[]]];
%t tl, {n, 2, 5}]](* _Robert Price_, Oct 13 2019 *)
%Y Cf. A136094 (smallest sequences), A351468 (Newey's sequences).
%Y Cf. A337300 (conjectured values).
%Y Cf. A180632 (superpermutations), A348574 (subset substrings).
%K nonn,nice,more
%O 1,2
%A _N. J. A. Sloane_, Jul 14 2001
%E a(5) = 19 from _John W. Layman_, Aug 29 2008
%E a(5)-a(7) are computed by Newey 1973, added by _Max Alekseyev_, Apr 16 2013
|
