cp's OEIS Frontend

A284464 Number of compositions (ordered partitions) of n into squarefree divisors of n.

%I A284464 #16 Feb 16 2025 08:33:43
%S A284464 1,1,2,2,5,2,25,2,34,19,129,2,1046,2,742,450,1597,2,44254,2,27517,
%T A284464 3321,29967,2,1872757,571,200390,18560,854850,2,154004511,2,3524578,
%U A284464 226020,9262157,51886,3353855285,2,63346598,2044895,1255304727,2,185493291001,2,1282451595,345852035,2972038875,2,6006303471178
%N A284464 Number of compositions (ordered partitions) of n into squarefree divisors of n.
%H A284464 Alois P. Heinz, <a href="/A284464/b284464.txt">Table of n, a(n) for n = 0..2000</a>
%H A284464 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Squarefree.html">Squarefree</a>
%H A284464 <a href="/index/Com#comp">Index entries for sequences related to compositions</a>
%F A284464 a(n) = [x^n] 1/(1 - Sum_{d|n, |mu(d)| = 1} x^d),  where mu(d) is the Moebius function (A008683).
%F A284464 a(n) = 2 if n is a prime.
%e A284464 a(4) = 5 because 4 has 3 divisors {1, 2, 4} among which 2 are squarefree {1, 2} therefore we have [2, 2], [2, 1, 1], [1, 2, 1], [1, 2, 2] and [1, 1, 1, 1].
%p A284464 with(numtheory):
%p A284464 a:= proc(n) option remember; local b, l;
%p A284464       l, b:= select(issqrfree, divisors(n)),
%p A284464       proc(m) option remember; `if`(m=0, 1,
%p A284464          add(`if`(j>m, 0, b(m-j)), j=l))
%p A284464       end; b(n)
%p A284464     end:
%p A284464 seq(a(n), n=0..50);   # _Alois P. Heinz_, Mar 30 2017
%t A284464 Table[d = Divisors[n]; Coefficient[Series[1/(1 - Sum[MoebiusMu[d[[k]]]^2 x^d[[k]], {k, Length[d]}]), {x, 0, n}], x, n], {n, 0, 48}]
%o A284464 (Python)
%o A284464 from sympy import divisors
%o A284464 from sympy.ntheory.factor_ import core
%o A284464 from sympy.core.cache import cacheit
%o A284464 @cacheit
%o A284464 def a(n):
%o A284464     l=[x for x in divisors(n) if core(x)==x]
%o A284464     @cacheit
%o A284464     def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)
%o A284464     return b(n)
%o A284464 print([a(n) for n in range(51)]) # _Indranil Ghosh_, Aug 01 2017, after Maple code
%Y A284464 Cf. A005117, A008683, A100346, A225244, A225245, A280194.
%K A284464 nonn
%O A284464 0,3
%A A284464 _Ilya Gutkovskiy_, Mar 27 2017