A011270 Hybrid binary rooted trees with n nodes whose root is labeled by "n".

1, 1, 4, 18, 90, 481, 2690, 15547, 92124, 556664, 3417062, 21248966, 133576724, 847465593, 5419399722, 34895368578, 226050057378, 1472170887755, 9633297762870, 63305402213336, 417612181048826, 2764492667188504, 18358282050480384, 122265756020847943

Offset: 0

Author

pallo(AT)u-bourgogne.fr (Jean Pallo)

Keywords

• nonn

Examples

			G.f. A(x) = 1 + x + 4*x^2 + 18*x^3 + 90*x^4 + 481*x^5 + 2690*x^6 + 15547*x^7 + 92124*x^8 + 556664*x^9 + 3417062*x^10 + ...
where x = x*A(x) - x^2*A(x)^2/(1 - x*A(x))^2.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
• J. M. Pallo, On the listing and random generation of hybrid binary trees, International Journal of Computer Mathematics, 50, 1994, 135-145.
• Index entries for reversions of series
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A011272.

Programs

Maple

G:= proc(n) option remember; if n<=0 then 1 else convert(series(
      (x^2*G(n-1)^3 +x*G(n-1)^2 +1)/ (1-x), x=0, n+1), polynom) fi
    end:
a:= n-> coeff(1+x*G(n-1)^2, x, n):
seq(a(n), n=0..20); # Alois P. Heinz, Aug 22 2008
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [1, 1, 4][n+1], (
      6*n*(210*n^2-411*n+163)*a(n-1)-4*(n-2)*(7*n-6)*(5*n-3)*a(n-2)
      +2*(n-3)*(2*n-3)*(35*n-16)*a(n-3))/(5*n*(n+1)*(35*n-51)))
    end:
seq(a(n), n=0..25); # Alois P. Heinz, May 18 2013

Mathematica

a[0] = 1; a[n_] := n*HypergeometricPFQ[{1-n, n+1, n+2}, {3/2, 2}, -1/4]; Table[ a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 02 2015, after Vladimir Kruchinin *)

Formula

G.f.: = 1+x*G(x)^2, where G(x) is g.f. for A007863.

Reversion of x - (x/(1 - x))^2 = 0, 1, -1, -2, -3, -4, -5, ... - Olivier Gérard, Jul 05 2001

a(n) = (2/(n+2))*Sum_{j=0...n} binomial(n+j+1, n+1)*binomial(n+j+2, n-j). - Vladimir Kruchinin, Dec 24 2010

G.f. A(x) satisfies: A(x) = 1/(1 - Sum_{k>=1} k*x^k*A(x)^k). - Ilya Gutkovskiy, Apr 10 2018

G.f. A(x) satisfies: A(x) = 1 + Sum_{n>=1} n^(n-1) * x^n*A(x)^(n+1) / (1 + (n-1)*x*A(x))^(n+1). - Paul D. Hanna, Oct 08 2023

a(n) ~ sqrt((35 + (869750 - 5250*sqrt(105))^(1/3) + 5*(14*(497 + 3*sqrt(105)))^(1/3))/525) / (sqrt(Pi) * n^(3/2) * ((2 - 104/(-181 + 105*sqrt(105))^(1/3) + (-181 + 105*sqrt(105))^(1/3))/6)^n). - Vaclav Kotesovec, Oct 08 2023