A375120 - OEIS

%I #14 Nov 04 2024 05:50:44

%S 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 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 1,3,1,15,1,1,2,2,1,3,1,9,2,1,1,9,1,1,1

%N Number of complete binary unordered tree-factorizations of n.

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

%C 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 a(1) = 1 is by convention, reckoning 1 as having a single empty factorization.

%C _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 For n = 4, the a(4) = 1 sole factor tree is

%e      4     4 = 2*2

%e     / \

%e    2   2

%e For n=12, the a(12) = 2 factor trees are

%e     12          12

%e    /  \        /  \

%e   2    6      3    4

%e       / \         / \

%e      2   3       2   2

%e The tree structures are the same but the values are not the same and are therefore distinct factorizations.

%o (SageMath)

%o @cached_function

%o def a(n):

%o     if is_prime(n) or n == 1: return 1

%o     T = [t for t in divisors(n) if 1 < t <= n/t]

%o     return sum(a(d)*a(n//d) for d in T)

%o print([a(n) for n in range(1, 88)])  # _Peter Luschny_, Nov 03 2024

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

%K nonn

%O 1,12

%A _Baron Kurt Hannsz_, Jul 30 2024