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

0, 0, 1, 6, 30, 160, 975, 6846, 54796, 493200, 4932045, 54252550, 651030666, 8463398736, 118487582395, 1777313736030, 28437019776600, 483429336202336, 8701728051642201, 165332832981201990, 3306656659624039990, 69439789852104840000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

a(n) mod 5 = A011658(n+1). - G. C. Greubel, Apr 13 2016

a(450) has 1001 decimal digits. - Michael De Vlieger, Apr 13 2016

Also the number of (undirected) paths in the complete graph K_n. - Eric W. Weisstein, Jun 04 2017

References

• 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.

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..449
• D. E. Knuth, TAOCP Vol. 4, Pre-fascicle 2b (generating all permutations).
• Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
• Eric Weisstein's World of Mathematics, Complete Graph
• Eric Weisstein's World of Mathematics, Graph Path

Crossrefs

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

Programs

Maple

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

Mathematica

RecurrenceTable[{a[0] == 0, a[n] == Sum[a[n - 1] + k, {k, 0, n - 1}]}, a, {n, 21}] (* Ilya Gutkovskiy, Apr 13 2016 *)
Table[(n!/2) Sum[1/k!, {k, 0, n - 2}], {n, 0, 21}] (* Michael De Vlieger, Apr 13 2016 *)
Table[1/2 E (n - 1) n Gamma[n - 1, 1], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)
Table[If[n == 0, 0, Floor[n! E - n - 1]/2], {n, 0, 20}] (* Eric W. Weisstein, Jun 04 2017 *)

Formula

a(n) = 1/2*floor(n!*exp(1)-n-1), n>0. - Vladeta Jovovic, Aug 18 2002

E.g.f.: x^2/2*exp(x)/(1-x). - Vladeta Jovovic, Aug 25 2002

a(n) = Sum_{k=0..n-1} a(n-1) + k, a(0)=0. - Ilya Gutkovskiy, Apr 13 2016

a(n) = A038154(n)/2. - Alois P. Heinz, Jan 26 2017