A320266 Number of balanced orderless tree-factorizations of n.

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 6, 1, 4, 1, 4, 2, 2, 1, 8, 2, 2, 3, 4, 1, 5, 1, 9, 2, 2, 2, 11, 1, 2, 2, 8, 1, 5, 1, 4, 4, 2, 1, 17, 2, 4, 2, 4, 1, 8, 2, 8, 2, 2, 1, 13, 1, 2, 4, 19, 2, 5, 1, 4, 2, 5, 1, 24, 1, 2, 4, 4, 2, 5, 1, 17, 6, 2, 1, 13, 2

Offset: 1

Author

Gus Wiseman, Oct 08 2018

Keywords

• nonn

Comments

A rooted tree is balanced if all leaves are the same distance from the root.

An orderless tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless tree-factorizations, one of each factor in a factorization of n.

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

Examples

			The a(36) = 11 balanced orderless tree-factorizations:
  36,
  (2*18), (3*12), (4*9), (6*6),
  (2*2*9), (2*3*6), (3*3*4),
  (2*2*3*3), ((2*2)*(3*3)), ((2*3)*(2*3)).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000669, A001055, A048816, A050336, A281118, A292505, A119262, A120803, A141268, A292504, A319312, A320160, A320267.

Programs

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[facs[n],{n}],n]];
Table[Length[Select[oltfacs[n],SameQ@@Length/@Position[#,_Integer]&]],{n,100}]

PARI

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={my(u=vector(n, i, 1), v=vector(n)); while(u, v+=u; u[1]=1; u=MultEulerT(u)-u); v} \\ Andrew Howroyd, Nov 18 2018

Formula

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