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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038155 a(n) = (n!/2) * Sum_{k=0..n-2} 1/k!. 16
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
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
Sequence in context: A280474 A208790 A026112 * A026331 A135490 A345887
KEYWORD
nonn,easy
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)