A080049 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 interchange operations in step L4.

0, 2, 11, 63, 388, 2734, 21893, 197069, 1970726, 21678036, 260136487, 3381774403, 47344841720, 710172625898, 11362762014473, 193166954246169, 3477005176431178, 66063098352192544, 1321261967043851051, 27746501307920872271, 610423028774259190172, 14039729661807961374198

Offset

2,2

References

Donald E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 2, Generating All Tuples and Permutations. Addison-Wesley (2005). Chapter 7.2.1.2, 39-40.

Links

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

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

R. J. Ord-Smith, Generation of permutation sequences: Part 1, Computer J., 13 (1970), 151-155.

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

Formula

a(2)=0, a(n)=n*a(n-1) + (n-1)*floor((n-1)/2).

c = limit n ->infinity a(n)/n! = 0.5430806.. = (e+1/e)/2-1 = A073743 - 1.

a(n) = floor (c*n! - (n-1)/2) for n>=2.

Prog

(Fortran) c FORTRAN program available at Pfoertner link.

Crossrefs

Cf. A080047, A080048, A038155, A038156, A056542, A073743, A079756, A080047, A080048.

Sequence in context: A065928 A188648 A114175 * A370392 A126745 A362799

Adjacent sequences: A080046 A080047 A080048 * A080050 A080051 A080052

Keyword

nonn,easy

Author

Hugo Pfoertner, Jan 24 2003

Status

approved