A079752 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

A079752

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 times the search for an element exchangeable with a_j has to be started.

0, 2, 13, 82, 579, 4638, 41749, 417498, 4592487, 55109854, 716428113, 10029993594, 150449903923, 2407198462782, 40922373867309, 736602729611578, 13995451862619999, 279909037252399998, 5878089782300399977

(list; graph; refs; listen; history; text; internal format)

OFFSET

3,2

COMMENTS

The asymptotic value for large n is 0.11505...*n! = (17/6-e)*n!. See also comment for A079884

LINKS

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

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.

FORMULA

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

MATHEMATICA

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