login
Number of partitions of n into distinct squarefree divisors of n.
9

%I #30 Feb 17 2024 02:45:48

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

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

%U 0,1,1,1,0,1,1,0,0,1,2,1,0,0,1,1,2,1,1

%N Number of partitions of n into distinct squarefree divisors of n.

%C a(n) <= A033630(n);

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

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

%H Alois P. Heinz, <a href="/A225245/b225245.txt">Table of n, a(n) for n = 0..10000</a> (5000 terms from Reinhard Zumkeller)

%H Noah Lebowitz-Lockard and Joseph Vandehey, <a href="https://arxiv.org/abs/2402.08119">On the number of partitions of a number into distinct divisors</a>, arXiv:2402.08119 [math.NT], 2024. See p. 2.

%F 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

%e a(2*3) = a(6) = #{6, 3+2+1} = 2;

%e a(2*2*3) = a(12) = #{6+3+2+1} = 1;

%e a(2*3*5) = a(30) = #{30, 15+10+5, 15+10+3+2, 15+6+5+3+1} = 4;

%e a(2*2*3*5) = a(60) = #{30+15+10+5, 30+15+10+3+2, 30+15+6+5+3+1} = 3;

%e a(2*3*7) = a(42) = #{42, 21+14+7, 21+14+6+1} = 3;

%e a(2*2*3*7) = a(84) = #{42+21+14+7, 42+21+14+6+1} = 2.

%t a[n_] := If[n == 0, 1, Coefficient[Product[If[MoebiusMu[d] != 0, 1+x^d, 1], {d, Divisors[n]}], x, n]];

%t Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Nov 08 2021, after _Ilya Gutkovskiy_ *)

%o (Haskell)

%o a225245 n = p (a206778_row n) n where

%o p _ 0 = 1

%o p [] _ = 0

%o p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m

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

%K nonn

%O 0,7

%A _Reinhard Zumkeller_, May 05 2013