cp's OEIS Frontend

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

%I A335349 #35 Jun 12 2022 03:00:26
%S A335349 2,16,98,500,2308,9920,40522,159212,606790,2256544,8224202,29473012,
%T A335349 104124044,363374560,1254711038,4292365876,14564351510,49059814576,
%U A335349 164186524940,546276316120,1807990549352,5955265349696,19530431537488,63795464433440,207623760855106,673440401953856
%N A335349 a(n) counts anti-chains of size three in "0,1,2" Motzkin trees on n edges.
%C A335349 "0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers A001006.
%C A335349 A005717(n+1) is the total number of vertices (= anti-chains of size 1) in all "0,1,2" trees with n edges, while A178834(n) is the total number of anti-chains of size 2 in all "0,1,2" trees on n edges.
%H A335349 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 A335349 G.f. is A000108(r-1) * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r = 2 * z^4 * T(z)^5 * M(z)^3 (with r = 3),  where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2)) / (2*z^2) is the g.f. of the Motzkin numbers A001006 and T(z) = 1 / sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426.
%e A335349 Out of the A001006(4) = 9 Motzkin rooted trees, there are only two that have anti-chains of size 3 (i.e., 3-sets of pairwise incomparable nodes), and each one has only one such an anti-chain. Thus, a(4) = 1 + 1 = 2.
%e A335349 In the first Motzkin tree below with 4 edges, {E, C, D} is an anti-chain of size 3. In the second one, {G, I, K} is an anti-chain of size 3.
%e A335349         A                          F
%e A335349        / \                        / \
%e A335349       /   \                      /   \
%e A335349      B     E                    G     H
%e A335349     / \                              / \
%e A335349    /   \                            /   \
%e A335349   C     D                          I     K
%o A335349 (PARI) M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2);
%o A335349 T(z) = 1/sqrt(1 - 2*z - 3*z^2);
%o A335349 my(z='z+O('z^30)); Vec(2*z^4*T(z)^5*M(z)^3)
%Y A335349 Cf. A000108, A001006, A002426, A005717, A178834.
%K A335349 nonn
%O A335349 4,1
%A A335349 _Petros Hadjicostas_, Jun 03 2020