A248475 -id:A248475 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane

nonn

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

			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

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).

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.

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

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

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

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

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 *)

{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 */

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

def A001475_list(prec):
    P. = 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

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

More terms from Harvey P. Dale, Apr 21 2012

A076276 Number of + signs needed to write the partitions of n (A000041) as sums.

Original entry on oeis.org

0, 0, 1, 3, 7, 13, 24, 39, 64, 98, 150, 219, 322, 455, 645, 892, 1232, 1668, 2259, 3008, 4003, 5260, 6897, 8951, 11599, 14893, 19086, 24284, 30827, 38888, 48959, 61293, 76578, 95223, 118152, 145993, 180037, 221175, 271186, 331402, 404208, 491521

Offset: 0

Floor van Lamoen, Oct 04 2002

nonn

Also, total number of parts in all partitions of n-1 plus the number of emergent parts of n, if n >= 1. Also, sum of largest parts of all partitions of n-1 plus the number of emergent parts of n, if n >= 1. - Omar E. Pol, Oct 30 2011
Also total number of parts that are not the largest part in all partitions of n. - Omar E. Pol, Apr 30 2012
Empirical: For n > 1, a(n) is the sum of the entries in the second column of the lower-triangular matrix of coefficients giving the expansion of degree-n complete homogeneous symmetric functions in the Schur basis of the algebra of symmetric functions. - John M. Campbell, Mar 18 2018

			4=1+3=2+2=1+1+2=1+1+1+1, 7 + signs are needed, so a(4)=7.

Cf. A001475, A248475.

a[0]=0; a[n_] := Sum[DivisorSigma[0, k]PartitionsP[n-k], {k, 1, n}]-PartitionsP[n]

a(n) = (Sum_{k=1..n} tau(k)*numbpart(n-k))-numbpart(n) = A006128(n)-A000041(n), n>0. - Vladeta Jovovic, Oct 06 2002
G.f.: sum(n>=1, (n-1) * x^n / prod(k=1,n, 1-x^k ) ). - Joerg Arndt, Apr 17 2011
a(n) = A006128(n-1) + A182699(n), n >= 1. - Omar E. Pol, Oct 30 2011

More terms from Vladeta Jovovic, Robert G. Wilson v, Dean Hickerson and Don Reble, Oct 06 2002

A248476 Number of pairs (not necessarily successors) of partitions of n that are incomparable in dominance (natural, majorization) ordering.

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 8, 30, 70, 170, 340, 770, 1424, 2810, 5166, 9542, 16614, 29596, 49952, 85610, 141604, 234622, 379218, 616008, 976134, 1549134, 2418768, 3771252, 5795300, 8903306, 13497384, 20438432, 30630108, 45789134, 67857566, 100346480, 147170162, 215341690

Offset: 1

Wouter Meeussen, Oct 07 2014

nonn

a(n) is always even since each incomparable pair (p1,p2) has a distinct companion (p2,p1).

Alois P. Heinz, Table of n, a(n) for n = 1..200 (first 55 terms from Wouter Meeussen)
Wikipedia, Dominance Order

Cf. A000041, A001255, A182988, A248475, A265508.

Table[Count[ Flatten[Outer[dominant , Partitions[n], Partitions[n], 1]], 0], {n, 24}] (* see A248475 for definition of 'dominant' *)

a(n) = p(n)^2 - A182988(n), where p(n) denotes the number of partitions of n, A000041(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A076276 Number of + signs needed to write the partitions of n (A000041) as sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A248476 Number of pairs (not necessarily successors) of partitions of n that are incomparable in dominance (natural, majorization) ordering.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula