|
%I #20 Apr 23 2016 03:11:33
%S 1,1,2,4,9,20,48,116,288,724,1849,4768,12423,32628,86342,229952,
%T 616042,1659012,4489101,12199521,33284546,91140797,250396629,
%U 690043032,1907022197,5284167884,14677681554,40862469713,114001697975
%N Number of 1-2-3 trees with n edges and with thinning limbs.
%C A 1-2-3 tree is an ordered tree with vertices of outdegree at most 3. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.
%H Vaclav Kotesovec, <a href="/A124497/a124497.txt">Recurrence (of order 11)</a>
%F G.f.: H*T(H^2*z^3), where T=2/sqrt(3*x)*sin((1/3)*arcsin(sqrt(27*x/4))) (solution of T=1+zT^3, T(0)=1), H=C(z^2/(1-z))/(1-z) and C(x)=[1-sqrt(1-4x)]/(2x) is the Catalan function.
%F More generally, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)C[k](M[k-1]^(k-1)*z^k).
%F a(n) = Sum_{m=1..n+2} (binomial(3*m,m)*Sum_{k=0..n-m}((binomial(2*m+2*k,k)* binomial(n-m-k,2*m+k))/(2*m+k+1))) + Sum_{k=0..n/2}((binomial(2*k,k)*binomial(n-k,k))/(k+1)). - _Vladimir Kruchinin_, Apr 24 2016
%F a(n) ~ c * d^n / n^(3/2), where d = (116 + (13044347 - 19683*sqrt(419729))^(1/3) + (13044347 + 19683*sqrt(419729))^(1/3)) / 162 = 2.949682448495588889993... and c = sqrt((9801741469 + 2*(101206884976506223911903300479 - 12725091747254383734308121 * sqrt(419729))^(1/3) + 2*(101206884976506223911903300479 + 12725091747254383734308121 * sqrt(419729))^(1/3)) / (773*Pi)) / 2916 = 1.1733468012519971025510728494463... . - _Vaclav Kotesovec_, Apr 22 2016
%p C:=x->(1-sqrt(1-4*x))/2/x: T:=x->2/sqrt(3*x)*sin((1/3)*arcsin(sqrt(27*x/4))): M2:=C(z^2/(1-z))/(1-z): G:=M2*T(M2^2*z^3): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=0..33);
%t Table[(Sum[Binomial[3*m, m] * Sum[(Binomial[2*m + 2*k, k]*Binomial[n - m - k, 2*m + k])/(2*m + k + 1), {k, 0, n - m}], {m, 1, n + 2}]) + Sum[(Binomial[2*k, k]*Binomial[n - k, k])/(k + 1), {k, 0, n/2}], {n, 0, 40}] (* _Vaclav Kotesovec_, Apr 22 2016, after _Vladimir Kruchinin_ *)
%o (Maxima)
%o a(n):=(sum(binomial(3*m,m)*sum((binomial(2*m+2*k,k)*binomial(n-m-k,2*m+k))/(2*m+k+1),k,0,n-m),m,1,n+2))+sum((binomial(2*k,k)*binomial(n-k,k))/(k+1),k,0,n/2); /* _Vladimir Kruchinin_, Apr 22 2016 */
%Y Cf. A090344, A124344.
%K nonn
%O 0,3
%A _Emeric Deutsch_ and _Louis Shapiro_, Nov 04 2006
|
