OFFSET
0,3
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
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
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
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
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
a(28) ff. corrected by Georg Fischer, Apr 11 2020
STATUS
approved