|
%I #33 Mar 04 2024 01:13:50
%S 0,1,0,4,24,256,3360,53824,1016064,22095616,543966720,14955833344,
%T 454227400704,15103031627776,545668238868480,21286707282264064,
%U 891735287528914944,39926103010743156736
%N Sequence with e.g.f. g(x) = -(1/2)*sqrt(2*exp(-2*x)-1) + 1/2.
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052 [math.CA], 2005.
%F The e.g.f. A(x) satisfies the autonomous differential equation
%F 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).
%F 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)).
%F 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
%F a(n) ~ 2^(n-3/2)*n^(n-1)/(exp(n)*(log(2))^(n-1/2)). - _Vaclav Kotesovec_, Jun 28 2013
%F 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
%e a(4) = 24: The 24 plane increasing trees on 4 vertices are
%e ............................................................
%e .........1(x4 colors).......1(x4 colors).......1(x4 colors).
%e ......../|\................/|\................/|\...........
%e ......./.|.\............../.|.\............../.|.\..........
%e ......2..3..4............2..4..3............3..2..4.........
%e ............................................................
%e .........1(x4 colors).......1(x4 colors).......1(x4 colors).
%e ......../|\................/|\................/|\...........
%e ......./.|.\............../.|.\............../.|.\..........
%e ......3..4..2............4..2..3............4..3..2.........
%e ............................................................
%t 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 *)
%o (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
%Y Cf. A000629, A000984, A124212, A124214, A229558.
%K nonn,easy
%O 0,4
%A _Karol A. Penson_, Apr 26 2010
| 