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

Offset: 1

Author

Christian G. Bower, Oct 15 1999

Keywords

• nonn

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

Examples

			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}}
  {{2,6}}
  {{3,4}}
  {{12}}
(End)
		

Links

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

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.

Programs

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

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