A030981 - OEIS

%I #31 Jun 28 2021 16:08:53

%S 1,1,4,11,41,146,564,2199,8835,35989,148912,623008,2633148,11222160,

%T 48181056,208180847,904593623,3950338043,17328256180,76316518987,

%U 337332601513,1495992837550,6654367576732,29681131861564

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

%H Vincenzo Librandi, <a href="/A030981/b030981.txt">Table of n, a(n) for n = 1..1000</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

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

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

%F 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

%F a(n) ~ 19^(n+1/2)/(3*sqrt(Pi)*n^(3/2)*2^(2*n+2)). - _Vaclav Kotesovec_, Oct 08 2012

%F 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

%p a := n -> (-1)^(n + 1)*2^(n - 1)*hypergeom([4/3, 5/3, 1 - n], [2, 5/2], 27/8):

%p seq(simplify(a(n)), n=1..24); # _Peter Luschny_, Aug 03 2017

%t 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 *)

%o (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

%Y Column k=0 of A101449.

%K nonn,easy

%O 1,3

%A _Emeric Deutsch_