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

Author

Reinhard Zumkeller, May 05 2013

Keywords

• nonn

Comments

a(n) <= A018818(n);

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

a(A000040(n)) = 2.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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

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 *)

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