A062714 -id:A062714 - cp's OEIS frontend

A374085 Number of sequences of length A062714(n) with symbols from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

1, 2, 42, 216

Offset: 1

Chai Wah Wu, Jun 27 2024

a(n) is a multiple of n!.

			a(1) = 1 as '1' is the only sequence of length A062714(1) = 1.
a(2) = 2 corresponding to the sequences of length A062714(2) = 3 : {'121', '212'}.
a(3) = 42 corresponding to the sequences of length A062714(3) = 7 : {'1213121', '1213212', '1231213', '1231231', '1231321', '1232123', '1232132', '1312131', '1312313', '1321231', '1321312', '1321321', '1323123', '1323132', '2123121', '2123212', '2131213', '2131231', '2132123', '2132132', '2132312', '2312132', '2312312', '2312321', '2313213', '2313231', '2321232', '2321323', '3121312', '3121321', '3123123', '3123132', '3123213', '3132131', '3132313', '3212312', '3212321', '3213123', '3213213', '3213231', '3231232', '3231323'}.

Cf. A062714, A180632.

A180632 Minimum length of a string over the alphabet A = {1,2,...,n} that contains every permutation of A as a substring exactly once, also known as length of the minimal super-permutation.

Original entry on oeis.org

0, 1, 3, 9, 33, 153

Offset: 0

Michael Hamm, Sep 13 2010

Obviously bounded below by n! + n - 1 and above by 2(n! - (n - 1)!) + 1.
A better lower bound is n! + (n - 1)! + (n - 2)! + n - 3 (A376269) and a better upper bound is A007489(n). - Nathaniel Johnston, Apr 22 2013
The above mentioned lower bound was essentially shown in 2011 by an anonymous poster on the internet and, filling in some minor details, brought into a formal form by Houston, Pantone and Vatter (see reference). - Peter Luschny, Oct 27 2018
Was conjectured to be equal to A007489, but it is now known that a(n) < A007489(n) for all n > 5. - Robin Houston, Aug 22 2014
Different from the minimal supersequence, in which each permutations of n letters can appear as a subsequence instead of a sub-string (i.e., with noncontiguous characters). Refer to A062714. - Maurizio De Leo, Mar 02 2015
In October 2018 Greg Egan found new records for n=7, 8, 9: a(7) <= 5908, a(8) <= 46205, and a(9) <= 408966. More generally, for any n >= 7, a(n) <= n! + (n-1)! + (n-2)! + (n-3)! + n - 3. - Peter Luschny, Oct 26 2018; corrected by Max Alekseyev, Jan 07 2019
In February 2019, Bogdan Coanda found an example showing that a(7) <= 5907. Later the same month, Greg Egan found an example showing a(7) <= 5906. - Robin Houston, Mar 11 2019
a(6) <= 872 = A007489(6) - 1 [Houston 2014]. - M. F. Hasler, Jul 28 2020

			For n = 1, 2, 3, 4, the (unique, up to relabeling the symbols) minimal words are:
1
121
123121321
123412314231243121342132413214321
For n = 5, there are exactly 8 distinct (up to relabeling the symbols) minimal words.
Comment from _N. J. A. Sloane_, Mar 27 2015: From the Houston (2014 arXiv) paper, a superpermutation of length 872 (not known to be minimal, but shorter than the old upper bound of 873):
  1234561234516234512634512364513264513624513642513645213645123465123415 6234152634152364152346152341652341256341253641253461253416253412653412 3564123546123541623541263541236541326543126453162435162431562431652431 6254316245316425314625314265314256314253614253164523146523145623145263 1452361452316453216453126435126431526431256432156423154623154263154236 1542316542315642135642153624153621453621543621534621354621345621346521 3462513462153642156342165342163542163452163425163421564325164325614325 6413256431265432165432615342613542613452613425613426513426153246513246 5312463512463152463125463215463251463254163254613254631245632145632415 6324516324561324563124653214653241653246153264153261453261543265143625 1436521435621435261435216435214635214365124361524361254361245361243561 2436514235614235164235146235142635142365143265413625413652413562413526 41352461352416352413654213654123

D. Ashlock and J. Tillotson. Construction of small superpermutations and minimal injective superstrings. Congressus Numerantium, 93 (1993), 91-98.

