OFFSET
0,3
COMMENTS
"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers.
LINKS
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.
FORMULA
G.f.: (M*T^2)/(2T-1) where M =(1-z-sqrt(1-2*z-3*z^2))/(2*z^2), the g.f. for the Motzkin numbers, and T=1/sqrt(1-2*z-3*z^2), the g.f. for the central trinomial numbers.
D-finite with recurrence: 3*(n+2)*(2*n-1)*a(n) -(4*n+5)*(2*n-1)*a(n-1) +(-20*n^2-8*n+27)*a(n-2) -3*(2*n+3)*(4*n-3)*a(n-3) -9*(2*n+3)*(n-1)*a(n-4)=0. - R. J. Mathar, Jul 24 2012
EXAMPLE
We have a(3)=9, as there are 9 vertices with even distance from the root in the 4 "0-1-2" Motzkin trees on 3 edges.
MAPLE
with(LREtools): with(FormalPowerSeries): # requires Maple 2022
M:= (1-z-sqrt(1-2*z-3*z^2))/(2*z^2): T:=1/sqrt(1-2*z-3*z^2):
ogf:= (M*T^2)/(2*T-1): req:= FindRE(ogf, z, u(n)):
init:= [1, 1, 3, 9, 24, 66]: iseq:= seq(u(i-1)=init[i], i=1..nops(init)):
rmin:= subs(n=n-4, MinimalRecurrence(req, u(n), {iseq})[1]); # Mathar's recurrence
a:= gfun:-rectoproc({rmin, iseq}, u(n), remember):
seq(a(n), n=0..27); # Georg Fischer, Nov 04 2022
# Alternative, using function FindSeq from A174403:
ogf := (1-x-sqrt(-3*x^2-2*x+1))/(2*x^2*(3*x^2+2*sqrt(-3*x^2-2*x+1)+2*x-1)):
a := FindSeq(ogf): seq(a(n), n=0..28); # Peter Luschny, Nov 04 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Lifoma Salaam, Jan 04 2011
STATUS
approved