A335349 -id:A335349 - cp's OEIS frontend

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

5, 55, 420, 2600, 14175, 70665, 329800, 1462680, 6228945, 25661875, 102847560, 402706500, 1545715325, 5831511195, 21671504880, 79475234200, 288043346370, 1033030388790, 3669961024940, 12927078062500, 45182780785500, 156811313843420, 540722493900480, 1853503409060160

Offset: 6

Petros Hadjicostas, Jun 03 2020

nonn

"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers A001006.
A005717(n+1) is the total number of vertices (= anti-chains of size 1) in all "0,1,2" trees with n edges, A178834(n) is the total number of anti-chains of size 2 in all "0,1,2" trees on n edges, and A335349(n) is the total number of anti-chains of size 3 in all "0,1,2" trees on n edges.
It would be interesting to examine whether there is an interpretation of this sequence and sequences A178834 and A335349 in terms of Motzkin paths. (Salaam (2008) worked with different families of rooted trees, but not with Motzkin paths.)

			For n=6, we list below all a(6) = 5 four-element anti-chains in Motzkin rooted trees with 6 edges:
              A               A                    A
             / \             / \                  / \
            /   \           /   \                /   \
           B     C         B     C              B     C
          / \   / \       / \                  / \
         /   \ /   \     /   \                /   \
        D    E F   G    D     E              D     E
        {D, E, F, G}         / \            / \
                            /   \          /   \
                           F     G        F     G
                        {C, D, F, G}         {C, E, F, G}
              A                                A
             / \                              / \
            /   \                            /   \
           B     C                          B     C
                / \                              / \
               /   \                            /   \
              D     E                          D     E
             / \                                    / \
            /   \                                  /   \
           F     G                                F     G
          {B, E, F, G}                        {B, D, F, G}

Martin Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics, 18(2) (1997), 195-210. [The author counts anti-chains for some kinds of rooted trees but not for Motzkin rooted trees.]
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).

Cf. A000108, A001006, A002426, A005717, A178834, A335349.

default(seriesprecision, 50);
M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2);
T(z) = 1/sqrt(1 - 2*z - 3*z^2);
for(n=0, 30, print1(polcoef(5*z^6*T(z)^7*M(z)^4, n, z), ", "))

G.f.: A000108(r-1) * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r = 5 * z^6 * T(z)^7 * M(z)^4 (with r = 4), 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.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula