A052335 - OEIS

A052335

Number of partitions of n into at most 1 copy of 1, 2 copies of 2, 3 copies of 3, ... .

1, 1, 1, 2, 3, 4, 5, 7, 10, 13, 17, 22, 28, 36, 46, 58, 73, 91, 114, 141, 173, 213, 261, 318, 387, 469, 567, 683, 821, 984, 1176, 1403, 1671, 1984, 2351, 2781, 3284, 3869, 4550, 5343, 6264, 7330, 8565, 9993, 11642, 13543, 15733, 18252, 21148, 24471, 28282, 32646, 37640, 43348, 49867, 57302, 65776, 75426, 86405, 98882

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Also number of partitions into non-pronic numbers (cannot be written as i*(i+1)).

Convolution of A024940 and A225044. - Vaclav Kotesovec, Jan 02 2017

Also the number of integer partitions of n with no part less than its own multiplicity. - Gus Wiseman, Sep 30 2025

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 129 terms from Reinhard Zumkeller)

Mircea Merca and Emil Simion, n-Color Partitions into Distinct Parts as Sums over Partitions, Symmetry (2023) Vol. 15, Iss. 11.

FORMULA

G.f.: Product_{i>=1} (1-x^(i*(i+1)))/(1-x^i).

G.f.: (1+x) * (1+x^2+x^4) * (1+x^3+x^6+x^9) * (1+x^4+x^8+x^12+x^16) * ... (g.f. above, expanded). - Joerg Arndt, Apr 01 2014

G.f.: Product_{n>=1} (1 - q^(n*(n+1))) / Product_{n>=1} (1 - q^n). - Joerg Arndt, Apr 01 2014

a(n) = p(n,1,1) with p(n,t,k) = if t<0 then 0 else if k<=n then p(n-k,t-1,k)+p(n,k+1,k+1) else 0^n. - Reinhard Zumkeller, Jan 20 2010

a(n) ~ exp(Pi*sqrt(2*n/3) - 3^(1/4) * Zeta(3/2) * n^(1/4) / 2^(3/4) - 3*Zeta(3/2)^2/(32*Pi)) / sqrt(2*n). - Vaclav Kotesovec, Jan 01 2017

EXAMPLE

a(5)=4 because we have [5], [4,1], [3,2] and [2,2,1] ([3,1,1], [2,1,1,1] and [1,1,1,1,1] do not qualify).

MAPLE

g:=product((1-x^(j*(j+1)))/(1-x^j), j=1..53): gser:=series(g, x=0, 55): seq(coeff(gser, x, n), n=0..49); # Emeric Deutsch, Mar 04 2006

# Alternative:

with(numtheory):

a:= proc(n) option remember; `if`(n=0, 1, add(add(

`if`(issqr(4*d+1), 0, d), d=divisors(j))*a(n-j), j=1..n)/n)

end:

seq(a(n), n=0..80); # Alois P. Heinz, Apr 01 2014

MATHEMATICA

CoefficientList[Series[Product[Sum[x^(i j ), {i, 0, j}], {j, 1, 49}], {x, 0, 49}], x]

(* Alternative: *)

a[n_] := a[n] = If[n == 0, 1, Sum[Sum[If[IntegerQ @ Sqrt[4*d+1], 0, d], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jan 30 2017, after Alois P. Heinz *)

Table[Length[Select[IntegerPartitions[n], And@@Table[Count[#, k]<=k, {k, Union[#]}]&]], {n, 0, 10}] (* Gus Wiseman, Sep 30 2025 *)

PROG

(PARI) N=66; q='q+O('q^N); Vec( prod(n=1, N, sum(k=0, n, q^(k*n)) ) ) \\ Joerg Arndt, Apr 01 2014

CROSSREFS

Cf. A002378.

For "=" instead of ">=" we have A033461, ranks A324587, see also A109298.

For constant partitions we have A038548.

For ">" instead of ">=" we have A087153, ranks A325128.

For parts instead of multiplicities we have A238873, complement A387118.

These partitions are ranked by A276078.

The complement is counted by A387578, ranks A276079.

A000041 counts integer partitions, strict A000009.