This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 5
 1, 3, 7, 12, 19, 28, 39 (list; graph; refs; listen; history; text; internal format)
 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) mod (n-1) = 0   int((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) LINKS P. Uznanski, All Permutations Supersequence is coNP-complete, arXiv preprint arXiv:1506.05079 [cs.CC], 2015. D. Galvin, The n-Part Trilogy Problem P. J. Koutas and T. C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, Vol. 11, 1975, pp. 125-132. M. Newey, Notes on a problem involving permutations as subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973. S. Radomirovic, A Construction of Short Sequences Containing All Permutations of a Set as Subsequences, Electronic Journal of Combinatorics 19(4), 2012, P31. FORMULA Conjecture: a(n) = Sum{k=1..n} A049039(k). - 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) CROSSREFS The corresponding lexicographically earliest shortest sequences are given by A136094. Sequence in context: A022791 A025742 A122793 * A039677 A011899 A002498 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

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.

Last modified September 18 07:50 EDT 2019. Contains 327168 sequences. (Running on oeis4.)