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

1, 0, 3, 4, 23, 66, 280, 1030, 4207, 16852, 69747, 289950, 1222540, 5192344, 22239672, 95864902, 415730735, 1812177000, 7936353049, 34901789568, 154067755503, 682428824890, 3032173906692, 13510960371744, 60360526255204, 270311970889296, 1213232586744900, 5456560663318648

Offset

1,3

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

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-2, k-1))/n.

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

D-finite with recurrence -2*n*(2*n-1)*a(n) +3*n*(n-2)*a(n-1) +30*(2*n-3)*(n-2)*a(n-2) +76*(n-2)*(n-3)*a(n-3)=0. - R. J. Mathar, Jul 24 2022

Prog

(PARI) a(n) = sum(k=1, n, ((-1)^(n-k)*2^(n-k)*binomial(n, k)*binomial(3*k-2, k-1))/n) \\ Michel Marcus, Aug 03 2017
(PARI) seq(n)={Vec(serreverse(x/(1/(1 -x)^2 - 2*x) + O(x*x^n)))} \\ Andrew Howroyd, Nov 21 2024

Crossrefs

Cf. A378079.

Sequence in context: A002351 A042035 A343402 * A041861 A042377 A276815

Adjacent sequences: A030977 A030978 A030979 * A030981 A030982 A030983

Keyword

nonn,changed

Author

Emeric Deutsch

Extensions

a(25) onwards from Andrew Howroyd, Nov 21 2024

Status

approved