A035102 Composite binary rooted trees with external nodes.

0, 0, 1, 0, 4, 0, 9, 4, 28, 0, 98, 0, 264, 56, 869, 0, 3016, 0, 9822, 528, 33592, 0, 119530, 196, 416024, 5712, 1486724, 0, 5369336, 0, 19392637, 67184, 70715340, 3696, 259535958, 0, 955277400, 832048, 3534572062, 0, 13131221944, 0, 48932651612, 10737632, 182965127280, 0, 686158447938

Offset

2,5

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

Links

Andrew Howroyd, Table of n, a(n) for n = 2..1000

Index entries for sequences related to rooted trees

Formula

A035010(n) + a(n) = Catalan(n-1) = A000108(n-1).

Mathematica

(* b = A035010 *) b[n_] := b[n] = CatalanNumber[n-1] - Sum[If[Divisible[n, d1], d2 = n/d1; b[d1]*CatalanNumber[d2-1], 0], {d1, 2, n-1}]; b[2] = 1; a[n_] := a[n] = CatalanNumber[n-1] - b[n]; Table[a[n], {n, 2, 37}] (* Jean-François Alcover, Jul 17 2012, after formula *)

Prog

(PARI) seq(n)={my(u=vector(n-1, n, binomial(2*n, n)/(n+1)), v=vector(n-1)); v[1] = 0; for(n=2, n, v[n-1] = u[n-1] - sumdiv(n, d, if(1<d && d<n, u[d-1]*v[n/d-1]))); u - v} \\ Andrew Howroyd, Nov 07 2025

Crossrefs

Cf. A000108, A035010.

Sequence in context: A338107 A100074 A330422 * A242015 A187507 A187857

Adjacent sequences: A035099 A035100 A035101 * A035103 A035104 A035105

Keyword

nonn

Author

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

Extensions

More terms from Andrew Howroyd, Nov 07 2025

Status

approved