|
| |
|
|
A176785
|
|
Sequence with e.g.f. g(x) = -(1/2)*sqrt(2*exp(-2*x)-1) + 1/2.
|
|
1
|
|
|
|
0, 1, 0, 4, 24, 256, 3360, 53824, 1016064, 22095616, 543966720, 14955833344, 454227400704, 15103031627776, 545668238868480, 21286707282264064, 891735287528914944, 39926103010743156736
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
