login
Number of complete orderless tree-factorizations of n >= 2.
16

%I #9 Nov 18 2018 19:26:48

%S 1,1,1,1,1,1,2,1,1,1,3,1,1,1,5,1,3,1,3,1,1,1,9,1,1,2,3,1,4,1,12,1,1,1,

%T 12,1,1,1,9,1,4,1,3,3,1,1,29,1,3,1,3,1,9,1,9,1,1,1,17,1,1,3,33,1,4,1,

%U 3,1,4,1,44,1,1,3,3,1,4,1,29,5,1,1,17,1

%N Number of complete orderless tree-factorizations of n >= 2.

%C An orderless tree-factorization (see A292504 for definition) is complete if all leaves are prime numbers. This sequence first differs from A281119 at a(64)=33.

%C a(n) depends only on the prime signature of n. - _Andrew Howroyd_, Nov 18 2018

%H Andrew Howroyd, <a href="/A292505/b292505.txt">Table of n, a(n) for n = 2..10000</a>

%F a(p^n) = A000669(n) for prime p. - _Andrew Howroyd_, Nov 18 2018

%e The a(60)=17 complete orderless tree-factorizations are: (2(2(35))), (2(3(25))), (2(5(23))), (2(235)), (3(2(25))), (3(5(22))), (3(225)), (5(2(23))), (5(3(22))), (5(223)), ((22)(35)), ((23)(25)), (22(35)), (23(25)), (25(23)), (35(22)), (2235).

%t postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];

%t oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];

%t Table[Length[Select[oltfacs[n],FreeQ[#,_Integer?(!PrimeQ[#]&)]&]],{n,2,100}]

%o (PARI) seq(n)={my(v=vector(n), w=vector(n)); v[1]=1; for(k=2, n, w[k]=v[k]+isprime(k); 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[2..n]} \\ _Andrew Howroyd_, Nov 18 2018

%Y Cf. A000311, A000669, A001055, A050336, A281119, A292504.

%K nonn

%O 2,7

%A _Gus Wiseman_, Sep 17 2017