A080047 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 times l has to be repeatedly decreased in step L3.

0, 1, 7, 41, 256, 1807, 14477, 130321, 1303246, 14335751, 172029067, 2236377937, 31309291196, 469639368031, 7514229888601, 127741908106337, 2299354345914202, 43687732572369991, 873754651447399991

Offset

2,3

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

Vincenzo Librandi, Table of n, a(n) for n = 2..200

D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).

Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithms L for lexicographic permutation generation

Formula

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

E.g.f.: (2-exp(x)*(x^2-2*x+2))/(2*(x-1)). - Vaclav Kotesovec, Oct 21 2012

Mathematica

Transpose[NestList[{First[#]+1, (First[#]+1)Last[#]+(First[#](First[#]-1))/2}&, {2, 0}, 20]][[2]] (* Harvey P. Dale, Feb 27 2012 *)
Rest[Rest[CoefficientList[Series[(2-Exp[x]*(x^2-2*x+2))/(2*(x-1)), {x, 0, 20}], x]*Range[0, 20]!]] (* Vaclav Kotesovec, Oct 21 2012 *)

Prog

FORTRAN program available at Pfoertner link.

Crossrefs

Cf. A038155, A038156, A056542, A080048, A080049, A079754.

Sequence in context: A115137 A036730 A258941 * A297671 A356298 A125120

Adjacent sequences: A080044 A080045 A080046 * A080048 A080049 A080050

Keyword

nonn

Author

Hugo Pfoertner, Jan 25 2003

Status

approved