|
|
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
|
|
|
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:
|
|
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
|
|
|
KEYWORD
|
nice,easy,nonn
|
|
AUTHOR
|
Bernard Amerlynck (B.Amerlynck(AT)ulg.ac.be)
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|