A056543 -id:A056543 - 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

A082425 a(1)=1, a(n) = -1 + n*Sum_{j=1..n-1} a(j).

Original entry on oeis.org

1, 1, 5, 27, 169, 1217, 9939, 90871, 920069, 10222989, 123698167, 1619321459, 22805443881, 343835923129, 5525934478859, 94309281772527, 1703461402016269, 32465970250192421, 651123070017747999, 13707854105636799979, 302258183029291439537, 6966331456484621749329

Offset: 1

Benoit Cloitre, Apr 24 2003

nonn

G. C. Greubel, Table of n, a(n) for n = 1..445

Cf. A001339, A056543, A083746.

Cf. A007808, A074143, A082427, A082428, A082430, A383436, A383437.

[n le 2 select 1 else (n^2*Self(n-1) +1)/(n-1): n in [1..30]]; // G. C. Greubel, Feb 03 2024

a:= n -> n*n!*add(1/(k*(k-1)*k!), k = 2..n): seq(a(n), n = 2..20); # Peter Bala, Jul 09 2008

a[n_]:= a[n]= If[n<3, 1, -1 +n*Sum[a[j], {j,n-1}]];
Table[a[n], {n,40}] (* G. C. Greubel, Feb 03 2024 *)

@CachedFunction # a = A082425
def a(n): return 1 if (n==1) else -1 + n*sum(a(j) for j in range(1,n))
[a(n) for n in range(1,41)] # G. C. Greubel, Feb 03 2024

For n >= 2, a(n) = floor(n*(3-e)*n!).
a(n) = n*A056543(n) - 1, n > 1. - Vladeta Jovovic, Apr 26 2003
From Peter Bala, Jul 09 2008: (Start)
In the following remarks we use an offset of 1, i.e., a(1) = 1, a(2) = 1, a(3) = 5, ... .
  For n >= 2, a(n) = n*n!*Sum_{k = 2..n} 1/(k*(k-1)*k!).
  For n >= 2, a(n) = 3*n*n! - Sum_{k = 0..n} (k+1)!*binomial(n,k).
  Limit_{n -> oo} a(n)/(n*n!) = 3 - e.
  E.g.f.: 1 + t + (3*t - exp(t))/(1-t)^2.
  a(n) = A083746(n+2) - A001339(n).
Recurrence relation: a(1) = 1, a(2) = 1, a(3) = 5, a(n) = (n+2)*a(n-1) - (n-1)*a(n-2) for n >= 4.
Recurrence relation: a(1) = 1, a(2) = 1, a(n) = (n^2*a(n-1) + 1)/(n-1) for n >= 3.
The recurrence relation x(n) = (n^2*x(n-1) - 1)/(n-1), for n >= 2, has the general solution x(n) = n*n!*x(1) - a(n); particular solutions are A007808 (x(1) = 1) and A001339 (x(1) = 3). (End)

Offset corrected by G. C. Greubel, Feb 03 2024

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