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

Author

Emeric Deutsch

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A378079.

Programs

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

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

Extensions

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