A225245 Number of partitions of n into distinct squarefree divisors of n.

1, 1, 1, 1, 0, 1, 2, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 4, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 3, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 3, 1, 1, 0, 0, 1, 3, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 1, 2, 1, 1

Offset: 0

Author

Reinhard Zumkeller, May 05 2013

Keywords

• nonn

Comments

a(n) <= A033630(n);

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

a(A225353(n)) = 0; a(A225354(n)) > 0.

Examples

			a(2*3)     = a(6)  = #{6, 3+2+1} = 2;
a(2*2*3)   = a(12) = #{6+3+2+1} = 1;
a(2*3*5)   = a(30) = #{30, 15+10+5, 15+10+3+2, 15+6+5+3+1} = 4;
a(2*2*3*5) = a(60) = #{30+15+10+5, 30+15+10+3+2, 30+15+6+5+3+1} = 3;
a(2*3*7)   = a(42) = #{42, 21+14+7, 21+14+6+1} = 3;
a(2*2*3*7) = a(84) = #{42+21+14+7, 42+21+14+6+1} = 2.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000 (5000 terms from Reinhard Zumkeller)
• Noah Lebowitz-Lockard and Joseph Vandehey, On the number of partitions of a number into distinct divisors, arXiv:2402.08119 [math.NT], 2024. See p. 2.

Crossrefs

Cf. A005117, A008683, A033630, A206778, A008966, A225244, A087188, A225353, A225354.

Programs

Haskell

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

Mathematica

a[n_] := If[n == 0, 1, Coefficient[Product[If[MoebiusMu[d] != 0, 1+x^d, 1], {d, Divisors[n]}], x, n]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 08 2021, after Ilya Gutkovskiy *)

Formula

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