OFFSET
0,4
COMMENTS
"0,1,2" trees are rooted trees where each vertex has outdegree zero, one or two. They are counted by the Motzkin numbers.
From Petros Hadjicostas, Jun 02 2020: (Start)
Let A(r,n) be the number of ordered pairs (T, s), where T is a "0,1,2" tree (Motzkin tree) with n edges and s is an r-element anti-chain in T. See Definition 42, p. 30, in Salaam (2008) but we use different notation here.
An r-element anti-chain in a tree is a set of r nodes such that, for every two nodes u and v in the set, u is neither an ancestor nor a descendant of v.
For the current sequence, a(n) = A(r=2, n) for n >= 0.
Let A[r](z) = Sum_{n >= 0} A(r,n)*z^n be the g.f. of the sequence (A(r,n): n >= 0) for fixed r >= 1.
In Theorem 44 (p. 33), Salaam proved that A[r](z) = c_{r-1} * z^(2*r-2) * L(z)^(r-1) * V(z)^r, where c_r = (1/(r + 1))*binomial(2*r, r) is the r-th Catalan number in A000108, L(z) = T(z) = 1/sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426, and V(z) = T(z)*M(z), where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2) is the g.f. of the Motzkin numbers A001006.
It follows (see Table 2.4, p. 39) that A[r](z) = c_{r-1} * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r for fixed r >= 1.
For r = 1, A[r=1](z) = Sum_{n >= 0} A(r=1, n)*z^n = T(z)*M(z) = V(z) is the g.f. of the total number of vertices in all "0,1,2" trees with n edges (i.e., the g.f. of the sequence (A005717(n+1): n >= 0)).
For r = 2, A[r=2](z) = z^2 * T(z)^3 * M(z)^2 is the g.f. of the current sequence. (End)
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see Definition 42 (p. 30), Theorem 44 (p. 33), and Table 2.4 (p. 39).
FORMULA
G.f.: z^2 * M(z)^2 * T(z)^3, where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2) is the g.f. of the Motzkin numbers and T(z) = 1/sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers.
D-finite with recurrence: -(n-2)*(n+2)*a(n) + (4*n^2-n-8)*a(n-1) + (2*n^2-n-12)*a(n-2) - 3*n*(4*n-3)*a(n-3) - 9*n*(n-1)*a(n-4) = 0. - R. J. Mathar, Jun 14 2016
a(n) ~ 3^(n + 3/2) * sqrt(n) / (4*sqrt(Pi)) * (1 - sqrt(3*Pi)/sqrt(n)). - Vaclav Kotesovec, Mar 08 2023
EXAMPLE
For n = 3, we have a(3) = 5 because there are 5 two-element anti-chains on "0,1,2" Motzkin trees on 3 edges.
MATHEMATICA
M:= (1-z -Sqrt[1-2*z-3*z^2])/(2*z^2); T:= 1/Sqrt[1-2*z-3*z^2]; CoefficientList[Series[z^2*M^2*T^3, {z, 0, 30}], z] (* G. C. Greubel, Jan 21 2019 *)
PROG
(PARI) z='z+O('z^33); M=(1-z-sqrt(1-2*z-3*z^2))/(2*z^2); T=1/sqrt(1-2*z-3*z^2); v=Vec(z^2*M^2*T^3+'tmp); v[1]=0; v
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); [0, 0] cat Coefficients(R!( (1-x-Sqrt(1-2*x-3*x^2))^2/(4*x^2*Sqrt(1-2*x-3*x^2)^3) )); // G. C. Greubel, Jan 21 2019
(SageMath) ((1-x-sqrt(1-2*x-3*x^2))^2/(4*x^2*sqrt(1-2*x-3*x^2)^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jan 21 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Lifoma Salaam, Dec 27 2010
STATUS
approved