login
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 comparisons required to find j in step L2.2'.
11

%I #21 May 28 2024 18:27:10

%S 0,4,25,156,1099,8800,79209,792100,8713111,104557344,1359245485,

%T 19029436804,285441552075,4567064833216,77640102164689,

%U 1397521838964420,26552914940323999,531058298806480000,11152224274936080021

%N 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 comparisons required to find j in step L2.2'.

%C The asymptotic value for large n is 0.21828...*n! See also comment for A079884

%D See under A079884

%H Hugo Pfoertner, <a href="https://www.randomwalk.de/sequences/lpgcount.txt">FORTRAN program for lexicographic permutation generation</a>.

%F a(3)=0, a(n) = n * a(n-1) + n for n >= 4.

%F a(n) = Sum_{j=3..n} (n+1)!/j!. - _Zerinvary Lajos_, Oct 20 2006

%F For n >= 3, a(n) = floor((e - 5/2)*n! - 1/2). - _Benoit Cloitre_, Aug 03 2007

%p a:=n->sum((n+1)!/j!,j=3..n): seq(a(n), n=2..20); # _Zerinvary Lajos_, Oct 20 2006

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

%o (Fortran) c Program available at link.

%Y Cf. A079884, A079751, A079752, A079753, A079754, A079755, A079756.

%K easy,nonn

%O 3,2

%A _Hugo Pfoertner_, Jan 14 2003

%E Edited and extended by _Robert G. Wilson v_, Jan 22 2003