A281118 a(1)=1, a(n>1) = number of tree-factorizations of n.

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 12, 1, 6, 1, 6, 2, 2, 1, 20, 2, 2, 4, 6, 1, 8, 1, 32, 2, 2, 2, 28, 1, 2, 2, 20, 1, 8, 1, 6, 6, 2, 1, 76, 2, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 38, 1, 2, 6, 112, 2, 8, 1, 6, 2, 8, 1, 116, 1, 2, 6, 6, 2, 8, 1, 76, 12, 2, 1

Offset: 1

Author

Gus Wiseman, Jan 15 2017

Keywords

• nonn

Comments

A tree-factorization of n>=2 is either (case 1) the number n or (case 2) a sequence of two or more tree-factorizations, one of each part of a weakly increasing factorization of n. These are rooted plane trees and the ordering of branches is important. For example, {{2,2},9}, {2,{2,9}}, {{2,2},{3,3}}, {6,{2,3}}, and {{2,3},6} are distinct tree-factorizations of 36, but {9,{2,2}}, {{2,9},2}, and {{3,3},{2,2}} are not.

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

Examples

			The a(30)=8 tree-factorizations are 30, 2*15, 2*(3*5), 3*10, 3*(2*5), 5*6, 5*(2*3), 2*3*5.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001055, A063834, A196545, A262673, A273873, A281113, A289501.

Programs

Mathematica

postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
treefacs[n_]:=If[n<=1,{{}},Prepend[Join@@Function[q,Tuples[treefacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
Table[Length[treefacs[n]],{n,2,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] += w[k]^e*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

Formula

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