OFFSET
0,4
LINKS
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052 [math.CA], 2005.
FORMULA
The e.g.f. A(x) satisfies the autonomous differential equation
A' = (1-2*A+2*A^2)/(1-2*A) with A(0) = 0. The compositional inverse of the e.g.f. is -1/2*log(1-2*x+2*x^2).
a(n) = (-1)^(n-1)*D^(n-1)(1) evaluated at x = 1, where D denotes the operator g(x) -> d/dx((x+1/x)*g(x)).
Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1-2*t+2*t^2)/(1-2*t) = 1+2*t^2+4*t^3+8*t^4+... leads to the following combinatorial interpretation for this sequence: a(n) gives the number of plane increasing trees on n vertices with no vertices of outdegree 1 and where each vertex of outdegree k >= 2 can be colored in 2^(k-1) ways. An example is given below. - Peter Bala, Sep 06 2011
a(n) ~ 2^(n-3/2)*n^(n-1)/(exp(n)*(log(2))^(n-1/2)). - Vaclav Kotesovec, Jun 28 2013
a(n+1) = 1/sqrt(2) * Sum_{k >= 0} (1/8)^k*binomial(2*k,k)*(2*k - 1)^n = 1/sqrt(2)*Sum_{k >= 0} (-1/2)^k*binomial(-1/2,k)*(2*k - 1)^n = Sum_{k = 0..n} ( Sum_{i = 0..k} (-1)^(k-i)/4^k* binomial(2*k,k)*binomial(k,i)*(2*i - 1)^n. Cf. A124212, A124214 and A229558. - Peter Bala, Aug 30 2016
EXAMPLE
a(4) = 24: The 24 plane increasing trees on 4 vertices are
............................................................
.........1(x4 colors).......1(x4 colors).......1(x4 colors).
......../|\................/|\................/|\...........
......./.|.\............../.|.\............../.|.\..........
......2..3..4............2..4..3............3..2..4.........
............................................................
.........1(x4 colors).......1(x4 colors).......1(x4 colors).
......../|\................/|\................/|\...........
......./.|.\............../.|.\............../.|.\..........
......3..4..2............4..2..3............4..3..2.........
............................................................
MATHEMATICA
max = 17; g[x_] := -(1/2)*Sqrt[2*Exp[-2*x] - 1] + 1/2; CoefficientList[ Series[ g[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Oct 05 2011 *)
PROG
(PARI) x='x+O('x^66); concat ([0], Vec( serlaplace( serreverse( -1/2*log(1-2*x+2*x^2) ) ) ) ) \\ Joerg Arndt, Mar 01 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Karol A. Penson, Apr 26 2010
STATUS
approved