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,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

Table of n, a(n) for n=0..26.

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

Cf. A178834, A121320, A091958, A143364, A091958.

Sequence in context: A096168 A051042 A121907 * A118771 A091587 A316892

Adjacent sequences: A179173 A179174 A179175 * A179177 A179178 A179179

Keyword

nonn

Author

Lifoma Salaam, Jan 04 2011

Status

approved