login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 18 18:56 EST 2018. Contains 297864 sequences.