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,4

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

Links

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

Formula

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

Example

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.

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}]

Prog

(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

Crossrefs

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

Sequence in context: A308063 A166974 A292504 * A349137 A284289 A111588

Adjacent sequences: A281115 A281116 A281117 * A281119 A281120 A281121

Keyword

nonn

Author

Gus Wiseman, Jan 15 2017

Status

approved