|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
