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

Author

Hugo Pfoertner, Jan 16 2003

Keywords

• nonn

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

Crossrefs

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

Programs

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}]

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

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

Extensions

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