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

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.

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.

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

Example

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.

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

Prog

(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

Crossrefs

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

Sequence in context: A255318 A249223 A115953 * A204770 A333382 A143379

Adjacent sequences: A225242 A225243 A225244 * A225246 A225247 A225248

Keyword

nonn

Author

Reinhard Zumkeller, May 05 2013

Status

approved