[seqfan] Inversion Formula for Peculiar G.F. - Help

Paul D. Hanna pauldhanna at juno.com
Sun Jan 16 03:33:58 CET 2005


> What is the non-recursive inversion of the equation:
>  
> F(x) = a(0)(1-x) + a(1)*x*(1-x)(1-2x) + a(2)*x^2*(1-x)(1-2x)(1-3x) + 
> ...          + a(n)*x^n*(1-x)(1-2x)(1-3x)*..*(1-(n+1)x) + ...
>  
> Knowing F(x), can one determine a(n) without recursion?
  
Here is a development that seems promising in finding a g.f. 
solution when the above F(x) is a constant. 
 
But I am encountering some difficulty, and can not make it work. 
My question is why - what am I missing. 
Does anyone see the missing pieces to this puzzle???   
     
The columns of triangle A102086 form an amazing set of examples. 
I found the following g.f.s for each column k: 
 
(1) T(k,k) = k+1 
    = Sum_{n>=0} T(n+k,k)*x^n*Product_{j=1..n+1}(1-(j+k)*x).
 
This leads to the matrix equation
 
(2) [C(x)]*T = D 
 
where [C(x)] is the upper triangular matrix of column functions: 
 
(3) [C(x)](n,k) = x^(k-n)*Product_{j=n..k} (1-(j+1)*x) 
 
and T equals A102086 as a lower triangular matrix, 
and D is the simple diagonal matrix: {1,2,3,4,...}. 
 
At first I re-arranged (2) to state the solution as: 
 
(4) T = [C(x)]^(-1) * D
 
and concluded that we have a g.f. for A102086 (=T)!!!
 
But when we multiply the matrices in (4), 
the resultant T does NOT produce a g.f. for A102086!!!  Why? 
 
Is it because (2) involves divergent infinite series as in (1)?  
 
To be specific, the product (4) produces:
[C(x)]^(-1) * D = 
 
[1/(1-x), -2*x, 0, 0, 0, ...]
[0, 2/(1-2*x), -3*x, 0, 0, ...]
[0, 0, 3/(1-3*x), -4*x, 0, ...]
[0, 0, 0, 4/(1-4*x), -5*x, 0, ...]
[0, 0, 0, 0, 5/(1-5*x), -6*x, ...]
...
which I expected at first to produce g.f.s for A102086! 
 
Below I give A102086 and explicit examples of the column g.f.s. 
 
What am I neglecting or doing wrong? 
Any comments would be appreciated.
Thanks,    
    Paul
----------------------------------------------------
 
Triangle A102086 begins: 
1,
1, 2,
3, 4, 3,
16, 20, 9, 4,
127, 156, 63, 16, 5,
1363, 1664, 648, 144, 25, 6,
18628, 22684, 8703, 1840, 275, 36, 7,
311250, 378572, 144243, 29824, 4200, 468, 49, 8,
6173791, 7504640, 2849400, 582640, 79775, 8316, 735, 64, 9,
...
Note that A102086 as a triangular matrix M is a solution to:
       M^2 = SHIFTUP(M).
Also, column 0 equals Valery Liskovets sequence: 
http://www.research.att.com/projects/OEIS?Anum=A082161
1,3,16,127,1363,18628,311250,6173791,142190703,3737431895,...
 
EXPLICIT EXAMPLES of G.F.s.
Here are the g.f.s for the first few columns of A102086.
Column 0: 
1 = (1-x) + 1*x*(1-x)(1-2x) + 3*x^2*(1-x)(1-2x)(1-3x) + ... 
+ T(n,0)*x^n*(1-x)(1-2x)(1-3x)*..*(1-(n+1)*x) + ...
 
Column 1: 
2 = 2(1-2x) + 4*x*(1-2x)(1-3x) + 20*x^2*(1-2x)(1-3x)(1-4x) + ... 
+ T(n+1,1)*x^n*(1-2x)(1-3x)(1-4x)*..*(1-(n+2)*x) + ...
 
Column 2: 
3 = 3(1-3x) + 9*x*(1-3x)(1-4x) + 63*x^2*(1-3x)(1-4x)(1-5x) + ... 
+ T(n+2,2)*x^n*(1-3x)(1-4x)(1-5x)*..*(1-(n+3)*x) + ...
 
EXPLICIT EXAMPLES of [C(x)].
The transpose of the upper triangular matrix 
of column functions [C(x)] is: 
[C(x)]^t = 
(1-x),  
x*(1-x)(1-2x), (1-2x), 
x^2*(1-x)(1-2x)(1-3x), x*(1-2x)(1-3x), (1-3x),
x^3*(1-x)(1-2x)(1-3x)(1-4x), x^2*(1-2x)(1-3x)(1-4x), x*(1-3x)(1-4x),
(1-4x), 
...
 
The inverse of upper triangular matrix [C(x)] is simple: 
[C(x)]^-1 =  
[1/(1-x), -x, 0, 0, 0, 0, ...]
[0, 1/(1-2*x), -x, 0, 0, 0, ...]
[0, 0, 1/(1-3*x), -x, 0, 0, ...]
[0, 0, 0, 1/(1-4*x), -x, 0, ...]
[0, 0, 0, 0, 1/(1-5*x),-x, ...]
... 
 
PARI CODE.
/* [C(x)] = Upper triangular matrix of column functions */
C=matrix(6,6,n,k,if(n<=k,x^(k-n)*prod(j=n,k,1-j*x)))
 
/* Diagonal matrix {1,2,3,...} */
D=matrix(6,6,n,k,if(n==k,n))
 
/* Build triangle A102086 */
{T(n,k)=if(n<k,0,if(n==k,k+1,
polcoeff(1-sum(i=k,n-1,T(i,k)*x^i*prod(j=1,i-k+1,1-(j+k)*x+x*O(x^n))),n))
)}
A102086=matrix(6,6,n,k,if(n>=k,T(n-1,k-1)))
 
/* This product produces D but with remainder terms */
C*A102086 
 
/* Does this product produce g.f. for A102086? */
(C^-1)*D
 
END.





More information about the SeqFan mailing list