login
Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.
0

%I #24 Nov 04 2022 17:11:27

%S 1,1,3,9,24,66,187,529,1506,4312,12394,35742,103377,299745,871011,

%T 2535873,7395522,21600720,63176964,185004852,542365407,1591631595,

%U 4675170690,13744341390,40438307599,119063564395,350799321531

%N Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.

%C "0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers.

%H Lifoma Salaam, <a href="https://search.proquest.com/docview/193997569">Combinatorial statistics on phylogenetic trees</a>, Ph.D. Dissertation, Howard University, Washington D.C., 2008.

%F 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.

%F 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

%e 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.

%p with(LREtools): with(FormalPowerSeries): # requires Maple 2022

%p M:= (1-z-sqrt(1-2*z-3*z^2))/(2*z^2): T:=1/sqrt(1-2*z-3*z^2):

%p ogf:= (M*T^2)/(2*T-1): req:= FindRE(ogf,z,u(n)):

%p init:= [1, 1, 3, 9, 24, 66]: iseq:= seq(u(i-1)=init[i],i=1..nops(init)):

%p rmin:= subs(n=n-4, MinimalRecurrence(req,u(n),{iseq})[1]); # Mathar's recurrence

%p a:= gfun:-rectoproc({rmin, iseq}, u(n), remember):

%p seq(a(n),n=0..27); # _Georg Fischer_, Nov 04 2022

%p # Alternative, using function FindSeq from A174403:

%p 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)):

%p a := FindSeq(ogf): seq(a(n), n=0..28); # _Peter Luschny_, Nov 04 2022

%Y Cf. A178834, A121320, A091958, A143364, A091958.

%K nonn

%O 0,3

%A _Lifoma Salaam_, Jan 04 2011