Dhruv Ajmera, An O(n) Space Construction of Superpermutations, arXiv:2505.09628 [cs.DM], 2025. See p. 29.
Anonymous 4chan Poster, Robin Houston, Jay Pantone and Vince Vatter, A lower bound on the length of the shortest superpattern, October 25, 2018.
Jeffrey A. Barnett, Permutation Strings
Greg Egan, Superpermutations, October 20, 2018.
Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 4-24, section 2; arXiv preprint, arXiv:1810.08252 [math.CO], 2018-2020.
James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
James Grime, Matt Parker and Robin Houston, New Superpermutations Discovered!, standupmaths video, March 11, 2019.
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Robin Houston and Matt Parker, Superpermutations: the maths problem solved by 4chan, standupmaths video (2019).
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Math., 313 (2013), 1553-1557.
Nathaniel Johnston, The minimal superpermutation problem, 2013.
Nathaniel Johnston, All minimal superpermutations on five symbols have been found
Miryana Stefanović, Supermutacije (Supermutations), Master's Thesis, Univ. Belgrade (Serbia 2023). See p. 9. (In Serbian)
Wikipedia, Superpermutation
Aaron Williams, Hamiltonicity of the Cayley digraph on the symmetric group generated by sigma = (1 2 ... n) and tau = (1 2), arXiv:1307.2549v3 [math.CO], 2017.

Cf. A188428, A224986, A062714, A007489, A376269.

Row lengths of A332089 (for n >= 1).

Edited and expanded by Nathaniel Johnston, Apr 22 2013
a(5) computed by Benjamin Chaffin and verified by Nathaniel Johnston, Aug 13 2014
Definition edited by Maurizio De Leo, Mar 02 2015; and by Max Alekseyev, Jan 07 2019

A337300 Partial sums of the geometric Connell sequence A049039.

Original entry on oeis.org

1, 3, 7, 12, 19, 28, 39, 51, 65, 81, 99, 119, 141, 165, 191, 218, 247, 278, 311, 346, 383, 422, 463, 506, 551, 598, 647, 698, 751, 806, 863, 921, 981, 1043, 1107, 1173, 1241, 1311, 1383, 1457, 1533, 1611, 1691, 1773, 1857, 1943, 2031, 2121, 2213, 2307, 2403

Offset: 1

Kevin Ryde, Aug 22 2020

a(n) is Newey's "more complicated" conjectured length of the shortest sequence containing all permutations of 1..n (A062714). It agrees with A062714(n) for n <= 7. [But not for n=8. - Pontus von Brömssen, Aug 18 2025]

Kevin Ryde, Table of n, a(n) for n = 1..5000
Malcolm Newey, Notes On a Problem Involving Permutations As Subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973. Conjectured M(n) formula bottom of page 12.

Cf. A000295, A049039 (first differences), A062714, A122793 (arithmetic Connell sums).

