|
| |
|
|
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.
|
|
2
|
|
|
|
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
|
|
|
|
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.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
