A030982 Number of noncrossing nonplanted bushes with n nodes, i.e., rooted noncrossing trees with n nodes and no nodes of degree 1.

0, 1, 1, 7, 18, 80, 284, 1169, 4628, 19137, 79165, 333058, 1410608, 6029816, 25941384, 112315945, 488862888, 2138161043, 9391903131, 41414729419, 183264846010, 813564012660, 3622193670040, 16170171489820, 72364908958800, 324586284275500, 1458976377988636

Offset

1,4

Links

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

Index entries for sequences related to rooted trees

Formula

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

Recurrence: 2*n*(2*n+1)*a(n) = (n-1)*(11*n-12)*a(n-1) + 6*(9*n^2-21*n+8) * a(n-2) - 4*(n-3)*(11*n-56)*a(n-3) - 152*(n-4)*(n-3)*a(n-4). - Vaclav Kotesovec, Oct 24 2012

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

a(n) = A030981(n) - A030980(n). - Andrew Howroyd, Nov 12 2017

Mathematica

Table[5*Sum[(-1)^(n-k)*2^(n-k)*k*Binomial[n, k]*Binomial[3*k-2, k-2]/ (2*k+1), {k, 2, n}]/n, {n, 1, 20}] (* Vaclav Kotesovec, Oct 24 2012 *)

Prog

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

Crossrefs

Cf. A030980, A030981.

Sequence in context: A019534 A024830 A262489 * A203381 A207158 A304992

Adjacent sequences: A030979 A030980 A030981 * A030983 A030984 A030985

Keyword

nonn,easy

Author

Emeric Deutsch

Status

approved