

A056542


a(n) = n*a(n1) + 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 n1 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 nonisomorphic 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. Prefascicle 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, Prefascicle 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), 137164.
Sam Wagstaff, Factorizations of a(51) through a(90)


FORMULA

a(n) = floor((e2)*n!).
a(n) = A002627(n)  n!.
a(n) = A000522(n)  2*n!.
a(n) = n!  A056543(n).
a(n) = (n1)*(a(n1) + a(n2)) + 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 !! (n1)
a056542_list = 0 : map (+ 1) (zipWith (*) [2..] a056542_list)
 Reinhard Zumkeller, Mar 24 2013
(MAGMA) [n le 2 select n1 else n*Self(n1)+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



