A301829 Number of ways to choose a nonempty submultiset of a factorization of n into factors greater than one.

0, 1, 1, 3, 1, 4, 1, 7, 3, 4, 1, 12, 1, 4, 4, 15, 1, 12, 1, 12, 4, 4, 1, 29, 3, 4, 7, 12, 1, 17, 1, 29, 4, 4, 4, 37, 1, 4, 4, 29, 1, 17, 1, 12, 12, 4, 1, 64, 3, 12, 4, 12, 1, 29, 4, 29, 4, 4, 1, 53, 1, 4, 12, 54, 4, 17, 1, 12, 4, 17, 1, 92, 1, 4, 12, 12, 4, 17

Offset

1,4

Links

Table of n, a(n) for n=1..78.

Formula

a(n) = Sum_{d|n, d>1} f(d) * f(n/d) where f(n) = A001055(n) is the number of factorizations of n into factors greater than 1.

Example

The a(12) = 12 submultisets ("<" means subset or equal):
(2)<(2*2*3), (3)<(2*2*3), (2*2)<(2*2*3), (2*3)<(2*2*3), (2*2*3)<(2*2*3),
(2)<(2*6), (6)<(2*6), (2*6)<(2*6),
(3)<(3*4), (4)<(3*4), (3*4)<(3*4),
(12)<(12).

Mathematica

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Sum[Length[facs[d]]*Length[facs[n/d]], {d, Rest[Divisors[n]]}], {n, 100}]

Crossrefs

Cf. A000712, A001055, A001222, A001405, A122768, A276024, A281113, A284640, A295632, A299701, A299702, A299729, A301830.

Sequence in context: A335113 A295276 A301856 * A006022 A326065 A078896

Adjacent sequences: A301826 A301827 A301828 * A301830 A301831 A301832

Keyword

nonn

Author

Gus Wiseman, Mar 27 2018

Status

approved