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,4

Links

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

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

Example

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.

Maple

with(numtheory):
b:= proc(n, i) option remember;
      `if`(i*(i+1)/2<n, 0, `if`(n=0, 1, b(n, i-1)+
      `if`(i<=n and issqrfree(i), b(n-i, i-1), 0)))
    end:
a:= n-> 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 *)

Prog

(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
(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

Crossrefs

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

Sequence in context: A361165 A358024 A358025 * A102885 A323089 A239511

Adjacent sequences: A087185 A087186 A087187 * A087189 A087190 A087191

Keyword

nonn

Author

Reinhard Zumkeller, Aug 24 2003

Extensions

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

Status

approved