BBC Russian

A003422

Left factorials: !n = Sum_{k=0..n-1} k!.
(Formerly M1237)

120

0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114, 4037914, 43954714, 522956314, 6749977114, 93928268314, 1401602636314, 22324392524314, 378011820620314, 6780385526348314, 128425485935180314, 2561327494111820314, 53652269665821260314, 1177652997443428940314 (list; graph; refs; listen; history; text; internal format)

	OFFSET	`0,3`
	COMMENTS	`Number of {12, 12, 12, 21}- and {12, 12, 21, 21}-avoiding signed permutations in the hyperoctahedral group.` `a(n) is the number of permutations on [n] that avoid the patterns 2n1 and n12. An occurrence of a 2n1 pattern is a (scattered) subsequence a-n-b with a > b. - David Callan, Nov 29 2007` `Also, numbers left over after the following sieving process: At step 1, keep all numbers of the set N = {0, 1, 2, ...}. In step 2, keep only every second number after a(2) = 2: N' = {0, 1, 2, 4, 6, 8, 10, ...}. In step 3, keep every third of the numbers following a(3) = 4, N" = {0, 1, 2, 4, 10, 16, 22, ...}. In step 4, keep every fourth of the numbers beyond a(4) = 10: {0, 1, 2, 4, 10, 34, 58, ...}, and so on. - M. F. Hasler, Oct 28 2010` `If s(n) is a second-order recurrence defined as s(0) = x, s(1) = y, s(n) = n(s(n - 1) - s(n - 2)), n > 1, then s(n) = ny - na(n - 1)*x. - Gary Detlefs, May 27 2012` `a(n) is the number of lists of {1, ..., n} with (1st element) = (smallest element) and (k-th element) <> (k-th smallest element) for k > 1, where a list means an ordered subset. a(4) = 10 because we have the lists: [1], [2], [3], [4], [1, 3, 2], [1, 4, 2], [1, 4, 3], [2, 4, 3], [1, 3, 4, 2], [1, 4, 2, 3]. Cf. A000262. - Geoffrey Critzer, Oct 04 2012` `Consider a tree graph with 1 vertex. Add an edge to it with another vertex. Now add 2 edges with vertices to this vertex, and then 3 edges to each open vertex of the tree (not the first one!), and the next stage is to add 4 edges, and so on. The total number of vertices at each stage give this sequence (see example). - Jon Perry, Jan 27 2013` `Additive version of the superfactorials A000178. - Jon Perry, Feb 09 2013` `Repunits in the factorial number system (see links). - Jon Perry, Feb 17 2013` `Whether n\|a(n) only for 1 and 2 remains an open problem. A published 2004 proof was retracted in 2011. This is sometimes known as Kurepa's conjecture. - Robert G. Wilson v, Jun 15 2013, corrected by Jeppe Stig Nielsen, Nov 07 2015.` `!n is not always squarefree for n > 3. Miodrag Zivkovic found that 54503^2 divides !26541. - Arkadiusz Wesolowski, Nov 20 2013` `a(n) gives the position of A007489(n) in A227157. - Antti Karttunen, Nov 29 2013` `Matches the total domination number of the Bruhat graph from n = 2 to at least n = 5. - Eric W. Weisstein, Jan 11 2019` `For the connection with Kurepa trees, see A. Petojevic, The {K_i(z)}_{i=1..oo} functions, Rocky Mtn. J. Math., 36 (2006), 1637-1650. - Aleksandar Petojevic, Jun 29 2018`
	REFERENCES	`Richard K. Guy, Unsolved Problems Number Theory, Section B44.` `D. Kurepa, On the left factorial function !n. Math. Balkanica 1 1971 147-153.` `N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).`
	LINKS	`T. D. Noe, Table of n, a(n) for n = 0..100` `P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), Article 00.1.5.` `Bernd C. Kellner, Some remarks on Kurepa's left factorial, arXiv:math/0410477 [math.NT], 2004.` `D. Kurepa, On the left factorial function !N, Math. Balkanica 1 (1971), 147-153. (Annotated scanned copy).` `T. Mansour and J. West, Avoiding 2-letter signed patterns, arXiv:math/0207204 [math.CO], 2002.` `Romeo Meštrović, Variations of Kurepa's left factorial hypothesis, arXiv preprint arXiv:1312.7037 [math.NT], 2013.` `Romeo Meštrović, The Kurepa-Vandermonde matrices arising from Kurepa's left factorial hypothesis, Filomat 29:10 (2015), 2207-2215; DOI 10.2298/FIL1510207M.` `Hisanori Mishima, Factorizations of many number sequences.` `Hisanori Mishima, Factorizations of many number sequences` `F. J. Papp, Letter to N. J. A. Sloane, Nov 1974.` `Jon Perry, Sum of Factorials. [Broken link?]` `Aleksandar Petojevic, On Kurepa's hypothesis for the left factorial, Filomat, Vol. 12, No. 1, 1998.` `Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.` `Aleksandar Petojevic, The {K_i(z)}_{i=1..oo} functions, Rocky Mtn. J. Math., 36 (2006), 1637-1650.` `Aleksandar Petojević, Marjana Gorjanac Ranitović, Dragan Rastovac, and Milinko Mandić, The Golden Ratio, Factorials, and the Lambert W Function, Journal of Integer Sequences, Vol. 27 (2024), Article 24.5.7.` `Eric Weisstein's World of Mathematics, Factorial Sums.` `Eric Weisstein's World of Mathematics, Left Factorial.` `Eric Weisstein's World of Mathematics, Repunit.` `Wikipedia, Factorial number system.` `Miodrag Zivkovic, The number of primes sum_{i=1..n} (-1)^(n-i)*i! is finite, Math. Comp. 68 (1999), pp. 403-409.` `Index entries for sequences related to factorial numbers.`
	FORMULA	`D-finite with recurrence: a(n) = na(n - 1) - (n - 1)a(n - 2). - Henry Bottomley, Feb 28 2001` `Sequence is given by 1 + 1(1 + 2(1 + 3(1 + 4(1 + ..., terminating in n(1)...). - Jon Perry, Jun 01 2004` `a(n) = Sum_{k=0..n-1} P(n, k) / C(n, k). - Ross La Haye, Sep 20 2004` `E.g.f.: (Ei(1) - Ei(1 - x))exp(-1 + x) where Ei(x) is the exponential integral. - Djurdje Cvijovic and Aleksandar Petojevic, Apr 11 2000` `a(n) = Integral_{x = 0..oo} [(x^n - 1)/(x - 1)]exp(-x) dx. - Gerald McGarvey, Oct 12 2007` `A007489(n) = !(n + 1) - 1 = a(n + 1) - 1. - Artur Jasinski, Nov 08 2007. Typos corrected by Antti Karttunen, Nov 29 2013` `Starting (1, 2, 4, 10, 34, 154, ...), = row sums of triangle A135722. - Gary W. Adamson, Nov 25 2007` `a(n) = a(n - 1) + (n - 1)! for n >= 2. - Jaroslav Krizek, Jun 16 2009` `E.g.f. A(x) satisfies the differential equation A'(x) = A(x) + 1/(1 - x). - Vladimir Kruchinin, Jan 19 2011` `a(n + 1) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = A182386(k) for k = 0, 1, ..., n. - Michael Somos, Apr 27 2012` `From Sergei N. Gladkovskii, May 09 2013 to Oct 22 2013: (Start)` `Continued fractions:` `G.f.: x/(1-x)Q(0) where Q(k) = 1 + (2k + 1)x/( 1 - 2x(k+1)/(2x(k+1) + 1/Q(k+1))).` `G.f.: G(0)x/(1-x)/2 where G(k) = 1 + 1/(1 - x(k+1)/(x(k+1) + 1/G(k+1))).` `G.f.: 2x/(1-x)/G(0) where G(k) = 1 + 1/(1 - 1/(1 - 1/(2x(k+1)) + 1/G(k+1))).` `G.f.: W(0)x/(1+sqrt(x))/(1-x) where W(k) = 1 + sqrt(x)/(1 - sqrt(x)(k+1)/(sqrt(x)(k+1) + 1/W(k+1))).` `G.f.: B(x)(1+x)/(1-x) where B(x) is the g.f. of A153229.` `G.f.: x/(1-x) + x^2/(1-x)/Q(0) where Q(k) = 1 - 2x(2k+1) - x^2(2k+1)(2k+2)/(1 - 2x(2k+2) - x^2(2k+2)(2k+3)/Q(k+1)).` `G.f.: x(1+x)B(x) where B(x) is the g.f. of A136580. (End)` `a(n) = (-1)^(n+1)C(n-1, -1) where C(n, x) are the Charlier polynomials (with parameter a=1) as given in A137338. (Evaluation at x = 1 gives A232845.) - Peter Luschny, Nov 28 2018` `a(n) = (a(n-3)(n-2)^2(n-3)! + a(n-1)^2)/a(n-2) (empirical). - Gary Detlefs, Feb 25 2022` `a(n) = signum(n)/b(1,n) with b(i,n) = i - [i<n] i/b(i+1,n). - Mohammed Bouras, Sep 07 2022` `Sum_{n>=1} 1/a(n) = A357145. - Amiram Eldar, Oct 01 2022`
	EXAMPLE	`!5 = 0! + 1! + 2! + 3! + 4! = 1 + 1 + 2 + 6 + 24 = 34.` `x + 2x^2 + 4x^3 + 10x^4 + 34x^5 + 154x^6 + 874x^7 + 5914x^8 + 46234x^9 + ...` `From Arkadiusz Wesolowski, Aug 06 2012: (Start)` `Illustration of initial terms:` `.` `. o o o o o` `. o o o o` `. o o o o o o` `. ooo ooo ooo ooo` `. oooo oooo oooo oooo oooo oooo` `.` `. 1 2 4 10 34` `.` `(End)` `The tree graph. The total number of vertices at each stage is 1, 2, 4, 10, ...` `0 0` `\|/` `0-0` `/` `0-0` `\` `0-0` `\|\` `0 0` `- Jon Perry, Jan 27 2013`
	MAPLE	`A003422 := proc(n) local k; add(k!, k=0..n-1); end proc:` `# Alternative, using the Charlier polynomials A137338:` `C := proc(n, x) option remember; if n > 0 then (x-n)C(n-1, x) - nC(n-2, x)` `elif n = 0 then 1 else 0 fi end: A003422 := n -> (-1)^(n+1)*C(n-1, -1):` `seq(A003422(n), n=0..22); # Peter Luschny, Nov 28 2018` `# third Maple program:` a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+(n-1)!) end: `seq(a(n), n=0..23); # Alois P. Heinz, Feb 24 2022`
	MATHEMATICA	`Table[Sum[i!, {i, 0, n - 1}], {n, 0, 20}] (* Stefan Steinerberger, Mar 31 2006 )` `Join[{0}, Accumulate[Range[0, 25]!]] ( Harvey P. Dale, Nov 19 2011 )` `a[0] = 0; a[1] = 1; a[n_] := a[n] = na[n - 1] - (n - 1)a[n - 2]; Array[a, 23, 0] ( Robert G. Wilson v, Jun 15 2013 )` `a[n_] := (-1)^nn!Subfactorial[-n-1]-Subfactorial[-1]; Table[a[n] // FullSimplify, {n, 0, 22}] ( Jean-François Alcover, Jan 09 2014 )` `RecurrenceTable[{a[n] == n a[n - 1] - (n - 1) a[n - 2], a[0] == 0, a[1] == 1}, a, {n, 0, 10}] ( Eric W. Weisstein, Jan 11 2019 )` `Range[0, 20]! CoefficientList[Series[(ExpIntegralEi[1] - ExpIntegralEi[1 - x]) Exp[x - 1], {x, 0, 20}], x] ( Eric W. Weisstein, Jan 11 2019 )` `Table[(-1)^n n! Subfactorial[-n - 1] - Subfactorial[-1], {n, 0, 20}] // FullSimplify ( Eric W. Weisstein, Jan 11 2019 )` `Table[(I Pi + ExpIntegralEi[1] + (-1)^n n! Gamma[-n, -1])/E, {n, 0, 20}] // FullSimplify ( Eric W. Weisstein, Jan 11 2019 *)`
	PROG	`(PARI) a003422(n)=sum(k=0, n-1, k!) \\ Charles R Greathouse IV, Jun 15 2011` `(Haskell)` `a003422 n = a003422_list !! n` `a003422_list = scanl (+) 0 a000142_list` `-- Reinhard Zumkeller, Dec 27 2011` `(Maxima) makelist(sum(k!, k, 0, n-1), n, 0, 20); /* Stefano Spezia, Jan 11 2019 /` `(Python)` `from itertools import count, islice` `def A003422_gen(): # generator of terms` `yield from (0, 1)` `c, f = 1, 1` `for n in count(1):` `yield (c:= c + (f:= fn))` `A003422_list = list(islice(A003422_gen(), 20)) # Chai Wah Wu, Jun 22 2022` `(Python)` `def a(n):` `if n == 0: return 0` `s = f = 1` `for k in range(1, n):` `f *= k` `s += f` `return round(s)` `print([a(n) for n in range(24)]) # Peter Luschny, Mar 05 2024`
	CROSSREFS	`Equals A007489(n-1)+1 for n>=1. Cf. A000142, A014144, A005165.` `Twice A014288. See also A049782, A100612.` `Cf. A102639, A102411, A102412, A101752, A094216, A094638, A008276, A000166, A000110, A000204, A000045, A000108, A135722, A227157, A000178, A137338, A232845, A357145.` `Sequence in context: A006397 A297197 A297201 * A117402 A109455 A372495` `Adjacent sequences: A003419 A003420 A003421 * A003423 A003424 A003425`
	KEYWORD	`nonn,easy,nice`
	AUTHOR	`N. J. A. Sloane, R. K. Guy`
	STATUS	`approved`