Multiplication of sequences
Christian G.Bower
bowerc at usa.net
Wed Feb 24 06:20:50 CET 1999
I wrote:
> I know of four models of sequence multiplication satisfying these
> properties.
>
> Termwise multiplication:
> (a0,a1,a2,...) * (b0,b1,b2,...) = (a0*a1,b0*b1,...)
>
> Multiplication of generating functions (or convolution)
> cn=SUM{i+j=n}ai*bj
>
> Multiplication of exponential generating functions
> (or exponential convolution)
> cn=SUM{i+j=n}c(i,j)*ai*bj
>
> Dirichlet convolution
> cn=SUM{i*j=n}ai*bj
>
> I wonder if there are any others.
Yes there are.
Taking a hint from exponential convolution
(BTW the formula should have been: > cn=SUM{i+j=n}C(n,i)*ai*bj)
The exponential generating function of a sequence {an} is
a0 + a1x + a2x^2/2! + a3x^3/3! + ...
Suppose instead of factorials we use arbitrary numbers.
Say for any sequence {zn} such that zk != 0 for any k,
we define the z-generating function of a as:
a0/z0 + a1x/z1 + a2x^2/z2 + a3x^3/z2 + ...
and the induced sequence product, z-convolution.
Then if C(x)=A(x)*B(x) (z.g.f.'s for c, a and b):
c_n = SUM{i+j=n} (z_n/(z_i*z_j)) * a_i * b_j
The algebra of the series shows that the product satisfies all the
usual qualities of multiplication.
Just one problem, if z is not carefully chosen, we are likely to get
fractions.
(1 + x/2 + x^2/3 + x^3/4 + ...)^2 = (1 + 2x/2 + (33/12)x^2/3 + ...)
However, if I choose z = 1,1,2,2,4,4,8,8...
I get z_n/(z_k*z_(n-k)) = 2 if n is even and k is odd, 1 otherwise.
so that:
(1 + x + x^2/2 + x^3/2 + x^4/4 + x^5/4 + x^6/8 + ...)^2 =
1 + 2x + 4x^2/2 + 4x^3/2 + 7x^4/4 + 6x^5/4 + 10x^6/8 + ...
There are many other possibilities.
One interesting fact is that for any constant c != 0:
if we set {zn} be z_n=c^n, then z-convolution is just
ordinary convolution.
Christian
____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1
More information about the SeqFan
mailing list