login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A124497 Number of 1-2-3 trees with n edges and with thinning limbs. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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

Table of n, a(n) for n=0..28.

Vaclav Kotesovec, Recurrence (of order 11)

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

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

PROG

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

CROSSREFS

Cf. A090344, A124344.

Sequence in context: A145550 A000081 A123467 * A286983 A289971 A093637

Adjacent sequences:  A124494 A124495 A124496 * A124498 A124499 A124500

KEYWORD

nonn

AUTHOR

Emeric Deutsch and Louis Shapiro, Nov 04 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 21:15 EST 2017. Contains 295919 sequences.