login
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).
2
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,4
LINKS
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see p. 40.
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)
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 *)
PROG
(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
(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
(Magma) R<x>:=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
CROSSREFS
KEYWORD
nonn
AUTHOR
Lifoma Salaam, Apr 12 2008
EXTENSIONS
a(10)-a(30) from Petros Hadjicostas, Jun 02 2020
STATUS
approved