login
a(n) = n(a(n-1) + 1), a(0) = 0.
(Formerly M3505)
53

%I M3505 #165 Jan 07 2020 10:45:49

%S 0,1,4,15,64,325,1956,13699,109600,986409,9864100,108505111,

%T 1302061344,16926797485,236975164804,3554627472075,56874039553216,

%U 966858672404689,17403456103284420,330665665962403999,6613313319248080000,138879579704209680021,3055350753492612960484

%N a(n) = n(a(n-1) + 1), a(0) = 0.

%C Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}. Some early references to this sequence are Izquierdo (1659), Caramuel de Lobkowitz (1670), Prestet (1675) and Bernoulli (1713). - _Don Knuth_, Oct 16 2001, Aug 16 2004

%C Stirling transform of A006252(n-1) = [0,1,1,2,4,14,38,...] is a(n-1) = [0,1,4,15,64,...]. - _Michael Somos_, Mar 04 2004

%C In particular, for n >= 1 a(n) is the number of nonempty sequences with n or fewer terms, each a distinct element of {1,...,n}. - _Rick L. Shepherd_, Jun 08 2005

%C a(n) = VarScheme(1,n). See A128195 for the definition of VarScheme(k,n). - _Peter Luschny_, Feb 26 2007

%C if s(n) is a sequence of the form s(0)=x, s(n)= n(s(n-1)+k), then s(n)= n!*x + a(n)*k. - _Gary Detlefs_, Jun 06 2010

%C Exponential convolution of factorials (A000142) and nonnegative integers (A001477). - _Vladimir Reshetnikov_, Oct 07 2016

%D Jacob Bernoulli, Ars Conjectandi (1713), page 127.

%D Johannes Caramuel de Lobkowitz, Mathesis Biceps Vetus et Nova (Campania: 1670), volume 2, 942-943.

%D J. K. Horn, personal communication to _Robert G. Wilson v_.

%D Sebastian Izquierdo, Pharus Scientiarum (Lyon: 1659), 327-328.

%D Jean Prestet, Elemens des Mathematiques (1675), page 341.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A007526/b007526.txt">Table of n, a(n) for n = 0..450</a> (first 101 terms from T. D. Noe)

%H J. L. Adams, <a href="/A000522/a000522_1.pdf">Conceptual Blockbusting: A Guide to Better Ideas</a>, Freeman, San Francisco, 1974. [Annotated scans of pages 69 and 70 only]

%H J. Bernoulli, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=ABZ9501.0001.001">Wahrscheinlichkeitsrechnung (Ars conjectandi) von Jakob Bernoulli (1713) Uebers. und hrsg. von R. Haussner</a>, Leipzig, W. Engelmann, (1899), <a href="http://www.hti.umich.edu/t/text/gifcvtdir/abz9501.0001.001/00000307.tifs.gif">[124] Kapitel VII. Variationen ohne Wiederholung. (Page 121)</a>.

%H Peter J. Freyd, <a href="http://dx.doi.org/10.1016/j.tcs.2006.12.033">Core algebra revisited</a>, Theoretical Computer Science, 375 (2007), Issues 1-3, 193-200.

%H Z. Kasa and Z. Katai, <a href="http://www.acta.sapientia.ro/acta-info/C4-2/info42-4.pdf">Scattered subwords and composition of natural numbers</a>, Acta Univ. Sapientiae, Informatica, 4, 2 (2012) 225-236. - From _N. J. A. Sloane_, Feb 21 2013

%H J. Sawada, A. Williams, <a href="http://www.cis.uoguelph.ca/~sawada/papers/pancake_successor.pdf">Successor rules for flipping pancakes and burnt pancakes</a>, Preprint 2015.

%H Elmar Teufl and Stephan Wagner, <a href="http://dx.doi.org/10.1016/j.jcta.2007.01.007">Enumeration problems for classes of self-similar graphs</a>, Journal of Combinatorial Theory, Series A, Volume 114, Issue 7, October 2007, Pages 1254-1277.

%F a(n) = A000522(n) - 1.

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

%F a(n) = Sum_{r=1..n} A008279(n, r)= n!*(Sum_{k=0..n-1} 1/k!).

%F a(n) = n(a(n-1) + 1).

%F E.g.f.: x*exp(x)/(1-x). - _Vladeta Jovovic_, Aug 25 2002

%F a(n) = Sum_{k=1..n} k!*C(n, k). - _Benoit Cloitre_, Dec 06 2002

%F a(n) = Sum_{k=0..n-1} (n! / k!). - _Ross La Haye_, Sep 22 2004

%F a(n) = Sum_{k=1..n} (Product_{j=0..k-1} (n-j)). - _Joerg Arndt_, Apr 24 2011

%F Binomial transform of n! - !n. - _Paul Barry_, May 12 2004

%F Inverse binomial transform of A066534. - _Ross La Haye_, Sep 16 2004

%F For n > 0, a(n) = exp(1) * Integral_{x>=0} exp(-exp(x/n)+x) dx. - _Gerald McGarvey_, Oct 19 2006

%F a(n) = Integral_{x>=0} (((1+x)^n-1)*exp(-x)). - _Paul Barry_, Feb 06 2008

%F a(n) = GAMMA(n+2)*(1+(-GAMMA(n+1)+exp(1)*GAMMA(n+1, 1))/GAMMA(n+1)). - _Thomas Wieder_, May 02 2009

