A144757 Number of factor trees for n.

1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 6, 1, 2, 2, 5, 1, 6, 1, 6, 2, 2, 1, 20, 1, 2, 2, 6, 1, 12, 1, 14, 2, 2, 2, 30, 1, 2, 2, 20, 1, 12, 1, 6, 6, 2, 1, 70, 1, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 60, 1, 2, 6, 42, 2, 12, 1, 6, 2, 12, 1, 140, 1, 2, 6, 6, 2, 12, 1, 70, 5, 2, 1, 60, 2, 2, 2, 20, 1, 60, 2, 6, 2, 2, 2, 252

Offset: 2

Author

David Radcliffe, Sep 20 2008

Keywords

• easy
• nonn

Comments

A factor tree for n is a binary tree, with the root labeled with n and the terminal nodes labeled with primes, such that each non-terminal node is the product of its two child nodes. This is the number of prime factorizations of n, ignoring the commutativity and associativity of multiplication.

Examples

			a(12)=6 because 12 can be factored as (2*2)*3, (2*3)*2, (3*2)*2, 2*(2*3), 2*(3*2) and 3*(2*2).
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A000108, A001222, A008480, A277120.

Programs

Haskell

a144757 n = a000108 (a001222 n - 1) * a008480 n
-- Reinhard Zumkeller, Nov 19 2015

Mathematica

a8480[n_] := With[{f = FactorInteger[n][[All, 2]]}, Total[f]!/Times @@ (f!)];
a[n_] := CatalanNumber[PrimeOmega[n] - 1] * a8480[n];
a /@ Range[2, 100] (* Jean-François Alcover, Sep 20 2019 *)

PARI

seq(n)={my(v=vector(n)); for(n=2, n, v[n] = isprime(n) + sumdiv(n, d, v[d]*v[n/d])); v[2..n]} \\ Andrew Howroyd, Nov 17 2018

PARI

a(n)={if(n>=2, my(sig=factor(n)[,2]); my(t=vecsum(sig)-1); binomial(2*t, t)*t!/vecprod(apply(k->k!, sig)), 0)} \\ Andrew Howroyd, Nov 17 2018

Formula

a(n) = A000108(A001222(n)-1) * A008480(n).