A079755 Operation count to create all permutations of n distinct elements using the "streamlined" version of Knuth's Algorithm L (lexicographic permutation generation).

0, 3, 23, 148, 1054, 8453, 76109, 761126, 8372436, 100469287, 1306100803, 18285411320, 274281169898, 4388498718473, 74604478214169, 1342880607855178, 25514731549248544, 510294630984971051, 10716187250684392271, 235756119515056630172, 5422390748846302494198, 130137377972311259861005

Offset: 3

Author

Hugo Pfoertner, Jan 16 2003

Keywords

• nonn

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.

Links

• Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

Crossrefs

Cf. A079884, A079750, A079751, A079752, A079753, A079754, A079756, A079885.

Programs

Fortran

Program available at Pfoertner link.

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 *)

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

Extensions

More terms from Benoit Cloitre and Robert G. Wilson v, Jan 19 2003