Baron Kurt Hannsz - cp's OEIS frontend

User: Baron Kurt Hannsz

Baron Kurt Hannsz has authored 1 sequences.

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

Baron Kurt Hannsz, Jul 30 2024

nonn

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

			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.

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

@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

cp's OEIS Frontend

User: Baron Kurt Hannsz

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

SageMath