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

Author

Ilya Gutkovskiy, Dec 09 2024

Keywords

• nonn

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)

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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