A079756 Operation count to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives number of interchanges in reversal step.

0, 0, 4, 29, 215, 1734, 15630, 156327, 1719637, 20635688, 268264004, 3755696121, 56335441899, 901367070474, 15323240198170, 275818323567179, 5240548147776545, 104810962955531052, 2201030222066152272

Offset

3,3

Comments

The asymptotic value for large n is 0.04308...*n! = (e+1/e-3)/2 * n! See also comment for A079884.

References

See under A079884

Links

Indranil Ghosh, Table of n, a(n) for n = 3..101

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation

Formula

a(3)=0, a(4)=0, a(n) = n*a(n-1) + (n-1)*(floor((n-1)/2)-1) for n>=5.

For n>=3, a(n) = floor(c*n!-(n-3)/2) where c = lim_{n->infinity} a(n)/n! = 0.04308063481524377... - Benoit Cloitre, Jan 19 2003

Recurrence: (n-5)*(n-3)*(n-2)*a(n) = (n-3)*(n^3 - 7*n^2 + 11*n - 1)*a(n-1) - (n-1)*(2*n - 5)*a(n-2) - (n-4)*(n-2)^2*(n-1)*a(n-3). - Vaclav Kotesovec, Mar 16 2014

Mathematica

a[3] = 0; a[4] = 0; a[n_] := n*a[n - 1] + (n - 1)*(Floor[(n - 1)/2] - 1); Table[a[n ], {n, 3, 21}]

Prog

FORTRAN program available at link
(Python)
l=[0, 0, 0, 0, 0]
for n in range(5, 22):
    l.append(n*l[n - 1] + (n - 1)*((n - 1)//2 - 1))
print(l[3:]) # Indranil Ghosh, Jul 18 2017

Crossrefs

Cf. A079884, A079750, A079751, A079752, A079753, A079754, A079755.

Sequence in context: A001883 A281600 A135429 * A344098 A221415 A087809

Adjacent sequences: A079753 A079754 A079755 * A079757 A079758 A079759

Keyword

nonn

Author

Hugo Pfoertner, Jan 16 2003

Extensions

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

Status

approved