%I #12 May 04 2018 02:57:30
%S 0,2,11,63,388,2734,21893,197069,1970726,21678036,260136487,
%T 3381774403,47344841720,710172625898,11362762014473,193166954246169,
%U 3477005176431178,66063098352192544,1321261967043851051
%N 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.
%D 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.
%H D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz">TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations)</a>.
%H R. J. Ord-Smith, <a href="https://doi.org/10.1093/comjnl/13.2.152">Generation of permutation sequences: Part 1</a>, Computer J., 13 (1970), 151-155.
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/lpure.txt">FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation</a>.
%F a(2)=0, a(n)=n*a(n-1) + (n-1)*floor((n-1)/2).
%F c = limit n ->infinity a(n)/n! = 0.5430806.. = (e+1/e)/2-1.
%F a(n) = floor (c*n! - (n-1)/2) for n>=2.
%o FORTRAN program available at Pfoertner link
%Y Cf. A080047, A080048, A038155, A038156, A056542, A079756.
%K nonn
%O 2,2
%A _Hugo Pfoertner_, Jan 24 2003
|