A180632 -id:A180632 - cp's OEIS frontend

A007489 a(n) = Sum_{k=1..n} k!.

0, 1, 3, 9, 33, 153, 873, 5913, 46233, 409113, 4037913, 43954713, 522956313, 6749977113, 93928268313, 1401602636313, 22324392524313, 378011820620313, 6780385526348313, 128425485935180313, 2561327494111820313, 53652269665821260313, 1177652997443428940313

Offset: 0

N. J. A. Sloane, Robert G. Wilson v

Equals row sums of triangle A143122 starting (1, 3, 9, 33, ...). - Gary W. Adamson, Jul 26 2008
a(n) for n>=4 is never a perfect square. - Alexander R. Povolotsky, Oct 16 2008
Number of cycles that can be written in the form (j,j+1,j+2,...), in all permutations of {1,2,...,n}. Example: a(3)=9 because in (1)(2)(3), (1)(23), (12)(3), (13)(2), (123), (132) we have 3+2+2+1+1+0=9 such cycles. - Emeric Deutsch, Jul 14 2009
Conjectured to be the length of the shortest word over {1,...,n} that contains each of the n! permutations as a factor (cf. A180632) [see Johnston]. - N. J. A. Sloane, May 25 2013
The above conjecture has been disproven for n>=6. See A180632 and the Houston 2014 reference. - Dmitry Kamenetsky, Mar 07 2016
a(n) is also the number of compositions of n if cardinal values do not matter but ordinal rankings do. Since cardinal values do not matter, a sequence of k summands summing to n can be represented as (s(1),...,s(k)), where the s's are positive integers and the numbers in parentheses are the initial ordinal rankings. The number of compositions of these summands are equal to k!, with k ranging from 1 to n. - Gregory L. Simay, Jul 31 2016
When the numbers denote finite permutations (as row numbers of A055089) these are the circular shifts to the left. Compare array A211370 for circular shifts to the left in a broader sense. Compare sequence A001563 for circular shifts to the right. - Tilman Piesk, Apr 29 2017
Since a(n) = (1!+2!+3!+...+n!) = 3(1+3!/3+4!/3+...+n!/3) is a multiple of 3 for n>2, the only prime in this sequence is a(2) = 3. - Eric W. Weisstein, Jul 15 2017
Generalization of 2nd comment: a(n) for n>=4 is never a perfect power (A007916) (Chentzov link). - Bernard Schott, Jan 26 2023

			a(4) = 1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33. - _Michael B. Porter_, Aug 03 2016

R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Section B44, Springer 2010.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Carauleanu Marc, Table of n, a(n) for n = 0..212 (first 100 terms from T. D. Noe)
N. N. Chentzov, D. O. Shklarsky, and I. M. Yaglom, The USSR Olympiad Problem Book, Selected Problems and Theorems of Elementary Mathematics, problem 115, pp. 28 and 201-202, Dover publications, Inc., New York, 1993.
R. K. Guy, Letter to N. J. A. Sloane, 1987
Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, The minimal superpermutation problem (2013)
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, Discrete Math. 313 (2013), no. 14, 1553--1557. MR3047396
S. Legendre and P. Paclet, On the Permutations Generated by Cyclic Shift , J. Int. Seq. 14 (2011) # 11.3.2.
Hisanori Mishima, Factorizations of many number sequences
Hisanori Mishima, Factorizations of many number sequences
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
Eric Weisstein's World of Mathematics, Factorial
Eric Weisstein's World of Mathematics, Left Factorial
G. Xiao, Sigma Server, Operate on "n!"
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 5.
Index entries for sequences related to factorial numbers

Equals A003422(n+1) - 1.
Cf. A000142, A000670, A001597, A007916, A137593, A143122, A161128, A180632.
Column k=0 of A120695.

List([1..20],n->Sum([1..n],Factorial)); # Muniru A Asiru, Jan 31 2018

a007489 n = a007489_list !! n
a007489_list = scanl (+) 0 $ tail a000142_list
-- Reinhard Zumkeller, Aug 29 2014

[0] cat [&+[Factorial(i): i in [1..n]]: n in [1..25]]; // Vincenzo Librandi, Sep 02 2016

A007489 := proc(n) local i; add(i!,i=1..n); end proc;

