A007863 Number of hybrid binary trees with n internal nodes.

1, 2, 7, 31, 154, 820, 4575, 26398, 156233, 943174, 5785416, 35955297, 225914342, 1432705496, 9158708775, 58954911423, 381806076426, 2485972170888, 16263884777805, 106858957537838, 704810376478024, 4664987368511948, 30974829705533240, 206266525653071416

Offset: 0

Author

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

Keywords

• nonn

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 nonassociative). 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

Examples

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
• R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
• Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
• F. Chapoton, S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv preprint arXiv:1310.4521 [math.CO], 2013-2014.
• R. Ehrenborg and M. A. Readdy, Sheffer posets and r-signed permutations, Preprint submitted to Ann. Sci. Math. Quebec, 1994. (Annotated scanned copy)
• 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.
• Sheng-liang Yang and Mei-yang Jiang, Pattern avoiding problems on the hybrid d-trees, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin)
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A007788, A011365.

Column k=2 of A245049.

Programs

Macsyma

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

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,23}] (* 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 *)

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)};

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

D-finite with recurrence: 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