A124497: 1-2-3-...-k Trees

[Paul D. Hanna]

Emeric (and Seqfans),
     What a fascinating problem.
Although I will not be using this formula now, 
let's extend your formula for k-ary trees: 
(*)  [z^n] C[k](z)^m  =  binomial(kn+m-1,n)*m/[(k-1)n+m] 
to give the coefficient of z^n in the m-th power of C[k](z). 
Note that the logarithm is obtained similarly: 
(**) [z^n] log( C[k](z) ) =  binomial(kn-1,n)/[(k-1)n], for n>0.
No doubt you are already aware of this lovely facts; 
and they may simplify some series representations involved here. 
 
I will not attempt to give a simpler g.f. for your M[n], where:
   M[n+1](z) = M[n](z)*C[n](z^n*M[n-1]^(n-1)); 
 
but using PARI I will list the first 31 terms for n=2..10 (below). 
 
You have some impressive results so far. 
     Paul 
 
(PARI)
{M=1/(1-x+O(x^31));
 for(n=2,10,
   M=M*sum(k=0,30,binomial(n*k,k)/((n-1)*k+1)*(x^n*M^(n-1))^k);
   print("n="n":");print(Vec(M))
 )
}

n=2: 
[1, 1, 2, 3, 6, 11, 23, 47, 102, 221, 493, 1105, 2516, 5763, 13328, 
30995, 72556, 170655, 403351, 957135, 2279948, 5449013, 13063596, 
31406517, 75701508, 182902337, 442885683, 1074604289, 2612341856, 
6361782007, 15518343597]
n=3: 
[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, 318681491431, 892495078849]
n=4: 
[1, 1, 2, 4, 10, 24, 62, 160, 425, 1140, 3105, 8528, 23643, 66008, 
185526, 524384, 1489810, 4251852, 12184745, 35048405, 101156752, 
292865417, 850314803, 2475327088, 7223400899, 21126670372, 
61920289652, 181838859665, 534980035009, 1576653291583, 
4654122552827]
n=5: 
[1, 1, 2, 4, 10, 25, 67, 180, 495, 1375, 3871, 10993, 31493, 90843, 
263686, 769466, 2256135, 6643082, 19634705, 58232350, 173242381, 
516860717, 1546035258, 4635543843, 13929569399, 41943013047, 
126532961332, 382396277940, 1157548532794, 3509416800398, 
10655157352027]
n=6: 
[1, 1, 2, 4, 10, 25, 68, 186, 522, 1479, 4246, 12289, 35872, 105411, 
311662, 926270, 2765778, 8292296, 24953437, 75338686, 228140842, 
692733127, 2108652750, 6433255041, 19668210742, 60247367313, 
184879648441, 568281131800, 1749490180723, 5393738767856, 
16651705792875]
n=7: 
[1, 1, 2, 4, 10, 25, 68, 187, 529, 1514, 4393, 12856, 37944, 112740, 
337017, 1012671, 3056978, 9265765, 28187304, 86028764, 263339173, 
808256040, 2486804090, 7668374150, 23694936466, 73354869098, 
227489892754, 706643494680, 2198340096395, 6848600059320, 
21363953916171]
n=8: 
[1, 1, 2, 4, 10, 25, 68, 187, 530, 1522, 4437, 13056, 38766, 115908, 
348733, 1054775, 3205251, 9780165, 29951916, 92029644, 283606809, 
876333336, 2714448570, 8426790446, 26213887250, 81699432762, 
255072076566, 797641572824, 2498068134817, 7834443329344, 
24602515926899]
n=9: 
[1, 1, 2, 4, 10, 25, 68, 187, 530, 1523, 4446, 13110, 39030, 117060, 
353404, 1072811, 3272526, 10024884, 30825490, 95103360, 294300321, 
913203240, 2840650881, 8856206258, 27667828196, 86601978030, 
271545341505, 852829532176, 2682483667081, 8449321174753, 
26648690288909]
n=10: 
[1, 1, 2, 4, 10, 25, 68, 187, 530, 1523, 4447, 13120, 39095, 117400, 
354974, 1079493, 3299426, 10128934, 31216245, 96538200, 299477771, 
931628670, 2905496841, 9082358938, 28450647731, 89294760932, 
280759352295, 884216374006, 2788990466531, 8809540396813, 
27863492984436]

END. 
----------------------------------------------------------
On Sat, 4 Nov 2006 23:30:30 -0500 (EST) Emeric Deutsch
<deutsch at duke.poly.edu> writes:
> 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