%F E.g.f.: -1/G(0) where G(k) = 1 - 1/(x - x^3/(x^2+(k+1)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 10 2012

%F Conjecture : a(n) = (n+2)*a(n-1) - (2*n-1)*a(n-2) + (n-2)*a(n-3). - _R. J. Mathar_, Dec 04 2012 [Conjecture verified by _Robert FERREOL_, Aug 04 2018]

%F G.f.: (Q(0) - 1)/(1-x), where Q(k)= 1 + (2*k + 1)*x/( 1 - x - 2*x*(1-x)*(k+1)/(2*x*(k+1) + (1-x)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 09 2013

%F G.f.: 2/((1-x)*G(0)) - 1/(1-x), where G(k)= 1 + 1/(1 - x*(2*k+2)/(x*(2*k+3) - 1 + x*(2*k+2)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 31 2013

%F a(n) = (...((((((0)+1)*1+1)*2+1)*3+1)*4+1)...*n). - _Bob Selcoe_, Jul 04 2013

%F G.f.: Q(0)/(2-2*x) - 1/(1-x), where Q(k)= 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1-x)/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Aug 09 2013

%F G.f.: (W(0) - 1)/(1-x), where W(k) = 1 - x*(k+1)/( x*(k+2) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - _Sergei N. Gladkovskii_, Aug 25 2013

%F For n > 0: a(n) = n*A000522(n-1). - _Reinhard Zumkeller_, Aug 27 2013

%F a(n) = (...(((((0)*1+1)*2+2)*3+3)*4+4)...*n+n). - _Bob Selcoe_, Apr 30 2014

%F 0 = 1 + a(n)*(+1 + a(n+1) - a(n+2)) + a(n+1)*(+2 +a(n+1)) - a(n+2) for all n >= 0. - _Michael Somos_, Aug 30 2016

%F a(n) = n*hypergeom([1, 1-n], [], -1). - _Peter Luschny_, May 09 2017

%F Product_{n>=1} (a(n)+1)/a(n) = e, coming from Product_{n=1..N}(a(n)+1)/a(n) = Sum_{n=0..N} 1/n!. - _Robert FERREOL_, Jul 12 2018

%F O.g.f.: Sum_{k>=1} k^k*x^k/(1 + (k - 1)*x)^(k+1). - _Ilya Gutkovskiy_, Oct 09 2018

%e G.f. = x + 4*x^2 + 15*x^3 + 64*x^4 + 325*x^5 + 1956*x^6 + 13699*x^7 + ...

%e Consider the nonempty subsets of the set {1,2,3,...,n} formed by the first n integers. E.g., for n = 3 we have {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. For each subset S we determine its number of parts, that is nprts(S). The sum over all subsets is written as sum_{S=subsets}. Then we have A007526 = Sum_{S=subsets} nprts(S)!. E.g., for n = 3 we have 1!+1!+1!+2!+2!+2!+3! = 15. - _Thomas Wieder_, Jun 17 2006

%e a(3)=15: Let the objects be a, b, and c. The fifteen nonempty ordered subsets are {a}, {b}, {c}, {ab}, {ba}, {ac}, {ca}, {bc}, {cb}, {abc}, {acb}, {bac}, {bca}, {cab} and {cba}.

%p A007526 := n -> add(n!/k!,k=0..n) - 1;

%p a := n -> n*hypergeom([1,1-n],[],-1):

%p seq(simplify(a(n)), n=0..22); # _Peter Luschny_, May 09 2017

%p # third Maple program:

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

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

%p end:

%p seq(a(n), n=0..23); # _Alois P. Heinz_, Jan 06 2020

%t Table[ Sum[n!/(n - r)!, {r, 1, n}], {n, 0, 20}] (* or *) Table[n!*Sum[1/k!, {k, 0, n - 1}], {n, 0, 20}]

%t a=1;Table[a=(a-1)*(n-1);Abs[a],{n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Nov 20 2009 *)

%t FoldList[#1*#2 + #2 &, 0, Range[19]] (* _Robert G. Wilson v_, Jul 07 2012 *)

%t f[n_] := Floor[E*n! - 1]; f[0] = 0; Array[f, 20, 0] (* _Robert G. Wilson v_, Feb 06 2015 *)

%t a[n_] := n (a[n - 1] +1); a[0] = 0; Array[a, 20, 0] (* _Robert G. Wilson v_, Feb 06 2015 *)

%t Round@Table[E n Gamma[n, 1], {n, 0, 20}] (* Round is equivalent to FullSimplify here, but is much faster - _Vladimir Reshetnikov_, Oct 07 2016 *)

%o (PARI) {a(n) = if( n<1, 0, n * (a(n-1) + 1))}; /* _Michael Somos_, Apr 06 2003 */

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff(x * exp(x + x * O(x^n)) / (1 - x), n))}; /* _Michael Somos_, Mar 04 2004 */

%o (PARI) a(n)= sum(k=1,n, prod(j=0,k-1,n-j))

%o (Haskell)

%o a007526 n = a007526_list !! n

%o a007526_list = 0 : zipWith (*) [1..] (map (+ 1) a007526_list)

%o -- _Reinhard Zumkeller_, Aug 27 2013

%o (GAP) a:=[0];; for n in [2..25] do a[n]:=(n-1)*(a[n-1]+1); od; a; # _Muniru A Asiru_, Aug 07 2018

%Y Row sums of A068424.

%Y Partial sums of A001339.

%Y Column k=1 of A326659.

%Y Cf. A000522, A007526, A001339, A128195.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, _Robert G. Wilson v_