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

1, 1, 2, 2, 5, 2, 25, 2, 34, 19, 129, 2, 1046, 2, 742, 450, 1597, 2, 44254, 2, 27517, 3321, 29967, 2, 1872757, 571, 200390, 18560, 854850, 2, 154004511, 2, 3524578, 226020, 9262157, 51886, 3353855285, 2, 63346598, 2044895, 1255304727, 2, 185493291001, 2, 1282451595, 345852035, 2972038875, 2, 6006303471178

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Eric Weisstein's World of Mathematics, Squarefree

Index entries for sequences related to compositions

Formula

a(n) = [x^n] 1/(1 - Sum_{d|n, |mu(d)| = 1} x^d), where mu(d) is the Moebius function (A008683).

a(n) = 2 if n is a prime.

Example

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].

Maple

with(numtheory):
a:= proc(n) option remember; local b, l;
      l, b:= select(issqrfree, divisors(n)),
      proc(m) option remember; `if`(m=0, 1,
         add(`if`(j>m, 0, b(m-j)), j=l))
      end; b(n)
    end:
seq(a(n), n=0..50);   # Alois P. Heinz, Mar 30 2017

Mathematica

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}]

Prog

(Python)
from sympy import divisors
from sympy.ntheory.factor_ import core
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if core(x)==x]
    @cacheit
    def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)
    return b(n)
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 01 2017, after Maple code

Crossrefs

Cf. A005117, A008683, A100346, A225244, A225245, A280194.

Sequence in context: A271622 A324505 A226135 * A038041 A197591 A097891

Adjacent sequences: A284461 A284462 A284463 * A284465 A284466 A284467

Keyword

nonn

Author

Ilya Gutkovskiy, Mar 27 2017

Status

approved