login
a(n) = a(n-1) + n * a(n-2), where a(1) = 1, a(2) = 2.
(Formerly M1449 N0573)
7

%I M1449 N0573 #60 Sep 04 2023 06:08:07

%S 1,2,5,13,38,116,382,1310,4748,17848,70076,284252,1195240,5174768,

%T 23103368,105899656,498656912,2404850720,11879332048,59976346448,

%U 309442319456,1628921941312,8746095288800,47840221880288,266492604100288,1510338372987776

%N a(n) = a(n-1) + n * a(n-2), where a(1) = 1, a(2) = 2.

%C a(n) is the number of set partitions of [n] in which the block containing 1 is of length <= 3 and all other blocks are of length <= 2. Example: a(4)=13 counts all 15 partitions of [4] except 1234 and 1/234. - _David Callan_, Jul 22 2008

%C Empirical: a(n) is the sum of the entries in the second-last row of the lower-triangular matrix of coefficients giving the expansion of degree-(n+1) complete homogeneous symmetric functions in the Schur basis of the algebra of symmetric functions. - _John M. Campbell_, Mar 18 2018

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 86 (divided by 2).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H John Cerkan, <a href="/A001475/b001475.txt">Table of n, a(n) for n = 1..795</a>

%H R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]

%F a(n) = (1/2)*A000085(n+1).

%F E.g.f.: (1/2)*( (1+x)*exp(x + x^2/2) - 1). - _Vladeta Jovovic_, Nov 04 2003

%F Given e.g.f. y(x), then 0 = y'(x) * (1+x) - (y(x)+1/2) * (2+2*x+x^2) = 1 - y''(x) + y'(x)*(1 + x) + 2*y(x). - _Michael Somos_, Jan 23 2018

%F 0 = +a(n)*(+a(n+1) +a(n+2) -a(n+3)) +a(n+1)*(-a(n+1) +a(n+2)) for all n>0. - _Michael Somos_, Jan 23 2018

%F a(n) ~ n^((n+1)/2) / (2^(3/2) * exp(n/2 - sqrt(n) + 1/4)) * (1 + 19/(24*sqrt(n))). - _Vaclav Kotesovec_, Apr 01 2018

%e G.f. = x + 2*x + 5*x^2 + 13*x^3 + 38*x^4 + 116*x^5 + 382*x^6 + 1310*x^7 + ... - _Michael Somos_, Jan 23 2018

%p a := proc(n) option remember: if n = 1 then 1 elif n = 2 then 2 elif n >= 3 then procname(n-1) +n*procname(n-2) fi; end:

%p seq(a(n), n = 1..100); # _Muniru A Asiru_, Jan 25 2018

%t RecurrenceTable[{a[1]==1,a[2]==2,a[n]==a[n-1]+n a[n-2]},a,{n,30}] (* _Harvey P. Dale_, Apr 21 2012 *)

%t (* Programs from _Michael Somos_, Jan 23 2018 *)

%t a[n_]:= With[{m=n+1}, If[m<2, 0, Sum[(2 k-1)!! Binomial[m, 2 k], {k, 0, m/2}]/2]];

%t a[n_]:= With[{m=n+1}, If[m<2, 0, HypergeometricU[-m/2, 1/2, -1/2] / (-1/2)^(m/2)/2]];

%t a[n_]:= With[{m=n+1}, If[m<2, 0, HypergeometricPFQ[{-m/2, (1-m)/2}, {}, 2]/2]];

%t a[n_]:= If[ n<1, 0, n! SeriesCoefficient[Exp[x+x^2/2]*(1+x)/2, {x, 0, n}]]; (* End *)

%t Fold[Append[#1, #1[[-1]] + #2 #1[[-2]]] &, {1, 2}, Range[3, 26]] (* _Michael De Vlieger_, Jan 23 2018 *)

%o (PARI) {a(n) = if( n<1, 0, n! * polcoeff( exp( x + x^2/2 + x * O(x^n)) * (1 + x) / 2, n))}; /* _Michael Somos_, Jan 23 2018 */

%o (PARI) my(N=30,x='x+O('x^N)); Vec(serlaplace((1/2)*( (1+x)*exp(x + x^2/2) - 1))) \\ _Joerg Arndt_, Sep 04 2023

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

%o (Magma) I:=[1,2]; [n le 2 select I[n] else Self(n-1)+n*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Mar 31 2018

%o (SageMath)

%o def A001475_list(prec):

%o P.<x> = PowerSeriesRing(QQ, prec)

%o return P( ((1+x)*exp(x+x^2/2) -1)/2 ).egf_to_ogf().list()

%o a=A001475_list(40); a[1:] # _G. C. Greubel_, Sep 03 2023

%Y Cf. A000085, A001189, A013989, A076276, A248475.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Harvey P. Dale_, Apr 21 2012