|
%I #104 May 16 2023 12:10:42
%S 1,2,7,31,154,820,4575,26398,156233,943174,5785416,35955297,225914342,
%T 1432705496,9158708775,58954911423,381806076426,2485972170888,
%U 16263884777805,106858957537838,704810376478024,4664987368511948,30974829705533240,206266525653071416
%N Number of hybrid binary trees with n internal nodes.
%C From _Benoit Jubin_, May 27 2012: (Start)
%C Definition of hybrid binary trees:
%C 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 A hybrid binary tree is an equivalence class of (a,n)-labeled binary trees under this relation. (End)
%C 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 Seiichi Manyama, <a href="/A007863/b007863.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..200 from Vincenzo Librandi)
%H 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 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 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 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 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 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 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 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 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F G.f. A(x) satisfies: x^2*A(x)^3 + x*A(x)^2 + (-1+x)*A(x) + 1 = 0.
%F a(n) = 3F2({-n, n+1, n+2 } ; {1, 3/2})( -(1/4) ). - _Olivier Gérard_, Apr 23 2009
%F 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 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 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 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 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 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 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 G.f. = 1 + 2*x + 7*x^2 + 31*x^3 + 154*x^4 + 820*x^5 + 4575*x^6 + ...
%p 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 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 Table[ HypergeometricPFQ[{-n, 1 + n, 2 + n}, {1, 3/2}, -(1/4)], {n,0,20}] - _Olivier Gérard_, Apr 23 2009
%t a[ n_] := If[ n < 0, 0, HypergeometricPFQ[{-n, 1 + n, 2 + n}, {1, 3/2}, -1/4]]; (* _Michael Somos_, Dec 31 2014 *)
%o (Macsyma) taylor_solve_choose_order:true; taylor_solve( A^3*X^2+A^2*X+A*(X-1)+1,A,X,0,[ 20 ]);
%o (PARI) {a(n) = if( n<0, 0, sum(k=0, n, binomial(n+k, n) * binomial(n+k+1, n-k)) / (n+1))};
%o (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 (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 Cf. A007788, A011365.
%Y Column k=2 of A245049.
%K nonn
%O 0,2
%A Jean Pallo (pallo(AT)u-bourgogne.fr)
|
