

A178834


a(n) counts antichains 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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.
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 relement antichain in T. See Definition 42, p. 30, in Salaam (2008) but we use different notation here.
An relement antichain 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_{r1} * z^(2*r2) * L(z)^(r1) * V(z)^r, where c_r = (1/(r + 1))*binomial(2*r, r) is the rth 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_{r1} * z^(2*r2) * T(z)^(2*r1) * 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



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.
Dfinite with recurrence: (n2)*(n+2)*a(n) + (4*n^2n8)*a(n1) + (2*n^2n12)*a(n2)  3*n*(4*n3)*a(n3)  9*n*(n1)*a(n4) = 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 twoelement antichains on "0,1,2" Motzkin trees on 3 edges.


MATHEMATICA

M:= (1z Sqrt[12*z3*z^2])/(2*z^2); T:= 1/Sqrt[12*z3*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=(1zsqrt(12*z3*z^2))/(2*z^2); T=1/sqrt(12*z3*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!( (1xSqrt(12*x3*x^2))^2/(4*x^2*Sqrt(12*x3*x^2)^3) )); // G. C. Greubel, Jan 21 2019
(SageMath) ((1xsqrt(12*x3*x^2))^2/(4*x^2*sqrt(12*x3*x^2)^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jan 21 2019


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



