A320271 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

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.

LINKS

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

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

EXAMPLE

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

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]

CROSSREFS

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

Sequence in context: A282842 A056768 A029511 * A056532 A079289 A365377

Adjacent sequences: A320268 A320269 A320270 * A320272 A320273 A320274

KEYWORD

nonn

AUTHOR

Gus Wiseman, Oct 08 2018

STATUS

approved