A124497 Number of 1-2-3 trees with n edges and with thinning limbs.

1, 1, 2, 4, 9, 20, 48, 116, 288, 724, 1849, 4768, 12423, 32628, 86342, 229952, 616042, 1659012, 4489101, 12199521, 33284546, 91140797, 250396629, 690043032, 1907022197, 5284167884, 14677681554, 40862469713, 114001697975

Offset: 0

Author

Emeric Deutsch and Louis Shapiro, Nov 04 2006

Keywords

• nonn

Comments

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.

Links

• Vaclav Kotesovec, Recurrence (of order 11)

Crossrefs

Cf. A090344, A124344.

Programs

Maple

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);

Mathematica

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

Maxima

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 */

Formula

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.

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).

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

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