|
|
A001475
|
|
a(n) = a(n-1) + n * a(n-2), where a(1) = 1, a(2) = 2.
(Formerly M1449 N0573)
|
|
7
|
|
|
1, 2, 5, 13, 38, 116, 382, 1310, 4748, 17848, 70076, 284252, 1195240, 5174768, 23103368, 105899656, 498656912, 2404850720, 11879332048, 59976346448, 309442319456, 1628921941312, 8746095288800, 47840221880288, 266492604100288, 1510338372987776
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
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
|
|
REFERENCES
|
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 86 (divided by 2).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
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
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
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
|
|
EXAMPLE
|
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
|
|
MAPLE
|
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:
|
|
MATHEMATICA
|
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 *)
a[n_]:= With[{m=n+1}, If[m<2, 0, Sum[(2 k-1)!! Binomial[m, 2 k], {k, 0, m/2}]/2]];
a[n_]:= With[{m=n+1}, If[m<2, 0, HypergeometricU[-m/2, 1/2, -1/2] / (-1/2)^(m/2)/2]];
a[n_]:= With[{m=n+1}, If[m<2, 0, HypergeometricPFQ[{-m/2, (1-m)/2}, {}, 2]/2]];
a[n_]:= If[ n<1, 0, n! SeriesCoefficient[Exp[x+x^2/2]*(1+x)/2, {x, 0, n}]]; (* End *)
Fold[Append[#1, #1[[-1]] + #2 #1[[-2]]] &, {1, 2}, Range[3, 26]] (* Michael De Vlieger, Jan 23 2018 *)
|
|
PROG
|
(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 */
(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
(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
(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
(SageMath)
P.<x> = PowerSeriesRing(QQ, prec)
return P( ((1+x)*exp(x+x^2/2) -1)/2 ).egf_to_ogf().list()
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|