Consider a binary n-vector, r_1.
Let r_0 = [0 0 .... 0 0] be the all zero vector.
For i > 1, compute r_i[j] = r_{i-1}[j] + r_{i-1}[j-1] + r_{i-1}[j+1] + r_{i-2}[j] (mod 2),
taking the terms to be zero when the index is 0 or greater than n.

For example:
                  0 0 0 0 
                  1 0 1 0  <--- r_1
                  1 0 1 1
                  0 0 1 0
                  1 1 0 0
                  0 0 0 0  <--- all zero vector
 
We list as the period below, values of i when we reach the all-zero vector again,
for some r_1 (provided no previous row was all-zero)

This sequence of vectors can also be generated by the Fibonacci polynomials.

Some theorems from our papers:

1. The maximum period value always occurs with r_1 = (1, 0, 0, ...., 0 0)
2. All period lengths divide the maximum period
3. The maximum period is less than 3*2^{n/2} (except for n=5).
   (actually, the correct constant is ~85/32 rather than 3)
4. If (for a fixed n) we have r_m=0, then the n by (m-1) grid is not
   completely solvable for the coin flipping problem.


n            periods
--           -------
3             6, 3
4             5
5             24, 12, 8, 6, 4, 3, 2
6             9
7             12, 6, 3
8             28, 14, 7, 4, 2
9             30, 15, 10, 5, 3
10            31
11            48, 24, 16, 12, 8, 6, 4, 3, 2
12            63
13            18, 9, 3
14            340, 170, 85, 68, 34, 20, 17, 10, 5, 4, 2
15            24, 12, 6, 3
16            255, 17, 15
17            168, 84, 56, 42, 28, 24, 21, 14, 12, 8, 7, 4, 3, 2
18            513
19            60, 30, 20, 15, 10, 6, 5, 3
20            2340, 585, 18, 9, 4, 2     

Other periods of e1=(1 0 0 0 0 ....)

n=39 period = 120
n=40 period = 1,048,575 
n=41 period = 4680
n=42 period = 16,383 
n=43 period = 372
n=44 period = 92,820
n=45 period = 12,282
n=46 period = 8,388,607
n=47 period = 192 
n=48 period = 2,097,153 
n=49 period = 6150
n=50 period = 262,140
n=81 period = 2,097,150

We have also studied this recurrence without the "boundaries" 
and in this case it is called Pascal's Rhombus.
See: 
	1. "A Pascal Rhombus," W. Klostermeyer, M. Mays, L. Soltes, and G. Trapp,
	    Fibonacci Quarterly, November 1997, pp. 318-328. 

	2. "On the Density of Ones in Pascal's Rhombus," J. Goldwasser, W. Klostermeyer,
	    M. Mays, and G. Trapp, to appear in Discrete Mathematics, (in which we prove that the rhombus
	    is "almost" all zeroes).
	    
Example Pascal's Rhombus


                1
              1 1 1
            1 2 4 2 1
          1 3 8 9 8 3 1
          
To see this mod 2, go back to the previous page.
          
Left Bounded Rhombus

1
1  1
3  2  1
6  7  3  1
16 18 12 4  1

We have shown that the position of the maximum value in a row creeps
to the right in the left bounded rhombus at a logarithmic rate.