FoldList[Plus, 0, (Range@ 21)! ] (* Robert G. Wilson v, Sep 21 2007 *)
Table[Sum[i!, {i, 1, n}], {n, 0, 21}] (* Zerinvary Lajos, Jul 12 2009 *)
Accumulate[Range[50]!]  (* Harvey P. Dale, Apr 30 2011 *)
Table[Plus@@(Range[n]!), {n, 20}] (* Alonso del Arte, Jul 18 2011 *)

a(n)=sum(k=1,n,k!) \\ Charles R Greathouse IV, Jul 25 2011

a(n) = Sum_{k=1..n} P(n, k)/C(n, k). - Ross La Haye, Sep 21 2004
a(n) = 3*A056199(n) for n>=2. - Philippe Deléham, Feb 10 2007
a(n) = !(n+1)-1=A003422(n+1)-1. - Artur Jasinski, Nov 08 2007 [corrected by Werner Schulte, Oct 20 2021]
Starting (1, 3, 9, 33, 153, ...), = row sums of triangle A137593 - Gary W. Adamson, Jan 28 2008
a(n) = a(n-1) + n! for n >= 1. - Jaroslav Krizek, Jun 16 2009
E.g.f. A(x) satisfies to the differential equation A'(x)=A(x)+x/(1-x)^2+1. - Vladimir Kruchinin, Jan 22 2011
a(0)=0, a(1)=1, a(n) = (n+1)*a(n-1)-n*a(n-2). - Sergei N. Gladkovskii, Jul 05 2012
G.f.: W(0)*x/(2-2*x) , where W(k) = 1 + 1/( 1 - x*(k+2)/( x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 19 2013
G.f.: x /(1-x)/Q(0),m=+2, where Q(k) = 1 - 2*x*(2*k+1) - m*x^2*(k+1)*(2*k+1)/( 1 - 2*x*(2*k+2) - m*x^2*(k+1)*(2*k+3)/Q(k+1) ) ; (continued fraction). - Sergei N. Gladkovskii, Sep 24 2013
E.g.f.: exp(x-1)*(Ei(1) - Ei(1-x)) - exp(x) + 1/(1 - x), where Ei(x) is the exponential integral. - Ilya Gutkovskiy, Nov 27 2016
a(n) = sqrt(a(n-1)*a(n+1)-a(n-2)*n*n!), n >= 2. - Gary Detlefs, Oct 26 2020
a(n) ~ n!. - Ridouane Oudra, Jun 11 2025

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.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jul 14 2001

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

			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)

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.
Maarten Löffler and Benjamin Raichel, Preprocessing Disks for Convex Hulls, Revisited, arXiv:2502.03633 [cs.CG], 2025. See p. 28.
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.

Cf. A136094 (smallest sequences), A351468 (Newey's sequences).
Cf. A049039, A337300 (conjectured values).
Cf. A373728 (circular), A180632 (superpermutations), A348574 (subset substrings).

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 *)

Conjecture: a(n) = Sum_{k=1..n} A049039(k) = A337300(n). - Gerald Hillier, Jun 18 2016 [The conjecture is false for n=8, provided that a(8)=52 is correct. - Pontus von Brömssen, Aug 18 2025]

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
a(8) (using A136094) from Pontus von Brömssen, Aug 18 2025

A332089 Irregular table read by rows, where row n lists the lexicographically first superpermutation of minimal length over {1, ..., n}.

Original entry on oeis.org

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

Offset: 1

M. F. Hasler, Jul 31 2020

Sequence A180632 gives the row lengths and more information about superpermutations, i.e., strings over a finite alphabet that contain all permutations thereof as a substring.

In March 2014, Ben Chaffin showed that minimal superpermutations of order n = 5 have length 153, and found all 8 distinct superpermutations of this kind; the (non-palindromic) lexicographically first one is row 5 of this table. For n = 6, Robin Houston has found a few months later several superpermutations of length 872 (one less than the previously conjectured minimal length), but we still don't know which is the shortest (and/or lexico-first) superpermutation for that case.

			The table starts:
  n | SP[n]
----+---------------------------
  1 | (1)
  2 | (1, 2, 1)
  3 | (1, 2, 3, 1, 2, 1, 3, 2, 1)
  4 | (1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2,
    |     1, 3, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1)
  5 | (1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1,
    |     2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4,
    |     2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 4, 5, 2, 1, 4, 3,
    |     5, 2, 1, 4, 5, 3, 2, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4,
    |     2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2,
    |     4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 2, 1,
    |     5, 4, 3, 2, 5, 1, 4, 3, 2, 5, 4, 1, 3, 2, 4, 5, 1, 3, 2,
    |     4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 3, 1, 2)
One can consider an initial row 0 of length 0, producing row 1 as concatenation of (), (1), ().
Row 2 results from duplicating row 1 with (2) inserted in the middle.
Row 3 results from making the list of all permutations in row 2, ((1, 2), (2, 1)), then duplicating these and inserting (3), i.e.: ((1, 2, 3, 1, 2), (2, 1, 3, 2, 1)), then merging together with the second instance of the overlapping '2' removed in the middle.
Row 4 results in the same way from row 3, where the permutations are all length 3 substrings except for the middle (1, 2, 1).
Applying the same procedure to row 4 yields a superpermutation of {1, ..., 5} of minimal length 153 which is palindromic as the earlier ones, but not the lexicographically first one, which is given above.

Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
Wikipedia, Superpermutation

Cf. A180632 (row lengths = minimal size of order n superpermutations), A332090 (row n read as base-(n+1) number).

PARI
```
A332089_row(n)=digits(A332090(n),n+1)
```

/* Independent of A332090: */
A332089_row(n)={n>5 && error("not yet implemented"); digits(fromdigits([d-37| d<-Vecsmall(["&", "&:", "&<12:", "&G1HN<3Y2OXG" ":ZO2[:GY3H:RE3YDOZ3P:[EXP>NER2=4ENH=2>P1"][n])],100))}

For n < 5, row n results from row n - 1 by making the list of all substrings which are permutations, duplicating them and inserting (n) between the two copies, and merging them together again, with overlap reduced as much as possible.

A224986 a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).

