A292504 Number of orderless tree-factorizations of n.

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 11, 1, 6, 1, 6, 2, 2, 1, 20, 2, 2, 4, 6, 1, 8, 1, 30, 2, 2, 2, 27, 1, 2, 2, 20, 1, 8, 1, 6, 6, 2, 1, 74, 2, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 38, 1, 2, 6, 96, 2, 8, 1, 6, 2, 8, 1, 114, 1, 2, 6, 6, 2, 8, 1, 74, 11, 2, 1

Offset

1,4

Comments

A factorization of n is a finite multiset of positive integers greater than 1 with product n. 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

Links

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

Michael De Vlieger, Records and indices of records.

Formula

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

Example

The a(16)=11 orderless tree-factorizations are: 16, (28), (2(24)), (2(2(22))), (2(222)), (44), (4(22)), ((22)(22)), (224), (22(22)), (2222).

Mathematica

postfacs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[postfacs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1, {{}}, Prepend[Union@@Function[q, Sort/@Tuples[oltfacs/@q]]/@DeleteCases[postfacs[n], {n}], n]];
Table[Length[oltfacs[n]], {n, 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] += binomial(e+w[k]-1, e)*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

Crossrefs

Cf. A000311, A001055, A050336, A141268, A281118, A292505.

Sequence in context: A050363 A308063 A166974 * A281118 A349137 A284289

Adjacent sequences: A292501 A292502 A292503 * A292505 A292506 A292507

Keyword

nonn

Author

Gus Wiseman, Sep 17 2017

Status

approved