A038156 a(n) = n! * Sum_{k=1..n-1} 1/k!.

0, 0, 2, 9, 40, 205, 1236, 8659, 69280, 623529, 6235300, 68588311, 823059744, 10699776685, 149796873604, 2246953104075, 35951249665216, 611171244308689, 11001082397556420, 209020565553571999, 4180411311071440000, 87788637532500240021, 1931350025715005280484

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• changed

Comments

Related to number of operations of addition and multiplication to evaluate a determinant of order n by cofactor expansion - see A026243.

Also number of operations needed 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 number of comparisons required to find j in step L2 (see answer to exercise 5). - Hugo Pfoertner, Jan 24 2003

For n>1, the number of possible ballots where there are n candidates and voters may identify their top m most preferred ones, where 0 < m < n. - Shaye Horwitz, Jun 28 2011

For n > 1, a(n) is the expected number of comparisons required to sort a random list of n distinct elements using the "bogosort" algorithm. - Andrew Slattery, Jun 02 2022

The number of permutations of all proper nonempty subsets of an n element set. - P. Christopher Staecker, May 09 2024

Examples

			a(2) = floor((2.718... - 1)*2) - 1 = 3 - 1 = 2,
a(3) = floor((2.718... - 1)*6) - 1 = 10 - 1 = 9.
		

References

• D. E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 2. Generating All Tuples and Permutations, Addison-Wesley, 2005.

Links

• Georg Fischer, Table of n, a(n) for n = 0..200 [first 28 terms from _Vincenzo Librandi_]
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 836
• G. A. Kamel, Partial Chain Topologies on Finite Sets, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.
• Hugo Pfoertner, FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation.
• Wikipedia, Bogosort
• Index entries for sequences related to factorial numbers

Crossrefs

Cf. A000522, A007526, A038155, A056542, A079884, A079750.

Row sums of A119741.

Programs

Maple

a:= proc(n) option remember;
      `if`(n<2, 0, a(n-1)*n+n)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 11 2020

Mathematica

a=1; Join[{0},Table[a=(a-1)*(n+1);Abs[a],{n,0,60}]] (* Vladimir Joseph Stephan Orlovsky, Nov 20 2009; 0 prefixed by _Georg Fischer Apr 11 2020 *)
Join[{0},FoldList[#1*#2 + #2 + #1 + 1 &, 0, Range@ 20]] (* Robert G. Wilson v, Feb 21 2015 *)

PARI

a(n)=floor((exp(1)-1)*n!-1) \\ Charles R Greathouse IV, Jun 29 2011

PARI

a(n)=(expm1(1)*n!-1)\1 \\ Charles R Greathouse IV, Jan 28 2014

Formula

a(n) = floor((e-1)*n!) - 1.

a(0) = a(1) = 0, a(n) = n*(a(n-1) + 1) for n>1. - Philippe Deléham, Oct 16 2009

E.g.f.: (exp(x) - 1)*x/(1 - x). - Ilya Gutkovskiy, Jan 26 2017

a(n) = A002627(n)-1, n>=1. - R. J. Mathar, Jan 03 2018

a(n) = A000522(n)-n!-1, n>=1. - P. Christopher Staecker, May 09 2024

Extensions

a(28) ff. corrected by Georg Fischer, Apr 11 2020