some help is needed Re: SEQ+# A127157 FROM Emeric Deutsch (fwd)

[Paul D. Hanna]

Emeric (and Seqfans), 
    Could it be that your g.f.: 
(1) z^2*G^3-z(z+2)G^2+(1+2z)G-t^2*z-1=0 
has a slight typo (should be t^1 instead of t^2)? 
 
I believe that the g.f. should be: 
(3) z^2*G^3 - z(z+2)G^2 + (1+2z)G - t*z - 1 = 0
 
which can be rewritten as:
1+t*z - (1+2*z)*G + z*(z+2)*G^2 - z^2*G^3 = 0 
 
But wait, this G has a constant term: G(0) = 1 
that your triangle does not include.
 
To remove the constant, substitute A = G+1 to get: 
 
(4) 1+t*z - (1+2*z)*(A+1) + z*(z+2)*(A+1)^2 - z^2*(A+1)^3 = 0 
 
Here, A = A(z,t) is the correct g.f. of your triangle. 
 
Putting (4) into powers of A: 
(5) t*z - (1-z)^2*A + 2*z*(1-z)*A^2 - z^2*A^3 = 0
 
which is equivalent to: 
(6) t*z - A*(1-z - z*A)^2 = 0
 
Restating: 
(7) t*z/(1-z)^2 = A*( 1 - z/(1-z)*A )^2 
  
 
Now, from your nice formula for [t^k z^n] A(z,t): 
(2) [t^k z^n] = 2*binomial(3k-1,2k)*binomial(n-1+k,3k-2)/(3k-1) 
we can easily derive A to be: 
 
(8) A(z,t) = t*z/(1-z)^2 * F( t*z^2/(1-z)^3 )^2
 
where F = 1 + x*F^3 is the g.f. of A001764 = [1,1,3,12,55,273,...]. 
  
 
So the problem now is to obtain (8) from (7). 
  
I have verified that (7) and (8) do in fact agree 
(I give my PARI code below) 
 
but can we apply Lagrange Inversion to (7) to obtain (8)? 
  
--Paul
 
/* Using Equation (8) where F = 1 + x*F^3: */
F=1+x;for(i=0,12,F=1+x*F^3+O(x^13));Vec(F)
A=t*z/(1-z +O(z^13))^2*subst(F^2,x,t*z^2/(1-z +O(z^13))^3);
T(n,k)=polcoeff(polcoeff(A,n,z),k,t)
for(n=0,12,for(k=0,(n+1)\2,print1(T(n,k),","));print("")) 
 
/* Using Equation (7): */
A=z+t;for(i=0,12,A=A + t*z - A*(1-z - z*A)^2 +O(z^13))
T(n,k)=polcoeff(polcoeff(A,n,z),k,t)
for(n=0,12,for(k=0,(n+1)\2,print1(T(n,k),","));print("")) 
 
/* Result of both (7) and (8): */ 
1,
2,
3,2,
4,10,
5,30,7,
6,70,56,
7,140,252,30,
8,252,840,330,
9,420,2310,1980,143,
10,660,5544,8580,2002,
11,990,12012,30030,15015,728,
12,1430,24024,90090,80080,12376,
  
On Tue, 27 Feb 2007 23:09:17 -0500 (EST) Emeric Deutsch
<deutsch at duke.poly.edu> writes:
> Dear Seqfans,
> The bivariate g.f. G(t,z) for the number of ordered trees with
> n edges and having 2k nodes of odd degree (not outdegree) satisfies
> 
> (1)        z^2*G^3-z(z+2)G^2+(1+2z)G-t^2*z-1=0
> 
> I have found this in my notes dating back to 1997; I have to recall
> the derivation (probably, a minor problem). However, according to my 
> 
> notes, I have found the formula
> 
> (2)        [t^k z^n] = 
> 2*binomial(3k-1,2k)*binomial(n-1+k,3k-2)/(3k-1)
> 
> only by inspection (consistent with the g.f. at least up to n=50).
> 
> Any idea for deriving (2)? Probably a tricky change of variables
> will make (1) "Lagrangeable".
> 
> Below you'll find the submitted sequence.
> 
> Thanks for any input.
> Emeric
> 
> 
> 
> ---------- Forwarded message ----------
> Date: Tue, 27 Feb 2007 22:52:40 -0500
> From: The On-Line Encyclopedia of Integer Sequences 
> <oeis at research.att.com>
> Reply-To: deutsch at duke.poly.edu
> To: njas at research.att.com
> Cc: deutsch at duke.poly.edu
> Subject: SEQ+# A127157 FROM Emeric Deutsch
> 
> The following is a copy of the email message that was sent to njas
> containing the sequence you submitted.
> 
> All greater than and less than signs have been replaced by their 
> html
> equivalents.  They will be changed back when the message is 
> processed.
> 
> This copy is just for your records.  No reply is expected.
>   Subject: PRE-NUMBERED NEW SEQUENCE A127157 FROM Emeric Deutsch
> 
> 
> %I A127157
> %S A127157 1, 2, 3, 2, 4, 10, 5, 30, 7, 6, 70, 56, 7, 140, 252, 30, 
> 8, 252, 840, 330, 9, 420, 2310, 1980, 143, 10, 660, 5544, 8580, 
> 2002, 11, 990, 12012, 30030, 15015, 728, 12, 1430, 24024, 90090, 
> 80080, 12376, 13, 2002, 45045, 240240, 340340, 111384, 3876, 14, 
> 2730, 80080, 583440, 1225224, 705432, 77520, 15, 3640, 136136, 
> 1312740, 3879876, 3527160, 813960, 21318
> %N A127157 Triangle read by rows: T(n,k) is the number of ordered 
> trees with n edges and 2k nodes of odd degree (not outdegree; 
> 1<=k<=ceil(n/2)).
> %C A127157 Neil: this is a funny-shaped triangle. END
> 
> Row n has ceil(n/2) terms.
> Row sums are the Catalan numbers (A000108).
> T(n,1)=n;
> T(n,2)=2*binom(n+1,4)=2*A000332(n+1);
> T(n,3)=7*binom(n+2,7)=7*A000580(n+2);
> T(n,4)=30*binom(n+3,10)=30*A001287(n+3);
> T(n,5)=143*binom(n+4,13)=143*A010966(n+4);
> T(2n-1,n)=A006013(n-1).
> %F A127157 T(n,k)=2*binomial(3k-1,2k)*binomial(n-1+k,3k-2)/(3k-1)  
> (formula obtained only by inspection).
> 
> 
> G.f.=G-1, where G=G(t,z) satisfies 
> z^2*G^3-z(z+2)G^2+(1+2z)G-t^2*z-1=0.
> %e A127157 Triangle starts:
> 1;
> 2;
> 3,2;
> 4,10;
> 5,30,7;
> 6,70,56;
> %p A127157 
> T:=(n,k)->2*binomial(3*k-1,2*k)*binomial(n-1+k,3*k-2)/(3*k-1): 
> for n from 1 to 15 do seq(T(n,k),k=1..ceil(n/2)) od;
> %Y A127157 A000108,A000332,A000580,A001287,A010966,A006013
> %O A127157 1
> %K A127157 ,nonn,
> %A A127157 Emeric Deutsch (deutsch at duke.poly.edu), Feb 27 2007
> RH
> RA 192.20.225.32
> RU
> RI
> 
>