A073576 Number of partitions of n into squarefree parts.

1, 1, 2, 3, 4, 6, 9, 12, 16, 21, 28, 36, 47, 60, 76, 96, 120, 150, 185, 228, 280, 342, 416, 504, 608, 731, 877, 1048, 1249, 1484, 1759, 2079, 2452, 2885, 3387, 3968, 4640, 5413, 6304, 7328, 8504, 9852, 11395, 13159, 15172, 17468, 20082, 23056, 26434, 30267

Offset: 0

Author

Vladeta Jovovic, Aug 27 2002

Keywords

• nonn

Comments

Euler transform of the absolute values of A008683. - Tilman Neumann, Dec 13 2008

Euler transform of A008966. - Vaclav Kotesovec, Mar 31 2018

Links

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

Crossrefs

Cf. A058647.

Cf. A087188.

Cf. A225244.

Cf. A114374.

Programs

Haskell

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

Maple

with(numtheory):
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      abs(mobius(d)), d=divisors(j)) *a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Mar 05 2015

Mathematica

Table[Length[Select[Boole /@ Thread /@ SquareFreeQ /@ IntegerPartitions[n], FreeQ[#, 0] &]], {n, 48}] (* Jayanta Basu, Jul 02 2013 *)
a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*Abs[MoebiusMu[d]], {d, Divisors[j]}] * a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Oct 10 2015, after Alois P. Heinz *)
nmax = 60; CoefficientList[Series[Exp[Sum[Sum[Abs[MoebiusMu[k]] * x^(j*k) / j, {k, 1, Floor[nmax/j] + 1}], {j, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Mar 31 2018 *)

Python

from functools import lru_cache
from sympy import mobius, divisors
@lru_cache(maxsize=None)
def A073576(n): return sum(sum(d*abs(mobius(d)) for d in divisors(i, generator=True))*A073576(n-i) for i in range(1,n+1))//n if n else 1 # Chai Wah Wu, Aug 23 2024

Formula

G.f.: 1/Product_{k>0} (1-x^A005117(k)).

a(n) = 1/n*Sum_{k=1..n} A048250(k)*a(n-k).

a(n) = A000041(n) - A114374(n) - A117395(n), n>0. - Reinhard Zumkeller, Mar 11 2006

G.f.: 1 + Sum_{i>=1} mu(i)^2*x^i / Product_{j=1..i} (1 - mu(j)^2*x^j). - Ilya Gutkovskiy, Jun 05 2017

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