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

1, 1, 1, 1, 0, 1, 7, 1, 0, 0, 1, 1, 24, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 151, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 31, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 864, 1, 1, 0, 0, 1, 127, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 7, 1, 0

Offset

0,7

Comments

From Robert Israel, Dec 15 2024: (Start)

If n is squarefree, a(n) >= 1, as [n] is a composition.

If n = b * c where b and c are coprime and c is squarefree, then a(n) >= a(b), as for any composition C of b into distinct squarefree divisors, multiplying each element of C by c gives a composition of n into distinct squarefree divisors. (End)

Links

Robert Israel, Table of n, a(n) for n = 0..10000

Example

a(6) = 7 because we have [6], [3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2] and [1, 2, 3].
a(12) = 24 because we have [6, 3, 2, 1] and 4! = 24 permutations.

Maple

ptns:= proc(S, n) option remember;
  # subsets of S with sum n
  local m, s;
  if convert(S, `+`) < n then return {} fi;
  if n = 0 then return {{}} fi;
  s:= max(S);
  if s > n then return procname(select(`<=`, S, n), n) fi;
  map(t -> t union {s}, procname(S minus {s}, n-s)) union procname(S minus {s}, n)
  end proc:
sfd:= proc(n) map(convert, combinat:-powerset(numtheory:-factorset(n)), `*`) end proc:
f:= proc(n) local t;
     add((nops(t))!, t = ptns(sfd(n), n))
end proc:
map(f, [$0..100]); # Robert Israel, Dec 15 2024

Mathematica

a[n_] := Module[{d = Select[Divisors[n], SquareFreeQ]}, Total[(Length /@ Select[Subsets[d], Total[#] == n &])!]]; a[0] = 1; Array[a, 100, 0] (* Amiram Eldar, Dec 10 2024 *)

Crossrefs

Cf. A005117, A087188, A225244, A225245, A284464, A331846, A331927.

Sequence in context: A036949 A059515 A136428 * A271697 A226371 A298937

Adjacent sequences: A378840 A378841 A378842 * A378844 A378845 A378846

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 09 2024

Status

approved