A178834 -id:A178834 - cp's OEIS frontend

A139263 Number of two element anti-chains in Riordan trees on n edges (also called non-redundant trees, i.e., ordered trees where no vertex has out-degree equal to 1).

0, 0, 1, 3, 14, 48, 172, 580, 1941, 6373, 20725, 66763, 213575, 679141, 2148948, 6771068, 21257741, 66529077, 207639925, 646480555, 2008458669, 6227766899, 19277394308, 59577651108, 183865477474, 566700165898, 1744578701517, 5364804428455, 16480883532586, 50582859417868, 155114365434224

Offset: 0

Lifoma Salaam, Apr 12 2008

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..2093
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see p. 40.

Cf. A001006, A005043, A102839, A139262, A178834.

R:=PowerSeriesRing(Rationals(), 35); [0,0] cat Coefficients(R!( (1 -x -Sqrt(1-2*x-3*x^2))*Sqrt(1-2*x-3*x^2)/(2*(1+x)*(1-2*x-3*x^2)^2) )); // G. C. Greubel, Jun 02 2020

a:= proc(n) option remember; `if`(n<4, [0$2, 1, 3][n+1],
      ((4*n-3)*(n-2)*a(n-1)+(2*n+9)*(n-2)*a(n-2)-3*
       (4*n-9)*n*a(n-3)-9*(n-1)*n*a(n-4))/(n*(n-2)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 02 2020

CoefficientList[Series[(1 -x -Sqrt[1-2*x-3*x^2])*Sqrt[1-2*x-3*x^2]/(2*(1+x)*(1 - 2*x-3*x^2)^2), {x, 0, 35}], x] (* G. C. Greubel, Jun 02 2020 *)

default(seriesprecision, 50)
f(x) = 1/sqrt(1-2*x-3*x^2);
r(x) = (1+x-sqrt(1-2*x-3*x^2))/(2*x*(1+x));
a(n) = polcoef(x^2*r(x)^2*f(x)^3, n, x);
for(n=0, 30, print1(a(n), ",")) \\ Petros Hadjicostas, Jun 02 2020

r(x)=(1+x-sqrt(1-2*x-3*x^2))/(2*x*(1+x))
m(x)=(1-x-sqrt(1-2*x-3*x^2))/(2*x^2)
g(x)=derivative(x*r(x),x)
a(x)=x^2*(x*m(x)+1)^3*g(x)^3/r(x)
taylor(a(x),x,0,30).list() # Petros Hadjicostas, Jun 02 2020

G.f.: A(x) = x^2 * (x*M(x) + 1)^3 * (d(x*R(x))/dx)^3/R(x), where M is the generating function for the Motzkin numbers and R is the generating function for the Riordan numbers.
From Petros Hadjicostas, Jun 02 2020: (Start)
Here R(x) = (1 + x - sqrt(1 - 2*x - 3*x^2))/(2*x*(1-x)) = g.f. of A005043 and M(x) = (1 - x - sqrt(1 - 2*x - 3*x^2))/(2*x^2) = g.f. of A001006.
If we let s(x) = sqrt(1 - 2*x - 3*x^2), then A(x) = x^2*((1 + x - s(x))/(2*x*(1 + x)))^2/s(x)^3 (see p. 40 in Salaam (2008)).
Alternatively, we may write A(x) = x^2 * R(x)^2 * B(x), where B(x) = g.f. of (A102839(n+1): n >= 0). (End)

a(10)-a(30) from Petros Hadjicostas, Jun 02 2020

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

Original entry on oeis.org

2, 16, 98, 500, 2308, 9920, 40522, 159212, 606790, 2256544, 8224202, 29473012, 104124044, 363374560, 1254711038, 4292365876, 14564351510, 49059814576, 164186524940, 546276316120, 1807990549352, 5955265349696, 19530431537488, 63795464433440, 207623760855106, 673440401953856

Offset: 4

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, while A178834(n) is the total number of anti-chains of size 2 in all "0,1,2" trees on n edges.

			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.
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.
        A                          F
       / \                        / \
      /   \                      /   \
     B     E                    G     H
    / \                              / \
   /   \                            /   \
  C     D                          I     K

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.

M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2);
T(z) = 1/sqrt(1 - 2*z - 3*z^2);
my(z='z+O('z^30)); Vec(2*z^4*T(z)^5*M(z)^3)

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.

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

Original entry on oeis.org

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.

A179176 Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.

Original entry on oeis.org

1, 1, 3, 9, 24, 66, 187, 529, 1506, 4312, 12394, 35742, 103377, 299745, 871011, 2535873, 7395522, 21600720, 63176964, 185004852, 542365407, 1591631595, 4675170690, 13744341390, 40438307599, 119063564395, 350799321531

Offset: 0

Lifoma Salaam, Jan 04 2011

nonn

"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers.

			We have a(3)=9, as there are 9 vertices with even distance from the root in the 4 "0-1-2" Motzkin trees on 3 edges.

Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008.

Cf. A178834, A121320, A091958, A143364, A091958.

with(LREtools): with(FormalPowerSeries): # requires Maple 2022
M:= (1-z-sqrt(1-2*z-3*z^2))/(2*z^2): T:=1/sqrt(1-2*z-3*z^2):
ogf:= (M*T^2)/(2*T-1): req:= FindRE(ogf,z,u(n)):
init:= [1, 1, 3, 9, 24, 66]: iseq:= seq(u(i-1)=init[i],i=1..nops(init)):
rmin:= subs(n=n-4, MinimalRecurrence(req,u(n),{iseq})[1]); # Mathar's recurrence
a:= gfun:-rectoproc({rmin, iseq}, u(n), remember):
seq(a(n),n=0..27); # Georg Fischer, Nov 04 2022
# Alternative, using function FindSeq from A174403:
ogf := (1-x-sqrt(-3*x^2-2*x+1))/(2*x^2*(3*x^2+2*sqrt(-3*x^2-2*x+1)+2*x-1)):
a := FindSeq(ogf): seq(a(n), n=0..28); # Peter Luschny, Nov 04 2022

G.f.: (M*T^2)/(2T-1) where M =(1-z-sqrt(1-2*z-3*z^2))/(2*z^2), the g.f. for the Motzkin numbers, and T=1/sqrt(1-2*z-3*z^2), the g.f. for the central trinomial numbers.

D-finite with recurrence: 3*(n+2)*(2*n-1)*a(n) -(4*n+5)*(2*n-1)*a(n-1) +(-20*n^2-8*n+27)*a(n-2) -3*(2*n+3)*(4*n-3)*a(n-3) -9*(2*n+3)*(n-1)*a(n-4)=0. - R. J. Mathar, Jul 24 2012

cp's OEIS Frontend

A139263 Number of two element anti-chains in Riordan trees on n edges (also called non-redundant trees, i.e., ordered trees where no vertex has out-degree equal to 1).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A179176 Number of vertices with even distance from the root in "0-1-2" Motzkin trees on n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula