A038156 - OEIS

%I #90 Jun 14 2024 15:00:11

%S 0,0,2,9,40,205,1236,8659,69280,623529,6235300,68588311,823059744,

%T 10699776685,149796873604,2246953104075,35951249665216,

%U 611171244308689,11001082397556420,209020565553571999,4180411311071440000,87788637532500240021,1931350025715005280484

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

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

%C 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

%C 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

%C 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

%C The number of permutations of all proper nonempty subsets of an n element set. - _P. Christopher Staecker_, May 09 2024

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

%H Georg Fischer, <a href="/A038156/b038156.txt">Table of n, a(n) for n = 0..200</a> [first 28 terms from _Vincenzo Librandi_]

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=836">Encyclopedia of Combinatorial Structures 836</a>

%H G. A. Kamel, <a href="http://www.aascit.org/journal/archive2?journalId=928&amp;paperId=2310">Partial Chain Topologies on Finite Sets</a>, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.

%H Hugo Pfoertner, <a href="https://www.randomwalk.de/sequences/lpure.txt">FORTRAN implementation of Knuth's Algorithm L for lexicographic permutation generation</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Bogosort">Bogosort</a>

%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>

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

%F a(0) = a(1) = 0, a(n) = n*(a(n-1) + 1) for n>1. - _Philippe Deléham_, Oct 16 2009

%F E.g.f.: (exp(x) - 1)*x/(1 - x). - _Ilya Gutkovskiy_, Jan 26 2017

%F a(n) = A002627(n)-1, n>=1. - _R. J. Mathar_, Jan 03 2018

%F a(n) = A000522(n)-n!-1, n>=1. - _P. Christopher Staecker_, May 09 2024

%e a(2) = floor((2.718... - 1)*2) - 1 = 3 - 1 = 2,

%e a(3) = floor((2.718... - 1)*6) - 1 = 10 - 1 = 9.

%p a:= proc(n) option remember;

%p       `if`(n<2, 0, a(n-1)*n+n)

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Apr 11 2020

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

%t Join[{0},FoldList[#1*#2 + #2 + #1 + 1 &, 0, Range@ 20]] (* _Robert G. Wilson v_, Feb 21 2015 *)

%o (PARI) a(n)=floor((exp(1)-1)*n!-1) \\ _Charles R Greathouse IV_, Jun 29 2011

%o (PARI) a(n)=(expm1(1)*n!-1)\1 \\ _Charles R Greathouse IV_, Jan 28 2014

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

%Y Row sums of A268216.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E a(28) ff. corrected by _Georg Fischer_, Apr 11 2020