cp's OEIS Frontend

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

%I A375120 #14 Nov 04 2024 05:50:44
%S A375120 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,
%T A375120 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,
%U A375120 1,3,1,15,1,1,2,2,1,3,1,9,2,1,1,9,1,1,1
%N A375120 Number of complete binary unordered tree-factorizations of n.
%C A375120 For prime n, the factorization tree is a single vertex in just one way so that a(n) = 1.
%C A375120 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).
%C A375120 a(1) = 1 is by convention, reckoning 1 as having a single empty factorization.
%C A375120 _Greg Martin_ observed: if p is prime then a(p^k) equals the k-th 'half-Catalan number' A000992. - _Peter Luschny_, Nov 04 2024
%e A375120 For n = 4, the a(4) = 1 sole factor tree is
%e A375120      4     4 = 2*2
%e A375120     / \
%e A375120    2   2
%e A375120 For n=12, the a(12) = 2 factor trees are
%e A375120     12          12
%e A375120    /  \        /  \
%e A375120   2    6      3    4
%e A375120       / \         / \
%e A375120      2   3       2   2
%e A375120 The tree structures are the same but the values are not the same and are therefore distinct factorizations.
%o A375120 (SageMath)
%o A375120 @cached_function
%o A375120 def a(n):
%o A375120     if is_prime(n) or n == 1: return 1
%o A375120     T = [t for t in divisors(n) if 1 < t <= n/t]
%o A375120     return sum(a(d)*a(n//d) for d in T)
%o A375120 print([a(n) for n in range(1, 88)])  # _Peter Luschny_, Nov 03 2024
%Y A375120 Cf. A281119, A292505, A007964 (a(n)=1), A058080 (a(n)>1), A000992.
%K A375120 nonn
%O A375120 1,12
%A A375120 _Baron Kurt Hannsz_, Jul 30 2024