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

Author

Lifoma Salaam, Apr 12 2008

Keywords

• nonn

Links

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

Crossrefs

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

Programs

Magma

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

Maple

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

Mathematica

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

PARI

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

Sage

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

Formula

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)

Extensions

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