|
%I #23 May 05 2016 21:11:54
%S 1,1,5,17,109,649,5285,44513,448861,4836601,58743125,766520657,
%T 10939702669,167136559849,2746173173765,48016925121473,
%U 893361709338301,17582667488919001,365487998075525045,7994319232001122097,183644125043688405229,4418905413530661307849
%N E.g.f. satisfies: A'(x) = 1 + A(x) + 2*A(x)^2, where A(0)=0.
%C a(n) = number of increasing ordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2 and the vertices of degree 2 are colored either white or black. An example is given below. - _Peter Bala_, Sep 13 2015
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of increasing trees</a>, preprint.
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://dx.doi.org/10.1007/3-540-55251-0_2">Varieties of increasing trees</a>, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%F E.g.f.: Series_Reversion( Integral 1/(1 + x + 2*x^2) dx ).
%F E.g.f.: (sqrt(7)*tan(sqrt(7)*x/2 + arctan(1/sqrt(7)))-1)/4. - _Vaclav Kotesovec_, Jan 13 2014
%F a(n) ~ n! * 1/2*(sqrt(7)/(Pi - 2*arctan(1/sqrt(7))))^(n+1). - _Vaclav Kotesovec_, Jan 13 2014
%F O.g.f.: A(x) = x/(1-x - 2*1*2*x^2/(1-2*x - 2*2*3*x^2/(1-3*x - 2*3*4*x^2/(1-... -n*x - 2*n*(n+1)*x^2/(1- ...))))) (continued fraction). - _Paul D. Hanna_, Jun 12 2014
%F Let f(x) = 1 + x + 2*x^2. Then a(n+1) = (f(x)*d/dx)^n f(x) evaluated at x = 0. - _Peter Bala_, Sep 13 2015
%F G.f.: 1/T(0), where m=4; u=x; T(k)= 1 - u*(2*k+1) - m*u^2*(k+1)*(2*k+1)/( 1 - u*(2*k+2) - m*u^2*(k+1)*(2*k+3)/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Oct 07 2015
%F a(n) = 2^n*A(n, 1/2) where A(n,x) are the André polynomials. - _Peter Luschny_, May 05 2016
%e E.g.f.: A(x) = x + x^2/2! + 5*x^3/3! + 17*x^4/4! + 109*x^5/5! + 649*x^6/6! +...
%e Related series.
%e A(x)^2 = 2*x^2/2! + 6*x^3/3! + 46*x^4/4! + 270*x^5/5! + 2318*x^6/6! +...
%e a(4) = 17. The 17 plane (ordered) increasing unary-binary trees on 4 vertices are shown below. A * indicates the vertex of outdegree 2 may be colored either white or black.
%e ...................................................................
%e ..4................................................................
%e ..|................................................................
%e ..3..........4...4...............4...4...............3...3.........
%e ..|........./.....\............./.....\............./.....\........
%e ..2....2...3.......3...2...3...2.......2...3...4...2.......2...4...
%e ..|.....\./.........\./.....\./.........\./.....\./.........\./....
%e ..1......1*..........1*......1*..........1*......1*..........1*....
%e ...................................................................
%e ..3...4...4...3....................................................
%e ...\./.....\./.....................................................
%e ....2*......2*......................................................
%e ....|.......|......................................................
%e ....1.......1......................................................
%e ...................................................................
%e - _Peter Bala_, Sep 13 2015
%t Rest[FullSimplify[CoefficientList[Series[(Sqrt[7]*Tan[Sqrt[7]*x/2 + ArcTan[1/Sqrt[7]]]-1)/4, {x, 0, 20}], x] * Range[0, 20]!]] (* _Vaclav Kotesovec_, Jan 13 2014 *)
%t nmax = 20; Clear[g]; g[nmax+1] = 1; g[k_] := g[k] = 1 - x*(2*k+1) - 4*x^2*(k+1)*(2*k+1)/( 1 - x*(2*k+2) - 4*x^2*(k+1)*(2*k+3)/g[k+1] ); CoefficientList[Series[1/g[0], {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Oct 15 2015, after _Sergei N. Gladkovskii_ *)
%o (PARI) {a(n)=local(A=x);for(i=1,n,A=intformal(1+A+2*A^2 +x*O(x^n))); n!*polcoeff(A,n)}
%o for(n=1,25,print1(a(n),", "))
%o (PARI) {a(n)=local(A=serreverse(intformal(1/(1+x+2*x^2 +x*O(x^n))))); n!*polcoeff(A,n)}
%o for(n=1,25,print1(a(n),", "))
%o (Sage)
%o @CachedFunction
%o def c(n,k) :
%o if n==k: return 1
%o if k<1 or k>n: return 0
%o return ((n-k)//2+1)*c(n-1,k-1)+k*c(n-1,k+1)
%o def A234797(n):
%o return add(c(n,k)*2^(n-k) for k in (0..n))
%o [A234797(n) for n in (1..22)] # _Peter Luschny_, Jun 10 2014
%Y Cf. A094503.
%K nonn,easy
%O 1,3
%A _Paul D. Hanna_, Jan 09 2014
| 