A179176 Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.
1, 1, 3, 9, 24, 66, 187, 529, 1506, 4312, 12394, 35742, 103377, 299745, 871011, 2535873, 7395522, 21600720, 63176964, 185004852, 542365407, 1591631595, 4675170690, 13744341390, 40438307599, 119063564395, 350799321531
Offset: 0
Keywords
Examples
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.
Links
- Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.
Programs
-
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
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
Comments