login
A178834
a(n) counts anti-chains of size two in "0,1,2" Motzkin trees on n edges.
5
0, 0, 1, 5, 23, 91, 341, 1221, 4249, 14465, 48442, 160134, 523872, 1699252, 5472713, 17520217, 55801733, 176942269, 558906164, 1759436704, 5522119250, 17285351782, 53977433618, 168194390290, 523076690018, 1623869984706
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
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