Original entry on oeis.org

1, 1, 1, 1, 2, 96, 8153726976, 320352637207127391364950814323398779319161580421120

Offset: 1

Nathaniel Johnston, Apr 22 2013

Consider words on n symbols that contain every permutation of those n symbols as contiguous substrings. The minimal length of such a string was conjectured to equal A007489(n) (see A180632). This sequence is a lower bound on the number of distinct (up to relabeling the symbols) such strings of the conjectured minimal length.
It was conjectured in the Ashlock paper that, for all n, there is only one string of length A007489(n) containing all permutations. This sequence shows that this conjecture fails as n grows.
In 2014 Houston has shown that the first conjecture about the minimal length is also false for all n > 5. In particular, A180632(6) <= 872 = A007489(n). - M. F. Hasler, Jul 28 2020
The next term a(9) ~ 2.18e291 is too large to be displayed here. - M. F. Hasler, Jul 29 2020

			a(n) = 1 for n <= 4, which agrees with the fact that the minimal strings containing all permutations in these cases are unique (see A180632).

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

Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
Nathaniel Johnston, The Minimal Superpermutation Problem, 2013.

Cf. A180632, A188428.

seq(product((n-k-2)!^(k*k!),k=1..max(n-4,0)),n=1..8);

apply( {A224986(n)=prod(k=1,n-4,(n-k-2)!^(k*k!))}, [1..8]) \\ M. F. Hasler, Jul 29 2020

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.

A376269 a(n) = n! + (n - 1)! + (n - 2)! + n - 3.

Original entry on oeis.org

3, 9, 33, 152, 867, 5884, 46085, 408246, 4032007, 43908488, 522547209, 6745939210, 93884313611, 1401079680012, 22317642547213, 377917892352014, 6778983923712015, 128403161542656016, 2560949482291200017, 53645489280294912018, 1177524571957493760019, 27027108408834293760020

Offset: 2

Paolo Xausa, Sep 18 2024

a(n) is a lower bound for the length of every superpermutation on n symbols (see links). An upper bound for the length of a minimal superpermutation is given by A341300(n).

