A225244 Number of partitions of n into squarefree divisors of n.

1, 1, 2, 2, 3, 2, 8, 2, 5, 4, 11, 2, 27, 2, 14, 14, 9, 2, 64, 2, 40, 18, 20, 2, 125, 6, 23, 10, 53, 2, 742, 2, 17, 26, 29, 26, 343, 2, 32, 30, 195, 2, 1654, 2, 79, 136, 38, 2, 729, 8, 341, 38, 92, 2, 1000, 38, 265, 42, 47, 2, 14188, 2, 50, 184, 33, 44, 5257, 2

Offset

0,3

Comments

a(n) <= A018818(n);

a(n) = A018818(n) iff n is squarefree: a(A005117(n)) = A018818(A005117(n));

a(A000040(n)) = 2.

Links

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

Formula

a(n) = [x^n] Product_{d|n, mu(d) != 0} 1/(1 - x^d), where mu() is the Moebius function (A008683). - Ilya Gutkovskiy, Jul 26 2017

Example

a(8) = #{2+2+2+2, 2+2+2+1+1, 2+2+1+1+1+1, 2+6x1, 8x1} = 5;
a(9) = #{3+3+3, 3+3+1+1+1, 3+1+1+1+1+1+1, 9x1} = 4;
a(10) = #{10, 5+5, 5+2+2+1, 5+2+1+1+1, 5+5x1, 2+2+2+2+2, 2+2+2+2+1+1, 2+2+2+1+1+1+1, 2+2+6x1, 2+8x1, 10x1} = 11;
a(11) = #{11, 1+1+1+1+1+1+1+1+1+1+1} = 2;
a(12) = #{6+6, 6+3+3, 6+3+2+1, 6+3+1+1+1, 6+2+2+2, 6+2+2+1+1, 6+2+1+1+1+1, 6+6x1, 3+3+3+3, 3+3+3+2+1, 3+3+3+1+1+1, 3+3+2+2+2, 3+3+2+2+1+1, 3+3+2+4x1, 3+3+6x1, 3+2+2+2+2+1, 3+2+2+2+1+1+1, 3+2+2+5x1, 3+2+7x1, 3+8x1, 2+2+2+2+2+2, 2+2+2+2+2+1+1, 2+2+2+2+1+1+1+1, 2+2+2+6x1, 2+2+8x1, 2+10x1, 12x1} = 27;
a(13) = #{11, 1+1+1+1+1+1+1+1+1+1+1+1+1} = 2;
a(14) = #{14, 7+7, 7+2+2+2+1, 7+2+2+1+1+1, 7+2+5x1, 7+7x1, 7x2, 6x2+1+1, 5x2+1+1+1+1, 4x2+6x1, 2+2+2+8x1, 2+2+10x1, 2+12x1, 14x1} = 14;
a(15) = #{15, 5+5+5, 5+5+3+1+1, 5+5+5x1, 5+3+3+3+1, 5+3+3+1+1+1+1, 5+3+7x1, 5+10x1, 3+3+3+3+3, 3+3+3+3+1+1+1, 3+3+3+6x1, 3+3+9x1, 3+12x1, 15x1} = 14.

Maple

with(numtheory):
a:= proc(n) local b, l; l:= sort([select(issqrfree, divisors(n))[]]):
      b:= proc(m, i) option remember; `if`(m=0 or i=1, 1,
            `if`(i<1, 0, b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
          end; forget(b):
      b(n, nops(l))
    end:
seq(a(n), n=0..100); # Alois P. Heinz, Feb 05 2014

Mathematica

a[0] = 1; a[n_] := Module[{b, l}, l = Select[Divisors[n], SquareFreeQ]; b[m_, i_] := b[m, i] = If[m == 0 || i == 1, 1, If[i < 1, 0, b[m, i - 1] + If[l[[i]] > m, 0, b[m - l[[i]], i]]]]; b[n, Length[l]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 27 2015, after Alois P. Heinz *)

Prog

(Haskell)
a225244 n = p (a206778_row n) n where
   p _          0 = 1
   p []         _ = 0
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

Crossrefs

Cf. A206778, A005117, A008966, A225245, A073576.

Sequence in context: A117754 A248577 A015999 * A345281 A338319 A369748

Adjacent sequences: A225241 A225242 A225243 * A225245 A225246 A225247

Keyword

nonn

Author

Reinhard Zumkeller, May 05 2013

Status

approved