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

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.

Links

Table of n, a(n) for n=3..20.

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

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 link.

Crossrefs

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

Sequence in context: A198797 A057835 A232145 * A197176 A264461 A006184

Adjacent sequences: A079752 A079753 A079754 * A079756 A079757 A079758

Keyword

nonn

Author

Hugo Pfoertner, Jan 16 2003

Extensions

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

Status

approved