A292504 Number of orderless tree-factorizations of n.

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 11, 1, 6, 1, 6, 2, 2, 1, 20, 2, 2, 4, 6, 1, 8, 1, 30, 2, 2, 2, 27, 1, 2, 2, 20, 1, 8, 1, 6, 6, 2, 1, 74, 2, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 38, 1, 2, 6, 96, 2, 8, 1, 6, 2, 8, 1, 114, 1, 2, 6, 6, 2, 8, 1, 74, 11, 2, 1

Offset: 1

Author

Gus Wiseman, Sep 17 2017

Keywords

• nonn

Comments

A factorization of n is a finite multiset of positive integers greater than 1 with product n. An orderless tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless tree-factorizations, one of each factor in a factorization of n.

a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

Examples

			The a(16)=11 orderless tree-factorizations are: 16, (28), (2(24)), (2(2(22))), (2(222)), (44), (4(22)), ((22)(22)), (224), (22(22)), (2222).
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16384
• Michael De Vlieger, Records and indices of records.

Crossrefs

Cf. A000311, A001055, A050336, A141268, A281118, A292505.

Programs

Mathematica

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
Table[Length[oltfacs[n]],{n,83}]

PARI

seq(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j] += binomial(e+w[k]-1, e)*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

Formula

a(p^n) = A141268(n) for prime p. - Andrew Howroyd, Nov 18 2018