login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335355 a(n) counts anti-chains of size four in "0,1,2" Motzkin trees on n edges. 1
5, 55, 420, 2600, 14175, 70665, 329800, 1462680, 6228945, 25661875, 102847560, 402706500, 1545715325, 5831511195, 21671504880, 79475234200, 288043346370, 1033030388790, 3669961024940, 12927078062500, 45182780785500, 156811313843420, 540722493900480, 1853503409060160 (list; graph; refs; listen; history; text; internal format)
OFFSET

6,1

COMMENTS

"0,1,2" trees are rooted trees where each vertex has out degree 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.)

LINKS

Table of n, a(n) for n=6..29.

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

FORMULA

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.

EXAMPLE

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}

PROG

(PARI) 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), ", "))

CROSSREFS

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

Sequence in context: A144893 A015266 A138163 * A306095 A081300 A190543

Adjacent sequences:  A335352 A335353 A335354 * A335356 A335357 A335358

KEYWORD

nonn

AUTHOR

Petros Hadjicostas, Jun 03 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 15:27 EDT 2021. Contains 347658 sequences. (Running on oeis4.)