cp's OEIS Frontend

A030983 Number of rooted noncrossing trees with n nodes such that root has degree 1 and the child of the root has degree at least 2.

%I A030983 #68 Jul 26 2022 15:34:14
%S A030983 0,3,16,83,442,2420,13566,77539,450340,2650635,15777450,94815732,
%T A030983 574518536,3506232184,21533144486,132980242755,825304177544,
%U A030983 5144743785545,32199189658020,202252227085755,1274578959894450,8056409137803600,51063344718826440
%N A030983 Number of rooted noncrossing trees with n nodes such that root has degree 1 and the child of the root has degree at least 2.
%C A030983 From _Andrei Asinowski_, May 09 2020: (Start)
%C A030983 With offset 0 (i.e., a(0) = 0 and a(1) = 3), a(n) is the total number of down-steps after the final up-step in all 2_1-Dyck paths of length 3*n.
%C A030983 A 2_1-Dyck path is a lattice path with steps U = (1, 2) and d = (1, -1) that starts at (0,0), stays (weakly) above the line y = -1, and ends at the x-axis.
%C A030983 For n = 2, a(2) = 16 is the total number of down-steps after the final up-step in dUddUd, dUdUdd, dUUddd, UdddUd, UddUdd, UdUddd, UUdddd (thus, 1 + 2 + 3 + 1 + 2 + 3 + 4). (End)
%H A030983 Andrew Howroyd, <a href="/A030983/b030983.txt">Table of n, a(n) for n = 3..200</a>
%H A030983 A. Asinowski, B. Hackl, and S. Selkirk, <a href="https://arxiv.org/abs/2007.15562">Down step statistics in generalized Dyck paths</a>, arXiv:2007.15562 [math.CO], 2020.
%H A030983 Marc Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00121-0">Enumeration of noncrossing trees on a circle</a>, Discrete Math., 180, 301-313, 1998.
%H A030983 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A030983 a(n) = (19*n - 31)*binomial(3*n - 8, n - 4)/(n - 1)/(2*n - 3).
%F A030983 G.f.: g^3*(3 - 2*g) where g*(1 - g)^2 = x. - _Mark van Hoeij_, Nov 09 2011 [That is, g = (4/3) * sin((1/3)*arcsin(sqrt(27*x/4)))^2 = x*(o.g.f. of A006013). - _Petros Hadjicostas_, Aug 08 2020]
%F A030983 From _Vladimir Kruchinin_, Mar 06 2013: (Start)
%F A030983 a(n) = binomial(3*n-5, 2*n-3)/(n-1) - 2*binomial(3*n-8, 2*n-5)/(n-2), n > 2.
%F A030983 a(n) = Sum_{i=1..n-3} binomial(3*i-2, 2*i-1) * binomial(3*(n-i-2), 2*(n-i-2)-1)/ (i*(n-i-2)).  (End)
%F A030983 a(n) ~ (76*3^(3*n - 15/2))/(4^n*sqrt(Pi)*n^(3/2)). - _Peter Luschny_, Aug 08 2020
%F A030983 D-finite with recurrence 2*(n-1)*(2*n-3)*a(n) +(-43*n^2+196*n-213)*a(n-1) +2*(62*n^2-446*n+759)*a(n-2) -12*(3*n-14)*(3*n-16)*a(n-3)=0. - _R. J. Mathar_, Jul 26 2022
%F A030983 D-finite with recurrence 2*(n-1)*(n-4)*(2*n-3)*(19*n-50)*a(n) -3*(3*n-10)*(3*n-8)*(n-3)*(19*n-31)*a(n-1)=0. - _R. J. Mathar_, Jul 26 2022
%p A030983 h := arcsin((3*sqrt(3)*sqrt(x))/2)/3:
%p A030983 gf := x*(64/9)*sin(h)^6*(1 - sin(h)^2*(8/9)): ser := series(gf, x, 32):
%p A030983 seq(coeff(ser, x, n), n=3..25); # _Peter Luschny_, Aug 08 2020
%p A030983 # Recurrence:
%p A030983 a := proc(n) option remember; if n < 4 then return 0 fi; if n = 4 then return 3 fi;
%p A030983 -((378*n^3 - 4536*n^2 + 18102*n - 24024)*a(n - 2) + (-1271*n^3 + 10308*n^2 - 26857*n + 22020)*a(n - 1))/(180*n^3 - 1170*n^2 + 2070*n - 1080) end:
%p A030983 seq(a(n), n=3..25); # _Peter Luschny_, Aug 08 2020
%t A030983 a[n_] := Binomial[3n-5, n-2]/(n-1) - 2 Binomial[3n-8, n-3]/(n-2);
%t A030983 a /@ Range[3, 25] (* _Jean-François Alcover_, Nov 03 2020, after A102892 *)
%o A030983 (PARI) a(n)=(19*n-31)*binomial(3*n-8, n-4)/(n-1)/(2*n-3); /* _Joerg Arndt_, Mar 07 2013 */
%o A030983 (PARI) concat(0, Vec((g->g^3*(3-2*g))(serreverse(x-2*x^2+x^3 + O(x^25))))) \\ _Andrew Howroyd_, Nov 12 2017
%Y A030983 Column k=1 of A102892.
%Y A030983 Cf. A006013.
%K A030983 nonn
%O A030983 3,2
%A A030983 _Emeric Deutsch_