A234797 E.g.f. satisfies: A'(x) = 1 + A(x) + 2*A(x)^2, where A(0)=0.

1, 1, 5, 17, 109, 649, 5285, 44513, 448861, 4836601, 58743125, 766520657, 10939702669, 167136559849, 2746173173765, 48016925121473, 893361709338301, 17582667488919001, 365487998075525045, 7994319232001122097, 183644125043688405229, 4418905413530661307849

Offset

1,3

Comments

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

Links

Table of n, a(n) for n=1..22.

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, preprint.

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

Formula

E.g.f.: Series_Reversion( Integral 1/(1 + x + 2*x^2) dx ).

E.g.f.: (sqrt(7)*tan(sqrt(7)*x/2 + arctan(1/sqrt(7)))-1)/4. - Vaclav Kotesovec, Jan 13 2014

a(n) ~ n! * 1/2*(sqrt(7)/(Pi - 2*arctan(1/sqrt(7))))^(n+1). - Vaclav Kotesovec, Jan 13 2014

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

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

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

a(n) = 2^n*A(n, 1/2) where A(n,x) are the André polynomials. - Peter Luschny, May 05 2016

Example

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! +...
Related series.
A(x)^2 = 2*x^2/2! + 6*x^3/3! + 46*x^4/4! + 270*x^5/5! + 2318*x^6/6! +...
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.
...................................................................
..4................................................................
..|................................................................
..3..........4...4...............4...4...............3...3.........
..|........./.....\............./.....\............./.....\........
..2....2...3.......3...2...3...2.......2...3...4...2.......2...4...
..|.....\./.........\./.....\./.........\./.....\./.........\./....
..1......1*..........1*......1*..........1*......1*..........1*....
...................................................................
..3...4...4...3....................................................
...\./.....\./.....................................................
....2*......2*......................................................
....|.......|......................................................
....1.......1......................................................
...................................................................
- Peter Bala, Sep 13 2015

Mathematica

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 *)
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 *)

Prog

(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)}
for(n=1, 25, print1(a(n), ", "))
(PARI) {a(n)=local(A=serreverse(intformal(1/(1+x+2*x^2 +x*O(x^n))))); n!*polcoeff(A, n)}
for(n=1, 25, print1(a(n), ", "))
(Sage)
@CachedFunction
def c(n, k) :
    if n==k: return 1
    if k<1 or k>n: return 0
    return ((n-k)//2+1)*c(n-1, k-1)+k*c(n-1, k+1)
def A234797(n):
    return add(c(n, k)*2^(n-k) for k in (0..n))
[A234797(n) for n in (1..22)] # Peter Luschny, Jun 10 2014

Crossrefs

Cf. A094503.

Sequence in context: A084167 A267143 A331636 * A062586 A301641 A067710

Adjacent sequences: A234794 A234795 A234796 * A234798 A234799 A234800

Keyword

nonn,easy

Author

Paul D. Hanna, Jan 09 2014

Status

approved