cp's OEIS Frontend

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

%I A281118 #18 Nov 18 2018 19:25:47
%S A281118 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,
%T A281118 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,
%U A281118 112,2,8,1,6,2,8,1,116,1,2,6,6,2,8,1,76,12,2,1
%N A281118 a(1)=1, a(n>1) = number of tree-factorizations of n.
%C A281118 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.
%C A281118 a(n) depends only on the prime signature of n. - _Andrew Howroyd_, Nov 18 2018
%H A281118 Michael De Vlieger, <a href="/A281118/b281118.txt">Table of n, a(n) for n = 1..10000</a>
%F A281118 a(p^n) = A289501(n) for prime p. - _Andrew Howroyd_, Nov 18 2018
%e A281118 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.
%t A281118 postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
%t A281118 treefacs[n_]:=If[n<=1,{{}},Prepend[Join@@Function[q,Tuples[treefacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
%t A281118 Table[Length[treefacs[n]],{n,2,83}]
%o A281118 (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
%Y A281118 Cf. A001055, A063834, A196545, A262673, A273873, A281113, A289501.
%K A281118 nonn
%O A281118 1,4
%A A281118 _Gus Wiseman_, Jan 15 2017