login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056542 a(n) = n*a(n-1) + 1, a(1) = 0. 18
0, 1, 4, 17, 86, 517, 3620, 28961, 260650, 2606501, 28671512, 344058145, 4472755886, 62618582405, 939278736076, 15028459777217, 255483816212690, 4598708691828421, 87375465144740000, 1747509302894800001 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

REFERENCES

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.

LINKS

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)

FORMULA

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

EXAMPLE

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

MATHEMATICA

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

PROG

(Haskell)

a056542 n = a056542_list !! (n-1)

a056542_list = 0 : map (+ 1) (zipWith (*) [2..] a056542_list)

-- Reinhard Zumkeller, Mar 24 2013

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

CROSSREFS

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.

Sequence in context: A020074 A163071 A321384 * A331158 A110508 A114190

Adjacent sequences:  A056539 A056540 A056541 * A056543 A056544 A056545

KEYWORD

easy,nonn

AUTHOR

Henry Bottomley, Jun 20 2000

EXTENSIONS

More terms from James A. Sellers, Jul 04 2000

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 22:16 EST 2020. Contains 331177 sequences. (Running on oeis4.)