A124329 Number of ordered trees with n edges, with thinning limbs and with root of degree 2. An ordered tree with thinning limbs is such that if a node has k children, all its children have at most k children.

0, 1, 2, 5, 10, 22, 46, 101, 220, 492, 1104, 2515, 5762, 13327, 30994, 72555, 170654, 403350, 957134, 2279947, 5449012, 13063595, 31406516, 75701507, 182902336, 442885682, 1074604288, 2612341855, 6361782006, 15518343596, 37912613630

Offset

1,3

Comments

Column 2 of A124328.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Formula

G.f.: [1-z-2z^2-sqrt(1-2z-3z^2+4z^3)]/[2(1-z)z^2].

a(n) ~ sqrt(493+101*sqrt(17)) * (1+sqrt(17))^n / (sqrt(Pi) * n^(3/2) * 2^(n+7/2)). - Vaclav Kotesovec, Sep 04 2014

a(n) = 2*Sum_{k = 0..(n-1)/2} binomial(2*k+1, k+1)*binomial(n-k, k+1)/(k+2). - Vladimir Kruchinin, Apr 21 2016

D-finite with recurrence (n+2)*a(n) +3*(-n-1)*a(n-1) +(-n+4)*a(n-2) +(7*n-13)*a(n-3) +2*(-2*n+5)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

Maple

G:=(1-z-2*z^2-sqrt(1-2*z-3*z^2+4*z^3))/2/z^2/(1-z): Gser:=series(G, z=0, 40): seq(coeff(Gser, z, n), n=1..36);
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [0$2, 1, 2][n+1],
      ((3*n+3)*a(n-1) +(n-4)*a(n-2) -(7*n-13)*a(n-3)
       +(4*n-10)*a(n-4)) / (n+2))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jul 08 2014

Mathematica

Rest[CoefficientList[Series[(1-x-2*x^2-Sqrt[1-2*x-3*x^2+4*x^3])/2/x^2/(1-x), {x, 0, 20}], x]] (* Vaclav Kotesovec, Sep 04 2014 *)
Table[2*Sum[((Binomial[2*k + 1, k + 1]*Binomial[n - k, k + 1])/(k + 2)), {k, 0, (n - 1)/2}], {n, 0, 20}] (* Vaclav Kotesovec, Apr 22 2016, after Vladimir Kruchinin *)

Prog

(Maxima)
a(n):=2*sum((binomial(2*k+1, k+1)*binomial(n-k, k+1))/(k+2), k, 0, (n-1)/2); /* Vladimir Kruchinin, Apr 21 2016 */

Crossrefs

Cf. A124344, A124328.

Sequence in context: A244398 A100938 A018004 * A144520 A101399 A320650

Adjacent sequences: A124326 A124327 A124328 * A124330 A124331 A124332

Keyword

nonn

Author

Emeric Deutsch, Nov 03 2006

Status

approved