A087188 Number of partitions of n into distinct squarefree parts.

1, 1, 1, 2, 1, 2, 3, 3, 4, 4, 5, 6, 6, 8, 9, 10, 13, 14, 16, 18, 20, 24, 27, 30, 35, 37, 42, 47, 51, 59, 64, 72, 81, 88, 98, 109, 120, 134, 147, 163, 179, 195, 216, 236, 258, 284, 310, 339, 371, 403, 441, 480, 523, 572, 621, 675, 734, 796, 865, 937, 1014, 1100, 1189

Offset: 0

Author

Reinhard Zumkeller, Aug 24 2003

Keywords

• nonn

Examples

			n=9: 5+3+1 = 6+2+1 = 6+3 = 7+2: a(9)=4;
n=10: 5+3+2 = 6+3+1 = 7+2+1 = 7+3 = 10: a(10)=5.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A073576, A000009, A005117, A008966, A225245, A256012.

Programs

Haskell

a087188 = p a005117_list where
   p _      0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jun 01 2015

Maple

with(numtheory):
b:= proc(n, i) option remember;
      `if`(i*(i+1)/2 b(n$2):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 02 2015

Mathematica

b[n_, i_] := b[n, i] = If[i*(i+1)/2 < n, 0, If[n == 0, 1, b[n, i-1] + If[i <= n && SquareFreeQ[i], b[n-i, i-1], 0]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 24 2015, after Alois P. Heinz *)
nmax = 100; CoefficientList[Series[Exp[Sum[(-1)^(j + 1)/j * Sum[Abs[MoebiusMu[k]] * x^(j*k), {k, 1, Floor[nmax/j] + 1}], {j, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Mar 31 2018 *)

PARI

ok(v)=for(i=2,#v, if(v[i]==v[i-1] || !issquarefree(v[i]), return(0))); #v==0 || issquarefree(v[1])
a(n)=my(s,u); forpart(v=n, if(ok(v), s++)); s \\ Charles R Greathouse IV, Nov 05 2017

Formula

O.g.f.: product_{i=1,2,...infinity} [1+x^A005117(i)]. - R. J. Mathar, May 16 2008

a(n) ~ exp(sqrt(2*n)) / (2^(1/4) * sqrt(Pi) * n^(3/4)). - Vaclav Kotesovec, Mar 24 2018

Extensions

Offset changed and a(0)=1 prepended by Reinhard Zumkeller, Jun 01 2015