login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!. 12
0, 0, 1, 6, 30, 160, 975, 6846, 54796, 493200, 4932045, 54252550, 651030666, 8463398736, 118487582395, 1777313736030, 28437019776600, 483429336202336, 8701728051642201, 165332832981201990, 3306656659624039990, 69439789852104840000 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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

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

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 *)

CROSSREFS

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

Sequence in context: A280474 A208790 A026112 * A026331 A135490 A345887

Adjacent sequences:  A038152 A038153 A038154 * A038156 A038157 A038158

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 5 22:41 EDT 2021. Contains 346488 sequences. (Running on oeis4.)