a(n) = my(k=logint(n,2)); n^2 - k*(n+1) + (2<

a(n) = n^2 - k*n + F(k) where k = floor(log_2(n)) and F(0) = 0 then F(k) = k + 2*F(k-1) [Newey], which is F(k) = 2^(k+1) - k - 2 = A000295(k+1), the Eulerian numbers.
a(n) = n^2 - k*(n+1) + 2*(2^k - 1) where k = floor(log_2(n)).
G.f.: 2*x/(1-x)^3 - ( Sum_{j>=0} x^(2^j) )/(1-x)^2.
a(n) = Sum_{i=1..n} A049039(i). - Gerald Hillier, Jun 18 2016

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

Original entry on oeis.org

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.

A188428 Number of strings of length n on three symbols containing all permutations of those three symbols as substrings (factors), divided by six.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 9, 54, 276, 1282, 5585, 23223, 93146, 362928, 1380535, 5145692, 18846775, 67982489, 241940204, 850777688, 2959796467, 10197732687, 34828459508, 118003182174, 396897710483, 1326018464696, 4402883891950, 14536059784925, 47737688829399

Offset: 1

Nathaniel Johnston, Mar 30 2011

nonn

Division by six is performed so that strings that are identical up to swapping the symbols are not double-counted.

The corresponding sequence for strings of length n on two symbols is given by a(n) = 2^(n-1) - n = A000295(n-1).

			a(9) = 1 because there are 6 strings of length 9 on the three symbols "1", "2", and "3" containing each of "123", "132", "213", "231", "312", and "321" as substrings: they are "123121321" and the five other strings obtained by swapping the roles of "1", "2", and "3" in that string.
The substrings must be contiguous -- if they were allowed to be non-contiguous (i.e., subsequences) then there would be a valid string of length 7: "1232132" (see A062714).

Paul Tek, Table of n, a(n) for n = 1..2000
Paul Tek, PERL program for this sequence

Cf. A000295, A062714, A180632, A224986.

A351468 Irregular triangle read by rows where row n is Newey's sequence containing all permutations of 1..n.

Original entry on oeis.org

1, 2, 1, 2, 1, 2, 3, 1, 2, 1, 3, 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 1, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 1, 4, 5, 2, 1, 3, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 1, 6, 2, 3, 4, 1, 5, 6, 2, 3, 1, 4, 5, 6, 2, 1, 3

Offset: 2

Kevin Ryde, Feb 23 2022

Row n contains n^2 - 2*n + 4 = A117950(n-1) terms, numbered as columns k >= 1. Row n contains within it all permutations of 1..n as subsequences. These subsequences need not be consecutive terms (and in general are not).
Newey's construction (section 6) is an initial 1..n then successive term 1 and n-2 terms from a rotating block of 2..n. The effect is term 1 at k=1, k=n+1, then steps n-1 apart, and the rest filled with repeating 2..n.
Koutas and Hu (equation (1)) form the same by blocks D_k(m|n) which start with 1 and then appropriate parts of rotated 2..n like Newey.
Jon E. Schoenfield in A062714 starts from repeated 2..n and inserts 1's.
For n = 3 to 7, Newey shows these sequences are as short as possible (A062714) for any sequence containing all permutations, and noted the "obvious" conjecture that maybe they would be shortest always. But this is not so, since Jon E. Schoenfield gives a shorter n=16 in A062714, and Radomirovic constructs shorter for all n >= 10.

			Triangle begins
  n=2:  1,2,1,2
  n=3:  1,2,3,1,2,1,3
  n=4:  1,2,3,4,1,2,3,1,4,2,1,3
  n=5:  1,2,3,4,5,1,2,3,4,1,5,2,3,1,4,5,2,1,3
For row n=3, the permutations of 1,2,3 are located within the row as follows (some are present in multiple ways too).
   1,2,3,1,2,1,3     row n=3
   1-2-3             \
   1---3---2         | all permutations
           2-1-3     | of 1,2,3 within
     2-3-1           | row n=3
       3-1-2         |
       3---2-1       /
For row n=4, see example in A062714.
For row n=5, the pattern of 1's among repeating 2..5 is
    2,3,4,5,  2,3,4,  5,2,3,  4,5,2,  3
  1,        1,      1,      1,      1,
   \-------/ \-----/ \-----/ \-----/
    5 apart,   thereafter 4 apart

Kevin Ryde, Table of n, a(n) for rows 2 .. 30, flattened
P. J. Koutas and T. C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, volume 11, 1975, pages 125-132.
Malcolm Newey, Notes on a Problem Involving Permutations as Subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973.

Cf. A117950 (row lengths), A062714 (shortest possible).

Cf. A351469 (Adelman's sequences).

T(n,k) = if(k<=n,k, my(q,r);[q,r]=divrem(k-2,n-1); if(r==0&&q

row(n) = my(r=1,t=1); vector((n-1)^2+3,i, if(i==1,1, r++>n,r=1+(n>2);1, if(t++>n,t=2, t)));

T(n,k) = k for 1 <= k <= n, otherwise.

T(n,k) = 1 if r=0 and q

T(n,k) = 2 + ((r-q) mod (n-1)),

where division q = floor((k-2)/(n-1)) remainder r = (k-2) mod (n-1). [Adapted from Jon E. Schoenfield in A062714.]

A136094 a(n) is the smallest number consisting of digits {1,...,n} that contains all the permutations of {1,...,n} as subsequences.

Original entry on oeis.org

1, 121, 1213121, 123412314213, 1234512341523142351, 1234516234152361425312643512, 123451672341526371425361274351263471253, 1234156782315426738152643718265341278635124376812453

Offset: 1

Aniruddha Das (hi.annie.pal(AT)gmail.com), May 10 2008

It is unclear how a(n) is defined for n >= 10.

P. J. Koutas and T. C. Hu, Shortest String Containing All Permutations, Discrete Mathematics, Vol. 11, 1975, pp. 125-132.
S.P. Mohanty, Shortest string containing all permutations, Discrete Mathematics, Volume 31, Issue 1, 1980, Pages 91-95.

The lengths of the terms are given by A062714.

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[]]];
FromDigits@tup, {n, 2, 5}]] (* Robert Price, Oct 13 2019 *)

Edited by N. J. A. Sloane, May 16 2008
a(4) corrected from 1234321234321 to 123412314213 by Bridget Tenner, Apr 21 2009, who also confirms a(1), a(2), a(3) and a(5).
a(3) and a(5) are corrected from A062714, incorrect terms a(6), a(7) are removed by Max Alekseyev, Apr 14 2013
a(3) corrected, a(6) added by Max Alekseyev, May 14 2013
a(7) added by Vitaliy Garnashevich, Mar 31 2017
a(8) added by Vitaliy Garnashevich, Jun 24 2020

A259482 Number of states in smallest deterministic finite automaton that accepts exactly the strings over the alphabet {1,2,...,n} having all permutations of 12...n as subsequences.

Original entry on oeis.org

2, 6, 44, 2014, 1651377

Offset: 1

