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.

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

Offset

2,2

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

Table of n, a(n) for n=2..20.

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

FORTRAN implementation of Knuth's Algorithms L for lexicographic permutation generation.

Formula

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.

Prog

FORTRAN program available at link.

Crossrefs

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

Sequence in context: A027209 A209807 A351588 * A177140 A372411 A027233

Adjacent sequences: A080045 A080046 A080047 * A080049 A080050 A080051

Keyword

nonn

Author

Hugo Pfoertner, Jan 24 2003

Status

approved