login
A079755
Operation count to create all permutations of n distinct elements using the "streamlined" version of Knuth's Algorithm L (lexicographic permutation generation).
8
0, 3, 23, 148, 1054, 8453, 76109, 761126, 8372436, 100469287, 1306100803, 18285411320, 274281169898, 4388498718473, 74604478214169, 1342880607855178, 25514731549248544, 510294630984971051, 10716187250684392271, 235756119515056630172, 5422390748846302494198, 130137377972311259861005
OFFSET
3,2
COMMENTS
Sequence gives number of loop repetitions in reversal step.
The asymptotic value for large n is 0.20975...*n! = (e + 1/e - 8/3)/2 * n!. See also comment for A079884.
REFERENCES
Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2.
See also under A079884.
FORMULA
a(3) = 0, a(n) = n * a(n - 1) + (n - 1)*floor((n - 1)/2) for n >= 4.
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
MATHEMATICA
a[3] = 0; a[n_] := n*a[n - 1] + (n - 1)*Floor[(n - 1)/2]; Table[a[n], {n, 3, 21}]
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 *)
PROG
(Fortran) Program available at Pfoertner link.
KEYWORD
nonn
AUTHOR
Hugo Pfoertner, Jan 16 2003
EXTENSIONS
More terms from Benoit Cloitre and Robert G. Wilson v, Jan 19 2003
STATUS
approved