|
| |
|
|
A248100
|
|
Number of ordered trees with n edges such that non-leaf vertices at even levels have outdegree 1 and those at odd levels have outdegree 2.
|
|
4
|
|
|
|
1, 1, 0, 1, 2, 1, 2, 6, 6, 7, 20, 30, 34, 75, 140, 182, 322, 644, 972, 1554, 3024, 5091, 8052, 14784, 26378, 43032, 75504, 136994, 232232, 399399, 720356, 1257256, 2161874, 3852576, 6831552, 11858418, 20949304, 37350768, 65554788, 115476376, 205872448
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
a(n) (n>=1) is the number of ordered trees with n-1 edges such that non-leaf vertices at even levels have outdegree 2 and those at odd levels have outdegree 1. Indeed, these trees can be obtained by deleting the root-edge from the trees described in the definition.
a(n) is also the number of excursions of length n with Motzkin-steps avoiding the consecutive steps without UU, UD and HH. The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending at (n,0) and never crossing the x-axis, i.e., staying at nonnegative altitude.
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: g(x) satisfies g = 1 + x + x^3*g^2. Sketch of proof (the symbolic method): the set S of ordered trees such that non-leaf vertices at even levels have outdegree 1 and those at odd levels have outdegree 2 consists of the one-point tree, the tree | , and the trees obtained from the tree Y (root at bottom) by attaching at each of the two leaves a tree from the set S (not necessarily the same). For the g.f. g(x) of S, x marking edges, this "decomposition picture" of S translates at once into the given equation.
G.f.: (1-sqrt(1-4*x^3-4*x^4))/(2*x^3).
a(n) = a(0)*a(n-3)+a(1)*a(n-4)+...+a(n-3)*a(0) for n>=3.
D-finite with recurrence 5*(n+3)*a(n) +4*(-n-2)*a(n-1) +4*(-n-1)*a(n-2) +10*(-2*n+3)*a(n-3) +4*(-n+5)*a(n-4) +8*(4*n-15)*a(n-5) +16*(n-5)*a(n-6)=0. - R. J. Mathar, Oct 07 2016
|
|
|
CROSSREFS
|
Cf. A329694 (Motzkin paths with different forbidden consecutive steps but a similar G.f.).
|
|
|
KEYWORD
|
nonn,walk
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
