A080049 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; graph; refs; listen; history; text; internal format)

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