login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A281118 a(1)=1, a(n>1) = number of tree-factorizations of n. 36
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 (list; graph; refs; listen; history; text; internal format)
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
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
Sequence in context: A308063 A166974 A292504 * A349137 A284289 A111588
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 15 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)