Asymptotic Approach to 2D Arrays

How would one go about determining the value of the general term of 
the array

              1   1   1   1   1   1   1   1 ...
              1   3   5   7   9  11  13  15 ...
              1   5  13  25  41  61  85 113 ...
              1   7  25  63 129 231 377 575 ...
               etc.

where A(n,m) = A(n-1,m) + A(n-1,m-1) + A(n,m-1)?  There is a nice 
approach based on generating functions, but it's also interesting to 
note that this array of numbers, like the binomial coefficients, has an
asymptotic relation to the normal distribution.  In fact, the Central 
Limit Theorem can be used to show that just about ANY symmetrical 2-D
recurrence formula with arbitrary boundary values gives a distribution 
of numbers that asymptotically approaches normality.

In the example mentioned above, we can write the numbers sideways in a
manner similar to Pascal's triangle 

1                                1                                  1
2                             1     1                               2
3                          1     3     1                            5
4                       1     5     5     1                        12
5                    1     7    13     7     1                     29
6                 1     9    25    25     9     1                  70
7             1     11    41    63    41    11     1              169

The numbers in the right hand column are the sums of the individual rows,
and satisfy the linear recurrence s(n)=2s(n-1)+s(n-2).  It follows that

                s(n) = k(1+sqrt(2))^n - k(1-sqrt(2))^n

where k = 1/2sqrt(2).

Knowing the total sum of each row, it only remains to determine how the
values are distributed in a given row.  If we are just interested in the
asymptotic behavior, the Central Limit Theorem can be used to estimate 
the values of A(n,m), m=0 to n, because they approach a "histrogram" of 
a normal distribution as n increases.

For example, take the 11th row of the preceding array:

   1   19   145  575  1289  1683  1289   575  145   19   1

The sum of this row is s(11)=5741, so this is the overall scale factor 
for the density.  To find the scale factor for the "x axis", observe 
that the integral over the central strip is 1683/5741 = 0.293154, so 
we know the central strip extends from -0.3761 sigma to +0.3761 sigma, 
and all the strips are 0.7522 sigma wide.  On this basis we can use 
the normal distribution to estimate the values in this row as follows 
[rounded to integers]:

    2   22   148   572   1285   1683   1285  572   148   22   2

This demontrates that even at n=11 the distribution is already quite 
close to normal.  The nice thing about this approach is that it works 
on a very wide class of arrays - just about any array generated by a 
symmetrical recurrence formula.  It doesn't even have to be a linear 
recurrence.  For example, the Eulerian numbers are generated by a 
recurrence of the form E(n,m)=nE(n-1,m)+mE(n,m-1), and they also 
asymptotically approach a normal distribution.

Return to MathPages Main Menu