login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007863 Number of hybrid binary trees with n internal nodes. 20
1, 2, 7, 31, 154, 820, 4575, 26398, 156233, 943174, 5785416, 35955297, 225914342, 1432705496, 9158708775, 58954911423, 381806076426, 2485972170888, 16263884777805, 106858957537838, 704810376478024, 4664987368511948, 30974829705533240, 206266525653071416 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

From Benoit Jubin, May 27 2012: (Start)

Definition of hybrid binary trees:

An (a,n)-labeled binary tree is a binary tree where each internal node is labeled by "a" (for associative) or "n" (for non associative). We define on the set of (a,n)-labeled binary trees with a given number of nodes an equivalence relation as follows: denote a tree with a root labeled "a" with left subtree A and right subtree B by AaB. Then we declare the trees (AaB)aC and Aa(BaC) equivalent, and two trees are equivalent if and only if one can go from one to the other by doing such transformations within any of their subtrees.

A hybrid binary tree is an equivalence class of (a,n)-labeled binary trees under this relation. (End)

Also the number of Dyck n-paths with up steps colored in two ways (N or A) and avoiding AA. The 7 Dyck 2-paths are NDND, NDAD, ADND, ADAD, NNDD, NADD, and ANDD. - David Scambler, May 21 2012

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO]

F. Chapoton, S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv preprint arXiv:1310.4521, 2013

Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

SeoungJi Hong and SeungKyung Park, Hybrid d-ary trees and their generalization, Bull. Korean Math. Soc. 51 (2014), No. 1, pp. 229-235.

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 sequences related to rooted trees

FORMULA

G.f. A(x) satisfies: x^2*A(x)^3 + x*A(x)^2 + (-1+x)*A(x) + 1 = 0.

a(n) = 3F2({-n, n+1, n+2 } ; {1, 3/2})( -(1/4) ). - Olivier Gérard, Apr 23 2009

a(n) = 1/(n+1)*sum(k=0..n, binomial(n+k,n)*binomial(n+k+1,n-k)). - Vladimir Kruchinin, Dec 24 2010

G.f.: A(x) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2*A(x)^k] * x^n/n ). - Paul D. Hanna, Feb 13 2011

The formal inverse of the g.f. A(x) is (sqrt(5*x^2 - 2*x + 1) - (1+x))/(2*x^2). - Paul D. Hanna, Aug 21 2012

The radius of convergence of g.f. A(x) is r = 0.1407810125... with A(r) = 2.1107712092... such that y=A(r) satisfies 5*y^3 - 12*y^2 + 4*y - 2 = 0. - Paul D. Hanna, Aug 21 2012

Conjecture: 45*n*(n+1)*a(n) -2*n*(157*n-71)*a(n-1) +12*(-3*n^2+15*n-14)*a(n-2) +2*(-14*n^2+43*n-21)*a(n-3) -4*(n-3)*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jun 03 2014

Recurrence (of order 3): 5*n*(n+1)*(35*n-62)*a(n) = 6*n*(210*n^2 - 477*n + 181)*a(n-1) - 4*n*(35*n^2 - 132*n + 115)*a(n-2) + 2*(n-2)*(2*n-5)*(35*n-27)*a(n-3). - Vaclav Kotesovec, Jul 11 2014

a(n) ~ sqrt((s*(1+s+2*r*s^2))/(1+3*r*s)) / (2*sqrt(Pi) * r^n * n^(3/2)), where r = 52/(3*(181 + 105*sqrt(105))^(1/3)) - 1/6*(181 + 105*sqrt(105))^(1/3) + 1/3 = 0.1407810125885522212..., s = 1/15*(12 + (1323 - 105*sqrt(105))^(1/3) + (21*(63 + 5*sqrt(105)))^(1/3)) = 2.110771209224758867... . - Vaclav Kotesovec, Jul 11 2014

EXAMPLE

G.f. = 1 + 2*x + 7*x^2 + 31*x^3 + 154*x^4 + 820*x^5 + 4575*x^6 + ...

MAPLE

A:= proc(n) option remember; if n=0 then 1 else convert(series((x^2 *A(n-1)^3 +x*A(n-1)^2 +1)/ (1-x), x=0, n+1), polynom) fi end: a:= n-> coeff(A(n), x, n): seq(a(n), n=0..30); # Alois P. Heinz, Aug 22 2008

MATHEMATICA

InverseSeries[Series[(y-y^2-y^3)/(1+y), {y, 0, 24}], x] (* then A(x)=y(x)/x . - Len Smiley, Apr 14 2000 *)

Table[ HypergeometricPFQ[{-n, 1 + n, 2 + n}, {1, 3/2}, -(1/4)], {n, 0, 20}] - Olivier Gérard, Apr 23 2009

a[ n_] := If[ n < 0, 0, HypergeometricPFQ[{-n, 1 + n, 2 + n}, {1, 3/2}, -1/4]]; (* Michael Somos, Dec 31 2014 *)

PROG

(Macsyma) taylor_solve_choose_order:true; taylor_solve( A^3*X^2+A^2*X+A*(X-1)+1, A, X, 0, [ 20 ]);

(PARI) {a(n) = if( n<0, 0, sum(k=0, n, binomial(n+k, n) * binomial(n+k+1, n-k)) / (n+1))};

(PARI) {a(n) = local(A = 1 + x + x * O(x^n)); for(i=1, n, A = 1 + x * (A + A^2) + x^2 * A^3); polcoeff(A, n)};

(PARI) {a(n) = local(A=1+x); for(i=1, n, A = exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2 * (A + x * O(x^n))^j) * x^m / m))); polcoeff(A, n, x)};

CROSSREFS

Cf. A007788.

Column k=2 of A245049.

Sequence in context: A007164 A126033 A256672 * A030823 A030873 A030913

Adjacent sequences:  A007860 A007861 A007862 * A007864 A007865 A007866

KEYWORD

nonn

AUTHOR

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 13:47 EDT 2017. Contains 284176 sequences.