|
%I #19 May 31 2019 17:37:07
%S 0,3,23,148,1054,8453,76109,761126,8372436,100469287,1306100803,
%T 18285411320,274281169898,4388498718473,74604478214169,
%U 1342880607855178,25514731549248544,510294630984971051
%N Operation count to create all permutations of n distinct elements using the "streamlined" version of Knuth's Algorithm L (lexicographic permutation generation).
%C Sequence gives number of loop repetitions in reversal step.
%C The asymptotic value for large n is 0.20975...*n! = (e + 1/e - 8/3)/2 * n!. See also comment for A079884.
%D Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2.
%D See also under A079884.
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/lpgcount.txt">FORTRAN program for lexicographic permutation generation</a>
%F a(3) = 0, a(n) = n * a(n - 1) + (n - 1)*floor((n - 1)/2) for n >= 4.
%F a(n) = floor(c*n! - (n - 1)/2) for n > 4, where c = lim n -> infinity a(n)/n! = 0.209747301481910445... - _Benoit Cloitre_, Jan 19 2003
%t a[3] = 0; a[n_] := n*a[n - 1] + (n - 1)*Floor[(n - 1)/2]; Table[a[n], {n, 3, 21}]
%t RecurrenceTable[{a[3]==0,a[n]==n*a[n-1]+(n-1)Floor[(n-1)/2]},a,{n,20}] (* _Harvey P. Dale_, May 31 2019 *)
%o FORTRAN program available at link.
%Y Cf. A079884, A079750, A079751, A079752, A079753, A079754, A079756, A079885.
%K nonn
%O 3,2
%A _Hugo Pfoertner_, Jan 16 2003
%E More terms from _Benoit Cloitre_ and _Robert G. Wilson v_, Jan 19 2003
| 