A320270 Number of unlabeled balanced semi-binary rooted trees with n nodes.

1, 1, 2, 2, 3, 4, 6, 7, 10, 13, 19, 25, 35, 46, 65, 88, 124, 171, 242, 334, 470, 653, 921, 1287, 1822, 2565, 3640, 5144, 7311, 10360, 14734, 20918, 29781, 42361, 60389, 86069, 122893, 175479, 250922, 358863

Offset

1,3

Comments

An unlabeled rooted tree is semi-binary if all out-degrees are <= 2, and balanced if all leaves are the same distance from the root. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

Links

Table of n, a(n) for n=1..40.

Gus Wiseman, The a(13) = 35 balanced semi-binary rooted trees.

Gus Wiseman, The a(15) = 65 balanced semi-binary rooted trees.

Gus Wiseman, The a(16) = 88 balanced semi-binary rooted trees.

Gus Wiseman, The a(18) = 171 balanced semi-binary rooted trees.

Example

The a(1) = 1 through a(7) = 6 balanced semi-binary rooted trees:
  o  (o)  (oo)   ((oo))   (((oo)))   ((o)(oo))    ((oo)(oo))
          ((o))  (((o)))  ((o)(o))   ((((oo))))   (((o)(oo)))
                          ((((o))))  (((o)(o)))   (((((oo)))))
                                     (((((o)))))  ((((o)(o))))
                                                  (((o))((o)))
                                                  ((((((o))))))

Mathematica

saur[n_]:=If[n==1, {{}}, Join@@Table[Select[Union[Sort/@Tuples[saur/@ptn]], SameQ@@Length/@Position[#, {}]&], {ptn, Select[IntegerPartitions[n-1], Length[#]<=2&]}]];
Table[Length[saur[n]], {n, 20}]

Crossrefs

Cf. A001190, A048816, A079500, A111299, A292050, A298204, A301345, A320271.

Sequence in context: A274312 A238861 A309212 * A274156 A094860 A213816

Adjacent sequences: A320267 A320268 A320269 * A320271 A320272 A320273

Keyword

nonn

Author

Gus Wiseman, Oct 08 2018

Status

approved