A080047 -id:A080047 - cp's OEIS frontend

A056542 a(n) = n*a(n-1) + 1, a(1) = 0.

0, 1, 4, 17, 86, 517, 3620, 28961, 260650, 2606501, 28671512, 344058145, 4472755886, 62618582405, 939278736076, 15028459777217, 255483816212690, 4598708691828421, 87375465144740000, 1747509302894800001, 36697695360790800022, 807349297937397600485

Offset: 1

Henry Bottomley, Jun 20 2000

For n >= 2 also operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of loop repetitions of the j search loop in step L2. - Hugo Pfoertner, Feb 06 2003
More directly: sum over all permutations of length n-1 of the product of the length of the first increasing run by the value of the first position. The recurrence follows from this definition. - Olivier Gérard, Jul 07 2011
This sequence shares divisibility properties with A000522; each of the primes in A072456 divide only a finite number of terms of this sequence. - T. D. Noe, Jul 07 2005
This sequence also represents the number of subdeterminant evaluations when calculation a determinant by Laplace recursive method. - Reinhard Muehlfeld, Sep 14 2010
Also, a(n) equals the number of non-isomorphic directed graphs of n+1 vertices with 1 component, where each vertex has exactly one outgoing edge, excluding loops and cycle graphs. - Stephen Dunn, Nov 30 2019

			a(4) = 4*a(3) + 1 = 4*4 + 1 = 17.
Permutations of order 3 .. Length of first run * First position
123..3*1
132..2*1
213..1*2
231..2*2
312..1*3
321..1*3
a(4) = 3+2+2+4+3+3 = 17. - _Olivier Gérard_, Jul 07 2011

D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.

T. D. Noe, Table of n, a(n) for n = 1..100
D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
Tom Muller, Prime and Composite Terms in Sloane's Sequence A056542, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.3. [Includes factorizations of a(1) through a(50)]
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
R. Sedgewick, Permutation generation methods, Computing Surveys, 9 (1977), 137-164.
Sam Wagstaff, Factorizations of a(51) through a(90)

Cf. A079751 (same recursion formula, but starting from a(3)=0), A038155, A038156, A080047, A080048, A080049.
Cf. A007808, A002627.
Equals the row sums of A162995 triangle (n>=2). - Johannes W. Meijer, Jul 21 2009
Cf. A073333, A002627, A185108.
Cf. A329426, A329427.
Cf. A070213 (indices of primes).

a056542 n = a056542_list !! (n-1)
a056542_list = 0 : map (+ 1) (zipWith (*) [2..] a056542_list)
-- Reinhard Zumkeller, Mar 24 2013

[n le 2 select n-1 else n*Self(n-1)+1: n in [1..20]]; // Bruno Berselli, Dec 13 2013