Paolo Xausa, Table of n, a(n) for n = 2..400
Anonymous 4chan poster, Robin Houston, Jay Pantone, and Vince Vatter, A lower bound on the length of the shortest superpattern, 2018.
Michael Engen and Vincent Vatter, Containing All Permutations, The American Mathematical Monthly, 128 (1), 2021, pp. 4-24 (preprint version).
James Grime and Brady Haran, Superpermutations, Numberphile video, 2018.
Wikipedia, Superpermutation.

Cf. A054119, A180632, A332089, A341300.

Table[n^2 * (n - 2)! + n - 3, {n, 2, 25}]

from sympy import factorial
def A376269(n): return n**2*factorial(n-2)+n-3 # Chai Wah Wu, Sep 20 2024

a(n) = A054119(n) + n - 3.
E.g.f.: (3 - x - x^2 - exp(x)*(3 - 4*x + x^2) - (1 - x)*x*log(1 - x))/(1 - x). - Stefano Spezia, Sep 18 2024
a(n) = (n-2)!*n^2 + n - 3. - Chai Wah Wu, Sep 20 2024
D-finite with recurrence (-n+1)*a(n) +(n-2)*(n+2)*a(n-1) -(n-1)*(n-3)*a(n-2) -(4*n-7)*(n-4)=0. - R. J. Mathar, Sep 23 2024

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.

A332090 The smallest superpermutation of order n, read as a base n+1 number.

Original entry on oeis.org

1, 16, 112249, 36192508500267905991836

Offset: 1

M. F. Hasler, Jul 28 2020

A superpermutation of order n is a string over the alphabet {1,...,n} such that every permutation of {1,...,n} occurs as a substring.
Such a string is the base n+1 representation of some number. The terms a(n) here are these numbers, corresponding to the lexicographically first superpermutation of minimal length A180632(n). This is the meaning of "smallest" in the name.
It is known that the superpermutations of minimal length are unique only for n < 5. For n = 5 there are 8 inequivalent superpermutations of minimal length 153. The lexicographically first one would correspond to
  a(5) = 27360223915482678295044186051702391878951111088124776744577\
         815578589162223809195375150272260250093757648411736389359241,
  while there is a unique palindromic one corresponding to a larger term, produced by the standard algorithm given in A332089's formula section.
The smallest superpermutation for n = 6 is not yet known for sure. The smallest known has 872 letters, so a(6) ~ 7^870 ~ 10^735, which is too large to be displayed here.

			For n=2, the shortest superpermutation is '121': it contains the permutations (1,2) and (2,1) as substrings. Considered as a number in base 3 this is 1*3^2 + 2*3 + 1 = 16 = a(2).
For n=3, the shortest superpermutation is '123121321': it contains all permutations of {1,2,3} as substrings. As a number written in base 4 this is 1*4^8 + 2*4^7 + ... + 1 = 112249 = a(3).
For n=4, the shortest superpermutation is '123412314231243121342132413214321'. As a number written in base 5 this is 1*5^32 + ... + 2*5 + 1 = 36192508500267905991836 = a(4).
From n=5 on, the shortest superpermutation is no longer unique: there are 8 inequivalent ones of minimal length 153. Only one of them is symmetric with respect to reversal of the digits, which is not the case for the lexicographically first one, which corresponds to the number a(5) ~ 6^152 + 2*6^151 + ... + 1*6 + 2 ~ 2.7e18.

Robin Houston, Tackling the Minimal Superpermutation Problem, arXiv:1408.5108 [math.CO], 2014.
Nathaniel Johnston, Non-uniqueness of minimal superpermutations, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
Wikipedia, Superpermutation.

Cf. A180632, A007489.

SP=[1, 121, 123121321, 123412314231243121342132413214321, fromdigits([d-37| d<-Vecsmall("&G1HN<3Y2OXG:ZO2[:GY3H:RE3YDOZ3P:[EXP>NER2=4ENH=2>P1")], 100)] \\ custom base100 encoding
  A332090(n)=fromdigits(digits(SP[n]),n+1)
/* Alternatively, considering A332089 as the more fundamental sequence: */
A332090(n)=fromdigits(A332089_row(n),n+1)

A341300 a(n) = n! + (n-1)! + (n-2)! + (n-3)! + n - 3.

Original entry on oeis.org

