login
Number of ordered trees with n edges, with thinning limbs and with root of degree 2. An ordered tree with thinning limbs is such that if a node has k children, all its children have at most k children.
2

%I #19 Jul 26 2022 11:16:05

%S 0,1,2,5,10,22,46,101,220,492,1104,2515,5762,13327,30994,72555,170654,

%T 403350,957134,2279947,5449012,13063595,31406516,75701507,182902336,

%U 442885682,1074604288,2612341855,6361782006,15518343596,37912613630

%N Number of ordered trees with n edges, with thinning limbs and with root of degree 2. An ordered tree with thinning limbs is such that if a node has k children, all its children have at most k children.

%C Column 2 of A124328.

%H Alois P. Heinz, <a href="/A124329/b124329.txt">Table of n, a(n) for n = 1..1000</a>

%F G.f.: [1-z-2z^2-sqrt(1-2z-3z^2+4z^3)]/[2(1-z)z^2].

%F a(n) ~ sqrt(493+101*sqrt(17)) * (1+sqrt(17))^n / (sqrt(Pi) * n^(3/2) * 2^(n+7/2)). - _Vaclav Kotesovec_, Sep 04 2014

%F a(n) = 2*Sum_{k = 0..(n-1)/2} binomial(2*k+1, k+1)*binomial(n-k, k+1)/(k+2). - _Vladimir Kruchinin_, Apr 21 2016

%F D-finite with recurrence (n+2)*a(n) +3*(-n-1)*a(n-1) +(-n+4)*a(n-2) +(7*n-13)*a(n-3) +2*(-2*n+5)*a(n-4)=0. - _R. J. Mathar_, Jul 26 2022

%p G:=(1-z-2*z^2-sqrt(1-2*z-3*z^2+4*z^3))/2/z^2/(1-z): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=1..36);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<4, [0$2, 1, 2][n+1],

%p ((3*n+3)*a(n-1) +(n-4)*a(n-2) -(7*n-13)*a(n-3)

%p +(4*n-10)*a(n-4)) / (n+2))

%p end:

%p seq(a(n), n=1..40); # _Alois P. Heinz_, Jul 08 2014

%t Rest[CoefficientList[Series[(1-x-2*x^2-Sqrt[1-2*x-3*x^2+4*x^3])/2/x^2/(1-x), {x, 0, 20}], x]] (* _Vaclav Kotesovec_, Sep 04 2014 *)

%t Table[2*Sum[((Binomial[2*k + 1, k + 1]*Binomial[n - k, k + 1])/(k + 2)), {k, 0, (n - 1)/2}], {n, 0, 20}] (* _Vaclav Kotesovec_, Apr 22 2016, after _Vladimir Kruchinin_ *)

%o (Maxima)

%o a(n):=2*sum((binomial(2*k+1, k+1)*binomial(n-k, k+1))/(k+2), k, 0, (n-1)/2); /* _Vladimir Kruchinin_, Apr 21 2016 */

%Y Cf. A124344, A124328.

%K nonn

%O 1,3

%A _Emeric Deutsch_, Nov 03 2006