A320271 Number of unlabeled semi-binary rooted trees with n nodes in which the non-leaf branches directly under any given node are all equal.

1, 1, 2, 3, 6, 9, 17, 26, 46, 72, 124, 196, 329, 525, 871, 1396, 2293, 3689, 6028, 9717, 15817, 25534, 41475, 67009, 108680, 175689, 284698, 460387, 745610, 1205997, 1952478, 3158475, 5112349, 8270824, 13385466, 21656290, 35045445, 56701735, 91753208

Offset: 1

Author

Gus Wiseman, Oct 08 2018

Keywords

• nonn

Comments

An unlabeled rooted tree is semi-binary if all out-degrees are <= 2. 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) = 17 semi-binary rooted trees:
  o  (o)  (oo)   ((oo))   (o(oo))    ((o(oo)))    ((oo)(oo))
          ((o))  (o(o))   (((oo)))   (o((oo)))    (o(o(oo)))
                 (((o)))  ((o)(o))   (o(o(o)))    (((o(oo))))
                          ((o(o)))   ((((oo))))   ((o((oo))))
                          (o((o)))   (((o)(o)))   ((o(o(o))))
                          ((((o))))  (((o(o))))   (o(((oo))))
                                     ((o((o))))   (o((o)(o)))
                                     (o(((o))))   (o((o(o))))
                                     (((((o)))))  (o(o((o))))
                                                  (((((oo)))))
                                                  ((((o)(o))))
                                                  ((((o(o)))))
                                                  (((o))((o)))
                                                  (((o((o)))))
                                                  ((o(((o)))))
                                                  (o((((o)))))
                                                  ((((((o))))))
		

Crossrefs

Cf. A001190, A003238, A111299, A126656, A292050, A298204, A301345, A317712, A320222, A320230, A320270.

Programs

Mathematica

crb[n_]:=Switch[n,1,1,2,1,3,2,?EvenQ,crb[n-1]+crb[n-2],?OddQ,crb[n-1]+crb[n-2]+crb[(n-1)/2]]
Array[crb,20]

Formula

a(1) = 1,

a(2) = 1,

a(3) = 2,

a(n even) = a(n-1) + a(n-2),

a(n odd) = a(n-1) + a(n-2) + a((n-1)/2).