A375120 Number of complete binary unordered tree-factorizations of n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 3, 1, 3, 1, 1, 1, 6, 1, 1, 1, 4, 1, 3, 1, 2, 2, 1, 1, 9, 1, 2, 1, 2, 1, 4, 1, 4, 1, 1, 1, 9, 1, 1, 2, 6, 1, 3, 1, 2, 1, 3, 1, 15, 1, 1, 2, 2, 1, 3, 1, 9, 2, 1, 1, 9, 1, 1, 1

Offset

1,12

Comments

For prime n, the factorization tree is a single vertex in just one way so that a(n) = 1.

For composite n, the two subtrees at n are a split of n into two factors n = d * (n/d), without order, so that a(n) = Sum_{d|n, 2 <= d <= n/d} a(d)*a(n/d).

a(1) = 1 is by convention, reckoning 1 as having a single empty factorization.

Greg Martin observed: if p is prime then a(p^k) equals the k-th 'half-Catalan number' A000992. - Peter Luschny, Nov 04 2024

Links

Table of n, a(n) for n=1..87.

Example

For n = 4, the a(4) = 1 sole factor tree is
     4     4 = 2*2
    / \
   2   2
For n=12, the a(12) = 2 factor trees are
    12          12
   /  \        /  \
  2    6      3    4
      / \         / \
     2   3       2   2
The tree structures are the same but the values are not the same and are therefore distinct factorizations.

Prog

(SageMath)
@cached_function
def a(n):
    if is_prime(n) or n == 1: return 1
    T = [t for t in divisors(n) if 1 < t <= n/t]
    return sum(a(d)*a(n//d) for d in T)
print([a(n) for n in range(1, 88)])  # Peter Luschny, Nov 03 2024

Crossrefs

Cf. A281119, A292505, A007964 (a(n)=1), A058080 (a(n)>1), A000992.

Sequence in context: A337323 A344770 A293895 * A300385 A317145 A330665

Adjacent sequences: A375117 A375118 A375119 * A375121 A375122 A375123

Keyword

nonn

Author

Baron Kurt Hannsz, Jul 30 2024

Status

approved