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
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
KEYWORD
nonn,easy
AUTHOR
Paul D. Hanna, Jan 09 2014
STATUS
approved