|
|
A120803
|
|
Number of series-reduced balanced trees with n leaves.
|
|
17
|
|
|
1, 1, 1, 2, 2, 4, 4, 8, 9, 16, 20, 37, 47, 80, 111, 183, 256, 413, 591, 940, 1373, 2159, 3214, 5067, 7649, 12054, 18488, 29203, 45237, 71566, 111658, 176710, 276870, 437820, 687354, 1085577, 1705080, 2688285, 4221333, 6644088, 10425748
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
In other words, rooted trees with all leaves at the same level and no node having exactly one child; the order of children is not significant.
|
|
LINKS
|
|
|
FORMULA
|
Let s_0(n) = 1 if n = 1, 0 otherwise; s_{k+1}(n) = EULER(s_k)(n) - s_k(n), where EULER is the Euler transform. Then a_n = sum_k s_k(n). (s_k(n) is the number of such trees of height k.) Note that s_k(n) = 0 for n < 2^k.
|
|
EXAMPLE
|
The a(10) = 16 series-reduced balanced rooted trees:
(oooooooooo)
((ooooo)(ooooo))
((oooo)(oooooo))
((ooo)(ooooooo))
((oo)(oooooooo))
((ooo)(ooo)(oooo))
((oo)(oooo)(oooo))
((oo)(ooo)(ooooo))
((oo)(oo)(oooooo))
((oo)(oo)(ooo)(ooo))
((oo)(oo)(oo)(oooo))
((oo)(oo)(oo)(oo)(oo))
(((oo)(ooo))((oo)(ooo)))
(((oo)(oo))((ooo)(ooo)))
(((oo)(oo))((oo)(oooo)))
(((oo)(oo))((oo)(oo)(oo)))
(End)
|
|
PROG
|
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(u=vector(n), v=vector(n)); u[1]=1; while(u, v+=u; u=EulerT(u)-u); v} \\ Andrew Howroyd, Oct 26 2018
|
|
CROSSREFS
|
Cf. A000081, A000669, A001003, A001678, A007059, A048816, A079500, A119262, A244925, A316624, A320154, A320160, A320169, A320179.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|