cp's OEIS Frontend

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

%I A035010 #35 Jan 28 2024 16:02:40
%S A035010 1,2,4,14,38,132,420,1426,4834,16796,58688,208012,742636,2674384,
%T A035010 9693976,35357670,129641774,477638700,1767253368,6564119892,
%U A035010 24466233428,91482563640,343059494120,1289904147128,4861945985428,18367353066440,69533549429280,263747951750360
%N A035010 Number of prime binary rooted trees with n external nodes.
%C A035010 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 A035010 B. Amerlynck, Itérées d'exponentielles: aspects combinatoires et arithmétiques, Mémoire de licence, Univ. Libre de Bruxelles (1998).
%H A035010 Alois P. Heinz, <a href="/A035010/b035010.txt">Table of n, a(n) for n = 2..1000</a>
%H A035010 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 A035010 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 A035010 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 A035010 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A035010 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 A035010 a(n) ~ 2^(2*n - 2) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jan 28 2024
%e A035010 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 A035010 with(numtheory):
%p A035010 C:= n-> binomial(2*n, n)/(n+1):
%p A035010 a:= proc(n) option remember; C(n-1)
%p A035010       -add(a(d)*C(n/d-1), d=divisors(n) minus {1, n})
%p A035010     end:
%p A035010 seq(a(n), n=2..30);  # _Alois P. Heinz_, Feb 12 2015
%t A035010 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 A035010 Cf. A035102.
%K A035010 nice,easy,nonn
%O A035010 2,2
%A A035010 Bernard Amerlynck (B.Amerlynck(AT)ulg.ac.be)
%E A035010 More terms from _Christian G. Bower_