login
This site is supported by donations 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. 3
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

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.

Index entries for sequences related to rooted trees

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).

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 * A055540 A006252 A079995

Adjacent sequences:  A035007 A035008 A035009 * A035011 A035012 A035013

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 18 15:00 EDT 2019. Contains 326106 sequences. (Running on oeis4.)