Convoluting Arrays

Let A and B denote infinite 2-dimensional arrays

  A = a00 a01 a02 a03 a04 ...     B = b00 b01 b02 b03 b04 ...
      a10 a11 a12 a13 ...             b10 b11 b12 b13 ...
      a20 a21 a22 ...                 b20 b21 b22 ...
      a30 a31 ...                     b30 b31 ...
      a40 ...                         b40 ...
        etc.                            etc.

For any fixed number x we can construct another array using the
formula
                    m+n
          C[m,n] = SUM  A[m-j,j] B[n-j,j] x^j
                    j=0

where A and B are understood to have zero values whenever the 
indicies are negative.  We will denote the above operation by 
C = F(A,B,x).

This operation leads to some interesting results.  Suppose we define
the array U1 as
                 U1 = 1 1 1 1 1 ..
                      1 1 1 1 ..
                      1 1 1 ..
                      1 1 ..
                      1 ..
                        etc.

and then define U2 = F(U1,U1,1) and U3 = F(U2,U2,1) and so on.  The
limit of this process is the array of binomial coefficients

               U_inf = 1 1 1 1 1 ..
                       1 2 3 4 ..
                       1 3 6 ..
                       1 4 ..
                       1 ..

Thus, letting B denote this array of binomial coefficients, we see
that B is the unique array such that B = F(B,B,1).  More generally we
can define an array Q(x) as the unique array Q such that Q=F(Q,Q,x).
(I believe the sequence converges for ANY x.)

Now consider the array  A = F(B,B,-1), which has the values

              A = 1  1  1  1  1  1  1  1..
                  1  0 -1 -2 -3 -4 -5..
                  1 -1 -2 -2 -1  1 ..
                  1 -2 -2  0  3 ..
                  1 -3 -1  3 ..
                  1 -4  1 ..
                  1 -5 ..
                  1 ..

In general the array given by A = F(B,B,k) satisfies the recurrence

      A[m,n] = A[m-1,n] + A[m,n-1] + (k-1) A[m-1,j-1]

Numerous combinatorial identities can be established for this family
of arrays.  Interestingly, the roots of the polynomial whose
coefficients are the nth diagonal of F(B,B,-1) are exactly the 
values of g such that the linear fractional mapping

                               1 + z
                     z  -->  g -----
                               1 - z

is periodic with a period of n.

Return to MathPages Main Menu