|
%I #43 Jun 03 2022 12:42:15
%S 0,1,1,1,2,3,5,8,14,25,46,85,158,294,548,1022,1908,3567,6683,12556,
%T 23669,44781,85046,162122,310157,595322,1146057,2212004,4278908,
%U 8292738,16097018,31286456,60873574,118543329,231009934,450434739,878687665
%N Number of B-trees of order infinity with n leaves, where a(n) = Sum_{k=1..floor(n/2)} a(k)*C(n-k-1,n-2*k) for n >= 2, with a(0)=0, a(1)=1.
%C A B-tree of order m is an ordered tree such that every node has at most m children, the root has at least 2 children, every node except the root has 0 or at least m/2 children, all end-nodes are at the same level. This sequence is the limit of the B-trees as m --> infinity.
%C Starting with offset 2, the eigensequence of triangle A011973. - _Gary W. Adamson_, Jul 08 2012
%C Number of balanced series-reduced rooted plane trees with n leaves. A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root. - _Gus Wiseman_, Oct 07 2018
%H Seiichi Manyama, <a href="/A119262/b119262.txt">Table of n, a(n) for n = 0..1000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/B-Tree.html">B-Tree</a>.
%F G.f. A(x) satisfies: A(x) = x + A(x^2/(1-x)).
%F G.f.: Sum_{n>=0} x^(2^n)/D(n,x) where D(0,x)=1, D(n+1,x) = D(n,x)*[D(n,x) - x^(2^n)].
%F G.f.: x = Sum_{n>=1} a(n) * x^n * (1-x^n) / (1+x)^(n-1). - _Paul D. Hanna_, Jul 31 2013
%F Conjecture: Let M_n be an n X n matrix whose elements are m_ij = 0 for i < j - 1, m_ij = -1 for i = j - 1, and m_ij = binomial(i - j, n - i) otherwise. Then a(n + 1) = Det(M_n). - _Benedict W. J. Irwin_, Apr 19 2017
%e A(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 8*x^7 + 14*x^8 + ...
%e Series form:
%e A(x) = x + x^2/(1-x) + x^4/((1-x)*((1-x)-x^2)) + x^8/((1-x)*((1-x)-x^2)*((1-x)*((1-x)-x^2)-x^4)) + ... + x^(2^n)/D(n,x) + x^(2^(n+1))/[D(n,x)*(D(n,x)-x^(2^n))] + ...
%e Terms also satisfy the series:
%e x = x*(1-x) + x^2*(1-x^2)/(1+x) + x^3*(1-x^3)/(1+x)^2 + 2*x^4*(1-x^4)/(1+x)^3 + 3*x^5*(1-x^5)/(1+x)^4 + 5*x^6*(1-x^6)/(1+x)^5 + 8*x^7*(1-x^7)/(1+x)^6 + 14*x^8*(1-x^8)/(1+x)^7 + 25*x^9*(1-x^9)/(1+x)^8 + ... + a(n)*x^n*(1-x^n)/(1+x)^(n-1) + ...
%e From _Gus Wiseman_, Oct 07 2018: (Start)
%e The a(1) = 1 through a(7) = 8 balanced series-reduced rooted plane trees:
%e o (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
%e ((oo)(oo)) ((oo)(ooo)) ((oo)(oooo)) ((oo)(ooooo))
%e ((ooo)(oo)) ((ooo)(ooo)) ((ooo)(oooo))
%e ((oooo)(oo)) ((oooo)(ooo))
%e ((oo)(oo)(oo)) ((ooooo)(oo))
%e ((oo)(oo)(ooo))
%e ((oo)(ooo)(oo))
%e ((ooo)(oo)(oo))
%e (End)
%t nn=38;f[x_]:=Sum[a[n]x^n,{n,0,nn}];a[0]=0;sol=SolveAlways[0==Series[f[x]-x-f[x^2/(1-x)],{x,0,nn}],x];Table[a[n],{n,0,nn}]/.sol (* _Geoffrey Critzer_, Mar 28 2013 *)
%o (PARI) a(n)=if(n==0,0,if(n==1,1,sum(k=1,n\2,a(k)*binomial(n-k-1,n-2*k))))
%o for(n=1, 20, print1(a(n), ", "))
%o (PARI) /* From: A(x) = x + A(x^2/(1-x)) */
%o {a(n)=local(A=x);for(i=1,n,A=x+subst(A,x,x^2/(1-x+x*O(x^n))));polcoeff(A,n)}
%o for(n=1, 20, print1(a(n), ", "))
%o (PARI) /* From: x = Sum_{n>=1} a(n)*x^n*(1-x^n)/(1+x)^(n-1) */
%o a(n)=if(n==1, 1, -polcoeff(sum(k=1, n-1, a(k)*x^k*(1-x^k)/(1+x+x*O(x^n))^(k-1)), n))
%o for(n=1, 20, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jul 31 2013
%Y Cf. A092684 (similar recurrence); B-trees: A014535 (order 3), A037026 (order 4), A058521 (order 5).
%Y Cf. A011973.
%Y Cf. A000081, A000311, A001678, A048816, A079500, A120803, A316624, A320154, A320160, A320169.
%K nonn
%O 0,5
%A _Paul D. Hanna_, May 11 2006
|