tmp=0; Join[{tmp}, Table[tmp=n*tmp+1, {n, 2, 100}]] (* T. D. Noe, Jul 12 2005 *)
FoldList[ #1*#2 + 1 &, 0, Range[2, 21]] (* Robert G. Wilson v, Oct 11 2005 *)

a(n) = floor((e-2)*n!).
a(n) = A002627(n) - n!.
a(n) = A000522(n) - 2*n!.
a(n) = n! - A056543(n).
a(n) = (n-1)*(a(n-1) + a(n-2)) + 2, n > 2. - Gary Detlefs, Jun 22 2010
1/(e - 2) = 2! - 2!/(1*4) - 3!/(4*17) - 4!/(17*86) - 5!/(86*517) - ... (see A002627 and A185108). - Peter Bala, Oct 09 2013
E.g.f.: (exp(x) - 1 - x) / (1 - x). - Ilya Gutkovskiy, Jun 26 2022

More terms from James Sellers, Jul 04 2000

A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

Original entry on oeis.org

0, 0, 1, 6, 30, 160, 975, 6846, 54796, 493200, 4932045, 54252550, 651030666, 8463398736, 118487582395, 1777313736030, 28437019776600, 483429336202336, 8701728051642201, 165332832981201990, 3306656659624039990, 69439789852104840000

Offset: 0

N. J. A. Sloane

For n>=2, a(n) gives the operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives the number of comparisons required to find the first interchangeable element in step L3 (see answer to exercise 5). - Hugo Pfoertner, Jan 27 2003
a(n) mod 5 = A011658(n+1). - G. C. Greubel, Apr 13 2016
a(450) has 1001 decimal digits. - Michael De Vlieger, Apr 13 2016
Also the number of (undirected) paths in the complete graph K_n. - Eric W. Weisstein, Jun 04 2017

D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.

Michael De Vlieger, Table of n, a(n) for n = 0..449
D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Path

Cf. A011658, A038154, A038156, A056542, A079752, A079884, A080047, A080048, A080049.

A038155:=n->(n!/2)*add(1/k!, k=0..n-2): seq(A038155(n), n=0..30); # Wesley Ivan Hurt, Apr 16 2016

RecurrenceTable[{a[0] == 0, a[n] == Sum[a[n - 1] + k, {k, 0, n - 1}]}, a, {n, 21}] (* Ilya Gutkovskiy, Apr 13 2016 *)
Table[(n!/2) Sum[1/k!, {k, 0, n - 2}], {n, 0, 21}] (* Michael De Vlieger, Apr 13 2016 *)
Table[1/2 E (n - 1) n Gamma[n - 1, 1], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)
Table[If[n == 0, 0, Floor[n! E - n - 1]/2], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)

a(n) = 1/2*floor(n!*exp(1)-n-1), n>0. - Vladeta Jovovic, Aug 18 2002
E.g.f.: x^2/2*exp(x)/(1-x). - Vladeta Jovovic, Aug 25 2002
a(n) = Sum_{k=0..n-1} a(n-1) + k, a(0)=0. - Ilya Gutkovskiy, Apr 13 2016
a(n) = A038154(n)/2. - Alois P. Heinz, Jan 26 2017

A080048 Operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of loop repetitions in reversal step.

Original entry on oeis.org

1, 7, 34, 182, 1107, 7773, 62212, 559948, 5599525, 61594835, 739138086, 9608795202, 134523132919, 2017846993897, 32285551902472, 548854382342168, 9879378882159177, 187708198761024543, 3754163975220491050

Offset: 2

Hugo Pfoertner, Jan 24 2003

D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.

Cf. A038155, A038156, A056542, A080047, A080049, A079755.

Fortran
```
! Program available at link.
```

a(2)=1, a(n)=n*a(n-1) + (n-1)*floor[(n+1)/2] for n>=3.

c = limit n --> infinity a(n)/n! = 1.54308063481524377826 = (e+1/e)/2, a(n) = floor [c*n!-(n+1)/2] for n>=2.

A080049 Operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of interchange operations in step L4.

Original entry on oeis.org

0, 2, 11, 63, 388, 2734, 21893, 197069, 1970726, 21678036, 260136487, 3381774403, 47344841720, 710172625898, 11362762014473, 193166954246169, 3477005176431178, 66063098352192544, 1321261967043851051, 27746501307920872271, 610423028774259190172, 14039729661807961374198

Offset: 2

Hugo Pfoertner, Jan 24 2003

Donald E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 2, Generating All Tuples and Permutations. Addison-Wesley (2005). Chapter 7.2.1.2, 39-40.

D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
R. J. Ord-Smith, Generation of permutation sequences: Part 1, Computer J., 13 (1970), 151-155.
Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.

Cf. A080047, A080048, A038155, A038156, A056542, A073743, A079756, A080047, A080048.

c FORTRAN program available at Pfoertner link.

a(2)=0, a(n)=n*a(n-1) + (n-1)*floor((n-1)/2).
c = limit n ->infinity a(n)/n! = 0.5430806.. = (e+1/e)/2-1 = A073743 - 1.
a(n) = floor (c*n! - (n-1)/2) for n>=2.

cp's OEIS Frontend

A056542 a(n) = n*a(n-1) + 1, a(1) = 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Formula

Extensions

A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A080048 Operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of loop repetitions in reversal step.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Fortran

Formula

A080049 Operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of interchange operations in step L4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Fortran

Formula