No subject

[Emeric Deutsch]

Dear Seqfans,
We (Lou Shapiro and myself) would like to submit a few
sequences similar to A124497 (shown at the bottom of this
message). They will refer to 1-2-3-4 trees, 1-2-3-4-5
trees, etc. rather than to 1-2-3 trees. We can describe
the corresponding g.f.'s but we need help in finding the
terms themselves.

Here is the description of all the g.f.'s. Let M[k](z) be
the g.f. of the 1-2-...-k trees with thinning limbs. I will
describe these functions; consequently, we may disregard
the objects counted by them.

Denote by C[k](z) the g.f. of the k-ary trees. C[k]
satisfies C[k]=1+zC[k]^k and the coefficient of z^n
in its series expansion is
(*)      binom(kn,n)/[(k-1)n+1].

I will write Mk for M[k] and Ck for C[k].

Obviously, M1(z)=1/(1-z) (path-trees). The next one is 
M2(z)=M1(z)C2(z^2*M1), i.e. M1 times C2 evaluated at
z^2*M1. This gives no problem since
C2(z)=[1-sqrt(1-4z)]/(2z). We obtain A090344.

Next M3(z)=M2(z)C3(z^3*M2^2); since there is an
explicit expression for C3(z), namely
C3(z)=2/sqrt(3z)*sin[(1/3)*arcsin(sqrt(27z/4))],
this yields easily A124497.

 From here on we need help.
M4(z)=M3(z)C4(z^4*M3^3); 
Most probably sequence starts with
1,1,2,4,10,24,62,160,425,1140,3105 (I used some terms
of the series of C4(z); see (*)).

M5(z)=M4(z)C5(z^5*M4^4);
Most probably sequence starts with
1,1,2,4,10,25,67,180,495,1375,3871 (I used some terms
of the series of C5(z); see (*)).

And so on.

These sequences approach A124344:
1,1,2,4,10,25,68,187,530,1523,4447,13121,39107,...

Many thanks.
Emeric

--------------------------------
A124497  Number of 1-2-3 trees with n edges and with thinning limbs. 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.

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; listen)
OFFSET  0,3
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).
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);
CROSSREFS  Cf. A090344, A124344.
KEYWORD  nonn,new
AUTHOR  Emeric Deutsch and Louis Shapiro (deutsch(AT)duke.poly.edu, 
lshapiro(AT)Howard.edu), Nov 04 2006