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
John Cerkan, Table of n, a(n) for n = 1..795
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
Reinis Cirpons, James East, and James D. Mitchell, Transformation representations of diagram monoids, arXiv:2411.14693 [math.RA], 2024. See pp. 3, 33.
FORMULA
a(n) = (1/2)*A000085(n+1).
E.g.f.: (1/2)*( (1+x)*exp(x + x^2/2) - 1). - Vladeta Jovovic, Nov 04 2003
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:
seq(a(n), n = 1..100); # Muniru A Asiru, Jan 25 2018
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 *)
(* Programs from Michael Somos, Jan 23 2018 *)
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)
def A001475_list(prec):
P.<x> = PowerSeriesRing(QQ, prec)
return P( ((1+x)*exp(x+x^2/2) -1)/2 ).egf_to_ogf().list()
a=A001475_list(40); a[1:] # G. C. Greubel, Sep 03 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Harvey P. Dale, Apr 21 2012
STATUS
approved