10, 34, 154, 873, 5908, 46205, 408966, 4037047, 43948808, 522910089, 6749568010, 93924230411, 1401558681612, 22323869568013, 378005070643214, 6780291598080015, 128424084332544016, 2561305169719296017, 53651891654000640018, 1177646217057902592019

Offset: 3

N. J. A. Sloane, Feb 13 2021

nonn

a(n) is an upper bound for the length of a minimal superpermutation on n symbols (see links). A lower bound is given by A376269(n). - Paolo Xausa, Sep 27 2024

Michael De Vlieger, Table of n, a(n) for n = 3..449
Michael Engen and Vincent Vatter, Containing all permutations, Amer. Math. Monthly, 128 (2021), 4-24; arXiv preprint, arXiv:1810.08252 [math.CO], 2018-2020.
Wikipedia, Superpermutation.

Cf. A180632, A332089, A376269.

Array[Total[(# - Range[0, 3])!] + # - 3 &, 20, 3] (* Michael De Vlieger, Apr 07 2021 *)

from sympy import factorial
def A341300(n): return (n**2*(n-2)+1)*factorial(n-3)+n-3 # Chai Wah Wu, Sep 20 2024

a(n) = (n-3)!*(n^2*(n-2) + 1) + n - 3. - Chai Wah Wu, Sep 20 2024

A244311 Primes (with d digits, say) that generate another prime when acted on by the "standard" superpermutation of length A007489(d) of d elements (cf. comment).

Original entry on oeis.org

13, 19, 31, 37, 79, 109, 113, 139, 193, 317, 331, 911, 991, 1453, 1481, 1669, 1831, 1901, 7127, 7561, 7589, 7687, 9343, 9413, 9811, 10223, 11821, 12889, 13627, 13633, 16979, 17551, 32297, 33529, 34157, 35747, 37409, 39521, 39829, 70957, 71339, 75653, 79633, 90289, 94793, 97583, 99877

Offset: 1

Abhiram R Devesh, Jun 25 2014

For primes with more than four digits, the sequence is based on the current information about the conjectured minimal length.
Since 2013 it is known that the superpermutations with minimal length are not unique for n > 4, and several ones are known for n = 5, cf. Wikipedia. Accordingly, the sequence is ill-defined if the choice of the superpermutation is not made precise. It also turns out that the 6-digit terms in the b-file correspond to the palindromic superpermutation of length A007489(d) obtained by the standard algorithm described on Wikipedia or Johnston's blog. For n = 5 this is of minimal length but only third in lexicographic order, for n >= 6 it is of non-minimal length. See A332088 for the analog sequence using the lexico-first superpermutation of minimal length and including the single-digit terms. - M. F. Hasler, Jul 28 2020
"Acted on" in the definition means that the digits of the prime are 'selected' according to those of the superpermutation. This sequence uses the palindromic superpermutations generated through the standard recursive algorithm, so the corresponding primes (with A007489(d) digits) are palindromic primes (A002385). - M. F. Hasler, Jul 29 2020

			The super-permutation of 3 objects abc with minimal length is abcabacba.
p = 109 is in this sequence as under the super-permutation with minimal length, the number 109101901 is also prime.

Abhiram R Devesh, Table of n, a(n) for n = 1..74
Nathaniel Johnston, Super Permutation
Wikipedia, Superpermutation

Cf. A007489, A002385, A180632, A332088.

my(s); #SSP=vector(6,n,s=if(n--,my(t);concat([if(#Set(s)A332088 for those of minimal length
is_A244311(n)=ispseudoprime(fromdigits(vecextract(n=digits(n), SSP[#n])))
(A244311_upto(N)=select(is_A244311, primes([1,N])))(10^5) \\ (End)

Definition corrected and keyword 'hard' removed; data and b-file double-checked by M. F. Hasler, Jul 29 2020

cp's OEIS Frontend

A007489 a(n) = Sum_{k=1..n} k!.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A332089 Irregular table read by rows, where row n lists the lexicographically first superpermutation of minimal length over {1, ..., n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A224986 a(n) = Product_{k=1..n-4} (n-k-2)!^(k*k!).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A376269 a(n) = n! + (n - 1)! + (n - 2)! + n - 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

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