A178834 a(n) counts anti-chains of size two in "0,1,2" Motzkin trees on n edges.

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

Author

Lifoma Salaam, Dec 27 2010

Keywords

• nonn

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)

Examples

			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.
		

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).

Crossrefs

Cf. A000108, A002426, A001006, A005717.

Programs

Magma

m:=30; R:=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

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 *)

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

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

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