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,5

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.

Links

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

Formula

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

Example

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).

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 *)

Prog

(Haskell)
a144757 n = a000108 (a001222 n - 1) * a008480 n
-- Reinhard Zumkeller, Nov 19 2015
(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

Crossrefs

Cf. A000108, A001222, A008480, A277120.

Sequence in context: A247050 A322401 A124333 * A372835 A363520 A215136

Adjacent sequences: A144754 A144755 A144756 * A144758 A144759 A144760

Keyword

easy,nonn

Author

David Radcliffe, Sep 20 2008

Status

approved