cp's OEIS Frontend

A007863 Number of hybrid binary trees with n internal nodes.

%I A007863 #107 Aug 09 2025 04:59:52
%S A007863 1,2,7,31,154,820,4575,26398,156233,943174,5785416,35955297,225914342,
%T A007863 1432705496,9158708775,58954911423,381806076426,2485972170888,
%U A007863 16263884777805,106858957537838,704810376478024,4664987368511948,30974829705533240,206266525653071416
%N A007863 Number of hybrid binary trees with n internal nodes.
%C A007863 From _Benoit Jubin_, May 27 2012: (Start)
%C A007863 Definition of hybrid binary trees:
%C A007863 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.
%C A007863 A hybrid binary tree is an equivalence class of (a,n)-labeled binary trees under this relation. (End)
%C A007863 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
%H A007863 Seiichi Manyama, <a href="/A007863/b007863.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..200 from Vincenzo Librandi)
%H A007863 R. Bacher, <a href="http://arxiv.org/abs/math/0409050">On generating series of complementary plane trees</a> arXiv:math/0409050 [math.CO], 2004.
%H A007863 Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.
%H A007863 F. Chapoton, S. Giraudo, <a href="http://arxiv.org/abs/1310.4521">Enveloping operads and bicoloured noncrossing configurations</a>, arXiv preprint arXiv:1310.4521 [math.CO], 2013-2014.
%H A007863 R. Ehrenborg and M. A. Readdy, <a href="/A007788/a007788.pdf">Sheffer posets and r-signed permutations</a>, Preprint submitted to Ann. Sci. Math. Quebec, 1994. (Annotated scanned copy)
%H A007863 Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.
%H A007863 SeoungJi Hong and SeungKyung Park, <a href="http://dx.doi.org/10.4134/BKMS.2014.51.1.229">Hybrid d-ary trees and their generalization</a>, Bull. Korean Math. Soc. 51 (2014), No. 1, pp. 229-235.
%H A007863 J. M. Pallo, <a href="http://dx.doi.org/10.1080/00207169408804251">On the listing and random generation of hybrid binary trees</a>, International Journal of Computer Mathematics, 50, 1994, 135-145.
%H A007863 Sheng-liang Yang and Mei-yang Jiang, <a href="https://journal.lut.edu.cn/EN/abstract/abstract528.shtml">Pattern avoiding problems on the hybrid d-trees</a>, J. Lanzhou Univ. Tech., (China, 2023) Vol. 49, No. 2, 144-150. (in Mandarin)
%H A007863 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A007863 G.f. A(x) satisfies: x^2*A(x)^3 + x*A(x)^2 + (-1+x)*A(x) + 1 = 0.
%F A007863 a(n) = 3F2({-n, n+1, n+2 } ; {1, 3/2})( -(1/4) ). - _Olivier Gérard_, Apr 23 2009
%F A007863 a(n) = (1/(n+1))*Sum_{k=0..n} binomial(n+k,n)*binomial(n+k+1,n-k). - _Vladimir Kruchinin_, Dec 24 2010
%F A007863 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
%F A007863 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
%F A007863 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
%F A007863 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
%F A007863 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
%F A007863 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
%e A007863 G.f. = 1 + 2*x + 7*x^2 + 31*x^3 + 154*x^4 + 820*x^5 + 4575*x^6 + ...
%p A007863 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
%t A007863 InverseSeries[Series[(y-y^2-y^3)/(1+y), {y, 0, 24}], x] (* then A(x)=y(x)/x . - _Len Smiley_, Apr 14 2000 *)
%t A007863 Table[ HypergeometricPFQ[{-n, 1 + n, 2 + n}, {1, 3/2}, -(1/4)], {n,0,23}] (* _Olivier Gérard_, Apr 23 2009 *)
%t A007863 a[ n_] := If[ n < 0, 0, HypergeometricPFQ[{-n, 1 + n, 2 + n}, {1, 3/2}, -1/4]]; (* _Michael Somos_, Dec 31 2014 *)
%o A007863 (Macsyma) taylor_solve_choose_order:true; taylor_solve( A^3*X^2+A^2*X+A*(X-1)+1,A,X,0,[ 20 ]);
%o A007863 (PARI) {a(n) = if( n<0, 0, sum(k=0, n, binomial(n+k, n) * binomial(n+k+1, n-k)) / (n+1))};
%o A007863 (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)};
%o A007863 (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)};
%Y A007863 Cf. A007788, A011365.
%Y A007863 Column k=2 of A245049.
%K A007863 nonn
%O A007863 0,2
%A A007863 Jean Pallo (pallo(AT)u-bourgogne.fr)