cp's OEIS Frontend

A176785 Sequence with e.g.f. g(x) = -(1/2)*sqrt(2*exp(-2*x)-1) + 1/2.

%I A176785 #38 Feb 08 2025 23:35:40
%S A176785 0,1,0,4,24,256,3360,53824,1016064,22095616,543966720,14955833344,
%T A176785 454227400704,15103031627776,545668238868480,21286707282264064,
%U A176785 891735287528914944,39926103010743156736
%N A176785 Sequence with e.g.f. g(x) = -(1/2)*sqrt(2*exp(-2*x)-1) + 1/2.
%H A176785 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 A176785 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 A176785 The e.g.f. A(x) satisfies the autonomous differential equation
%F A176785 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 A176785 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 A176785 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 A176785 a(n) ~ 2^(n-3/2)*n^(n-1)/(exp(n)*(log(2))^(n-1/2)). - _Vaclav Kotesovec_, Jun 28 2013
%F A176785 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 A176785 a(4) = 24: The 24 plane increasing trees on 4 vertices are
%e A176785 ............................................................
%e A176785 .........1(x4 colors).......1(x4 colors).......1(x4 colors).
%e A176785 ......../|\................/|\................/|\...........
%e A176785 ......./.|.\............../.|.\............../.|.\..........
%e A176785 ......2..3..4............2..4..3............3..2..4.........
%e A176785 ............................................................
%e A176785 .........1(x4 colors).......1(x4 colors).......1(x4 colors).
%e A176785 ......../|\................/|\................/|\...........
%e A176785 ......./.|.\............../.|.\............../.|.\..........
%e A176785 ......3..4..2............4..2..3............4..3..2.........
%e A176785 ............................................................
%t A176785 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 A176785 (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 A176785 Cf. A000629, A000984, A124212, A124214, A229558.
%K A176785 nonn,easy
%O A176785 0,4
%A A176785 _Karol A. Penson_, Apr 26 2010