|
%I #47 Feb 23 2024 17:43:41
%S 0,0,1,5,23,91,341,1221,4249,14465,48442,160134,523872,1699252,
%T 5472713,17520217,55801733,176942269,558906164,1759436704,5522119250,
%U 17285351782,53977433618,168194390290,523076690018,1623869984706
%N a(n) counts anti-chains of size two 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.
%C From _Petros Hadjicostas_, Jun 02 2020: (Start)
%C 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.
%C 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.
%C For the current sequence, a(n) = A(r=2, n) for n >= 0.
%C 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.
%C 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.
%C 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.
%C 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)).
%C For r = 2, A[r=2](z) = z^2 * T(z)^3 * M(z)^2 is the g.f. of the current sequence. (End)
%H G. C. Greubel, <a href="/A178834/b178834.txt">Table of n, a(n) for n = 0..1000</a>
%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; see Definition 42 (p. 30), Theorem 44 (p. 33), and Table 2.4 (p. 39).
%F 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.
%F 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
%F a(n) ~ 3^(n + 3/2) * sqrt(n) / (4*sqrt(Pi)) * (1 - sqrt(3*Pi)/sqrt(n)). - _Vaclav Kotesovec_, Mar 08 2023
%e 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.
%t 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 *)
%o (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
%o (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
%o (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
%Y Cf. A000108, A002426, A001006, A005717.
%K nonn
%O 0,4
%A _Lifoma Salaam_, Dec 27 2010
|
