login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A035010 Number of prime binary rooted trees with n external nodes. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
2,2
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.
REFERENCES
B. Amerlynck, Itérées d'exponentielles: aspects combinatoires et arithmétiques, Mémoire de licence, Univ. Libre de Bruxelles (1998).
LINKS
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.
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
EXAMPLE
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.
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 *)
CROSSREFS
Cf. A035102.
Sequence in context: A006611 A007462 A053623 * A349450 A055540 A006252
KEYWORD
nice,easy,nonn
AUTHOR
Bernard Amerlynck (B.Amerlynck(AT)ulg.ac.be)
EXTENSIONS
More terms from Christian G. Bower
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:34 EDT 2024. Contains 370952 sequences. (Running on oeis4.)