[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