A050345 - OEIS

A050345

Number of ways to factor n into distinct factors with one level of parentheses.

1, 1, 1, 1, 1, 3, 1, 3, 1, 3, 1, 6, 1, 3, 3, 4, 1, 6, 1, 6, 3, 3, 1, 13, 1, 3, 3, 6, 1, 12, 1, 7, 3, 3, 3, 15, 1, 3, 3, 13, 1, 12, 1, 6, 6, 3, 1, 25, 1, 6, 3, 6, 1, 13, 3, 13, 3, 3, 1, 31, 1, 3, 6, 12, 3, 12, 1, 6, 3, 12, 1, 37, 1, 3, 6, 6, 3, 12, 1, 25, 4, 3, 1, 31, 3, 3, 3, 13, 1, 31, 3, 6, 3, 3

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

First differs from A296120 at a(36) = 15, A296120(36) = 14. - Gus Wiseman, Apr 27 2025

Each "part" in parentheses is distinct from all others at the same level. Thus (3*2)*(2) is allowed but (3)*(2*2) and (3*2*2) are not.

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).

LINKS

R. J. Mathar, Table of n, a(n) for n = 1..2519

FORMULA

Dirichlet g.f.: Product_{n>=2}(1+1/n^s)^A045778(n).

a(n) = A050346(A025487^(-1)(A046523(n))), where A025487^(-1) is the inverse with A025487^(-1)(A025487(n))=n. - R. J. Mathar, May 25 2017

a(n) = A050346(A101296(n)). - Antti Karttunen, May 25 2017

EXAMPLE

12 = (12) = (6*2) = (6)*(2) = (4*3) = (4)*(3) = (3*2)*(2).

From Gus Wiseman, Apr 26 2025: (Start)

This is the number of ways to partition a factorization of n (counted by A001055) into a set of sets. For example, the a(12) = 6 choices are:

{{2},{2,3}}

{{2},{6}}

{{3},{4}}

(End)

MATHEMATICA

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

sps[{}]:={{}}; sps[set:{i_, ___}] := Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort /@ (#/.x_Integer:>set[[x]])]& /@ sps[Range[Length[set]]]];

Table[Sum[Length[Select[mps[y], UnsameQ@@#&&And@@UnsameQ@@@#&]], {y, facs[n]}], {n, 30}] (* Gus Wiseman, Apr 26 2025 *)

CROSSREFS

Cf. A050346-A050350. a(A002110)=A000258.

For multisets of multisets we have A050336.

For integer partitions we have a(p^k) = A050342(k), see A001970, A089259, A261049.

For normal multiset partitions see A116539, A292432, A292444, A381996, A382214, A382216.

The case of a unique choice (positions of 1) is A166684.

Twice-partitions of this type are counted by A358914, see A270995, A281113, A294788.

For sets of multisets we have A383310 (distinct products A296118).

For multisets of sets we have we have A383311, see A296119.

A001055 counts factorizations, strict A045778.

A050320 counts factorizations into squarefree numbers, distinct A050326.

A302494 gives MM-numbers of sets of sets.

A382077 counts partitions that can be partitioned into a sets of sets, ranks A382200.

A382078 counts partitions that cannot be partitioned into a sets of sets, ranks A293243.

Cf. A000009, A002865, A005117, A045782, A279785, A293511, A296120, A316439, A381441, A382201.

Sequence in context: A386984 A348610 A296120 * A348611 A070039 A373032

Adjacent sequences: A050342 A050343 A050344 * A050346 A050347 A050348

KEYWORD

nonn

AUTHOR

Christian G. Bower, Oct 15 1999

STATUS

approved