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,3

Comments

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

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

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

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

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.

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.

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.

Wikipedia, Bogosort

Index entries for sequences related to factorial numbers

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 9 2024

Example

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

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

Prog

(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

Crossrefs

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

Row sums of A268216.

Sequence in context: A367242 A052512 A166554 * A296964 A261047 A052846

Adjacent sequences: A038153 A038154 A038155 * A038157 A038158 A038159

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

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

Status

approved