Jeffrey Shallit, Jun 28 2015

The automaton is assumed to be "complete"; that is, there is a transition from every state on every letter.

Also, the length of the shortest string accepted by this automaton is the sequence A062714.

			For n = 2 there is a 6-state automaton accepting (11*22*1 + 22*11*2)(1 + 2)*.

Kevin Ryde, Perl program running Foma or SFST to construct the DFAs

Cf. A062714.

a(5) from Kevin Ryde, Aug 21 2020

A373728 a(n) is the length of a shortest integer sequence on a circle containing all permutations of the set {1, 2, ..., n} as subsequences.

Original entry on oeis.org

2, 4, 8, 12, 17

Offset: 2

Michel Marcus, Jun 15 2024

This is called r(n) in Lecouturier and Zmiaikou.

			From _Chai Wah Wu_, Jun 27 2024: (Start)
Sequence corresponding to each n (which may not be unique):
n = 2: 12
n = 3: 1232
n = 4: 12341214
n = 5: 123451215432
n = 6: 12345612156431265
(End)

Emmanuel Lecouturier and David Zmiaikou, On a conjecture of H. Gupta, Discrete Math. 312, 8(2012), 1444-1452.

Cf. A062714.

from itertools import count, permutations, product
def is_subseq(s, p):
    while s != "" and p != "":
        if p[0] == s[0]: s = s[1:]
        p = p[1:]
    return s == ""
def a(n):
    digits = "".join(str(i) for i in range(n))
    for k in count(0):
        for p in product(digits, repeat=k):
            r, c_all = (digits + "".join(p))*2, True
            for q in permutations(digits):
                w = "".join(q)
                if not any(is_subseq(w, r[j:j+n+k]) for j in range(n+k)):
                    c_all = False
                    break
            if c_all:
                return n+k
print([a(n) for n in range(2, 6)]) # Michael S. Branicky, Jun 17 2024

a(n) <= n^2/2 if n is even.

a(n) < n^2/2 + n/4 -1 if n is odd.

A348574 Length of the shortest string over the alphabet {1,...,n} such that every subset of {1,...,n} appears as a substring (in some order).

Original entry on oeis.org

1, 2, 4, 8, 13, 24, 40

Offset: 1

Alexander D. Healy, Oct 23 2021

a(7) = 40 by computer search.
a(8) >= 73 by formula (1) of Lipski.
a(8) <= 76 using 12345671825473861253846275138427163587...
                 ...26341568237415876412573641823178456231.
a(9) >= 130 by formula (1) of Lipski.
a(9) <= 149 using 1234567891245739681253946175283419726538...
                  ...4926137845926374159837241856931728643...
                  ...1597246159283674981635781642391874562...
                  ...89751384973251697248567213864957684.

			a(4) = 8 because the string 12342413 contains every subset of {1,2,3,4} as a substring -- e.g., {1,3,4} can be found in the last three symbols ('413') -- and it can be shown that no string of length 7 has this property (see, e.g., Lipski 1978).
Examples of optimal strings for n <= 7:
1: 1
2: 12
3: 1231
4: 12342413
5: 1234512413524
6: 123415643641253624531625
7: 1234567214573126431523674256147325716357

I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, pp. 39-40.

W. Lipski, Jr., On strings containing all subsets as substrings, Discrete Mathematics 21, 1978, pp. 253-259.

Cf. A062714.

a(n) >= binomial(n, ceiling(n/2)) + ceiling(n/2) - 1. [Lipski, formula (1)]

a(n) >= n * ceiling(binomial(n, floor(n/2)) / n). [Lipski, formula (3)]

Showing 1-10 of 12 results. Next

cp's OEIS Frontend

A374085 Number of sequences of length A062714(n) with symbols from {1, 2, 3, ..., n} which contains, as a subsequence, each possible ordering of the n symbols 1, 2, 3, ..., n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A180632 Minimum length of a string over the alphabet A = {1,2,...,n} that contains every permutation of A as a substring exactly once, also known as length of the minimal super-permutation.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A337300 Partial sums of the geometric Connell sequence A049039.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A188428 Number of strings of length n on three symbols containing all permutations of those three symbols as substrings (factors), divided by six.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A351468 Irregular triangle read by rows where row n is Newey's sequence containing all permutations of 1..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A136094 a(n) is the smallest number consisting of digits {1,...,n} that contains all the permutations of {1,...,n} as subsequences.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A259482 Number of states in smallest deterministic finite automaton that accepts exactly the strings over the alphabet {1,2,...,n} having all permutations of 12...n as subsequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A373728 a(n) is the length of a shortest integer sequence on a circle containing all permutations of the set {1, 2, ..., n} as subsequences.

Views

Author

Keywords

Comments