A035010 Number of prime binary rooted trees with n external nodes.

1, 2, 4, 14, 38, 132, 420, 1426, 4834, 16796, 58688, 208012, 742636, 2674384, 9693976, 35357670, 129641774, 477638700, 1767253368, 6564119892, 24466233428, 91482563640, 343059494120, 1289904147128, 4861945985428, 18367353066440, 69533549429280, 263747951750360

Offset: 2

Author

Bernard Amerlynck (B.Amerlynck(AT)ulg.ac.be)

Keywords

• nice
• easy
• nonn

Comments

If a,b are binary trees, a.b is equal to tree b where a copy of a is put on each of b's external nodes. This is non-commutative but associative. A binary tree a is prime if it is different from the 1 node tree and if a=b.c implies that b or c is equal to the 1 node tree.

Examples

			a(4) = C(3) - Sum_{d_1*d_2=4} a(d_1)*C(d_2-1) = 5 - a(2)*C(1) = 5 - 1 = 4.
		

References

• B. Amerlynck, Itérées d'exponentielles: aspects combinatoires et arithmétiques, Mémoire de licence, Univ. Libre de Bruxelles (1998).

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..1000
• V. Blondel, Une famille d'opérations sur les arbres binaires, [A family of operations on binary trees], Comptes Rendus de l'Academie des Sciences de Paris - Serie I, 321, 491-494, 1995.
• V. Blondel, Structured numbers: properties of a hierarchy of operations on binary trees, Acta Informatica, vol. 35 (1998), pp. 1-15.
• Carles Cardó, Arithmetic and k-maximality of the cyclic free magma, Algebra universalis (2019) 80:35.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A035102.

Programs

Maple

with(numtheory):
C:= n-> binomial(2*n, n)/(n+1):
a:= proc(n) option remember; C(n-1)
      -add(a(d)*C(n/d-1), d=divisors(n) minus {1, n})
    end:
seq(a(n), n=2..30);  # Alois P. Heinz, Feb 12 2015

Mathematica

a[n_] := a[n] = CatalanNumber[n-1] - Sum[If[Divisible[n, d1], d2 = n/d1; a[d1]*CatalanNumber[d2-1], 0], {d1, 2, n-1}]; a[2] = 1; Table[a[n], {n, 2, 26}] (* Jean-François Alcover, Oct 25 2011, after formula *)

Formula

a(n) = C(n-1) - Sum_{d_1*d_2=n and 1 < d_1 < n} a(d_1)*C(d_2-1) where C(n) is the n-th Catalan number (A000108).

a(n) ~ 2^(2*n - 2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 28 2024

Extensions

More terms from Christian G. Bower