login
a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.
16

%I #32 Jun 04 2017 08:01:16

%S 0,0,1,6,30,160,975,6846,54796,493200,4932045,54252550,651030666,

%T 8463398736,118487582395,1777313736030,28437019776600,483429336202336,

%U 8701728051642201,165332832981201990,3306656659624039990,69439789852104840000

%N a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!.

%C For n>=2, a(n) gives the operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2. Sequence gives the number of comparisons required to find the first interchangeable element in step L3 (see answer to exercise 5). - _Hugo Pfoertner_, Jan 27 2003

%C a(n) mod 5 = A011658(n+1). - _G. C. Greubel_, Apr 13 2016

%C a(450) has 1001 decimal digits. - _Michael De Vlieger_, Apr 13 2016

%C Also the number of (undirected) paths in the complete graph K_n. - _Eric W. Weisstein_, Jun 04 2017

%D D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.

%H Michael De Vlieger, <a href="/A038155/b038155.txt">Table of n, a(n) for n = 0..449</a>

%H D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz">TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations)</a>.

%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/lpure.txt">FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteGraph.html">Complete Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphPath.html">Graph Path</a>

%F a(n) = 1/2*floor(n!*exp(1)-n-1), n>0. - _Vladeta Jovovic_, Aug 18 2002

%F E.g.f.: x^2/2*exp(x)/(1-x). - _Vladeta Jovovic_, Aug 25 2002

%F a(n) = Sum_{k=0..n-1} a(n-1) + k, a(0)=0. - _Ilya Gutkovskiy_, Apr 13 2016

%F a(n) = A038154(n)/2. - _Alois P. Heinz_, Jan 26 2017

%p A038155:=n->(n!/2)*add(1/k!, k=0..n-2): seq(A038155(n), n=0..30); # _Wesley Ivan Hurt_, Apr 16 2016

%t RecurrenceTable[{a[0] == 0, a[n] == Sum[a[n - 1] + k, {k, 0, n - 1}]}, a, {n, 21}] (* _Ilya Gutkovskiy_, Apr 13 2016 *)

%t Table[(n!/2) Sum[1/k!, {k, 0, n - 2}], {n, 0, 21}] (* _Michael De Vlieger_, Apr 13 2016 *)

%t Table[1/2 E (n - 1) n Gamma[n - 1, 1], {n, 0, 20}] (* _Eric W. Weisstein_, Jun 04 2017 *)

%t Table[If[n == 0, 0, Floor[n! E - n - 1]/2], {n, 0, 20}] (* _Eric W. Weisstein_, Jun 04 2017 *)

%Y Cf. A011658, A038154, A038156, A056542, A079752, A079884, A080047, A080048, A080049.

%K nonn,easy

%O 0,4

%A _N. J. A. Sloane_