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

%I #4 Oct 09 2018 15:12:54

%S 1,1,2,3,6,9,17,26,46,72,124,196,329,525,871,1396,2293,3689,6028,9717,

%T 15817,25534,41475,67009,108680,175689,284698,460387,745610,1205997,

%U 1952478,3158475,5112349,8270824,13385466,21656290,35045445,56701735,91753208

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

%C 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.

%F a(1) = 1,

%F a(2) = 1,

%F a(3) = 2,

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

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

%e The a(1) = 1 through a(7) = 17 semi-binary rooted trees:

%e o (o) (oo) ((oo)) (o(oo)) ((o(oo))) ((oo)(oo))

%e ((o)) (o(o)) (((oo))) (o((oo))) (o(o(oo)))

%e (((o))) ((o)(o)) (o(o(o))) (((o(oo))))

%e ((o(o))) ((((oo)))) ((o((oo))))

%e (o((o))) (((o)(o))) ((o(o(o))))

%e ((((o)))) (((o(o)))) (o(((oo))))

%e ((o((o)))) (o((o)(o)))

%e (o(((o)))) (o((o(o))))

%e (((((o))))) (o(o((o))))

%e (((((oo)))))

%e ((((o)(o))))

%e ((((o(o)))))

%e (((o))((o)))

%e (((o((o)))))

%e ((o(((o)))))

%e (o((((o)))))

%e ((((((o))))))

%t 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]]

%t Array[crb,20]

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

%K nonn

%O 1,3

%A _Gus Wiseman_, Oct 08 2018