A030981 Number of noncrossing bushes with n nodes; i.e., rooted noncrossing trees with n nodes and no nonroot nodes of degree 1.

1, 1, 4, 11, 41, 146, 564, 2199, 8835, 35989, 148912, 623008, 2633148, 11222160, 48181056, 208180847, 904593623, 3950338043, 17328256180, 76316518987, 337332601513, 1495992837550, 6654367576732, 29681131861564

Offset

1,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.

Index entries for sequences related to rooted trees

Formula

a(n) = Sum_{k=1..n} ((-1)^(n-k)*2^(n-k)*binomial(n, k)*binomial(3*k, k-1))/n.

G.f.: A(z) satisfies z*A(z)^3 + 3z*A(z)^2 + z*A(z) - A(z) + z = 0.

Recurrence: 2*n*(2*n+1)*a(n) = (n+2)*(3*n-1)*a(n-1) + 4*(n-2)*(15*n-13)*a(n-2) + 76*(n-3)*(n-2)*a(n-3). - Vaclav Kotesovec, Oct 08 2012

a(n) ~ 19^(n+1/2)/(3*sqrt(Pi)*n^(3/2)*2^(2*n+2)). - Vaclav Kotesovec, Oct 08 2012

a(n) = (-1)^(n+1)*2^(n-1)*hypergeom([4/3, 5/3, 1-n], [2, 5/2], 27/8). - Peter Luschny, Aug 03 2017

Maple

a := n -> (-1)^(n + 1)*2^(n - 1)*hypergeom([4/3, 5/3, 1 - n], [2, 5/2], 27/8):
seq(simplify(a(n)), n=1..24); # Peter Luschny, Aug 03 2017

Mathematica

Table[Sum[(-1)^(n-k)*2^(n-k)*Binomial[n, k]*Binomial[3*k, k-1], {k, 1, n}]/n, {n, 1, 25}] (* Vaclav Kotesovec, Oct 08 2012 *)

Prog

(PARI) a(n) = sum(k=1, n, (-1)^(n-k)*2^(n-k)*binomial(n, k)*binomial(3*k, k-1))/n; \\ Andrew Howroyd, Nov 12 2017

Crossrefs

Column k=0 of A101449.

Sequence in context: A047091 A121092 A281346 * A151455 A149269 A149270

Adjacent sequences: A030978 A030979 A030980 * A030982 A030983 A030984

Keyword

nonn,easy

Author

Emeric Deutsch

Status

approved