|
|
A030981
|
|
Number of noncrossing bushes with n nodes; i.e., rooted noncrossing trees with n nodes and no nonroot nodes of degree 1.
|
|
4
|
|
|
1, 1, 4, 11, 41, 146, 564, 2199, 8835, 35989, 148912, 623008, 2633148, 11222160, 48181056, 208180847, 904593623, 3950338043, 17328256180, 76316518987, 337332601513, 1495992837550, 6654367576732, 29681131861564
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
|
|
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):
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|