Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #6 Mar 31 2012 10:29:02
%S 1,7,34,182,1107,7773,62212,559948,5599525,61594835,739138086,
%T 9608795202,134523132919,2017846993897,32285551902472,548854382342168,
%U 9879378882159177,187708198761024543,3754163975220491050
%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 loop repetitions in reversal step.
%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 <a href="http://www.randomwalk.de/sequences/lpure.txt">FORTRAN implementation of Knuth's Algorithms L for lexicographic permutation generation</a>.
%F 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.
%o FORTRAN program available at link.
%Y Cf. A038155, A038156, A056542, A080047, A080049, A079755.
%K nonn
%O 2,2
%A _Hugo Pfoertner_, Jan 24 2003