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
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
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
KEYWORD
nonn,easy
AUTHOR
STATUS
approved