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

Author

Gus Wiseman, Oct 08 2018

Keywords

• nonn

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.

Examples

			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))))))
		

Links

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

Crossrefs

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

Programs

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}]