A035010 - OEIS

%I #35 Jan 28 2024 16:02:40

%S 1,2,4,14,38,132,420,1426,4834,16796,58688,208012,742636,2674384,

%T 9693976,35357670,129641774,477638700,1767253368,6564119892,

%U 24466233428,91482563640,343059494120,1289904147128,4861945985428,18367353066440,69533549429280,263747951750360

%N Number of prime binary rooted trees with n external nodes.

%C 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.

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

%H Alois P. Heinz, <a href="/A035010/b035010.txt">Table of n, a(n) for n = 2..1000</a>

%H V. Blondel, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k6473221w/f113.image">Une famille d'opérations sur les arbres binaires</a>, [A family of operations on binary trees], Comptes Rendus de l'Academie des Sciences de Paris - Serie I, 321, 491-494, 1995.

%H V. Blondel, <a href="http://www.inma.ucl.ac.be/~blondel/publications/98B-snumbers.pdf">Structured numbers: properties of a hierarchy of operations on binary trees</a>, Acta Informatica, vol. 35 (1998), pp. 1-15.

%H Carles Cardó, <a href="https://doi.org/10.1007/s00012-019-0608-2">Arithmetic and k-maximality of the cyclic free magma</a>, Algebra universalis (2019) 80:35.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

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

%F a(n) ~ 2^(2*n - 2) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jan 28 2024

%e 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.

%p with(numtheory):

%p C:= n-> binomial(2*n, n)/(n+1):

%p a:= proc(n) option remember; C(n-1)

%p       -add(a(d)*C(n/d-1), d=divisors(n) minus {1, n})

%p     end:

%p seq(a(n), n=2..30);  # _Alois P. Heinz_, Feb 12 2015

%t 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 *)

%Y Cf. A035102.

%K nice,easy,nonn

%O 2,2

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

%E More terms from _Christian G. Bower_