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

Author

Hugo Pfoertner, Jan 24 2003

Keywords

• nonn
• easy

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

• 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.

Crossrefs

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

Programs

Fortran

c FORTRAN program available at Pfoertner link.

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.