2-dimensional version of Fibonacci numbers

[Marc LeBrun]

I just submitted A089934 thru 9, with plenty of cross links, qv.


On the off-chance it'd be amusing to {0,1} fans, or helpful to someone
hacking "Hard Square", I'll add a few notes on how I ground out the
values (apologies if this is too banal):

Take the infinite {0,1} matrix(!) M = 

 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... 
 1 0 1 1 0 1 0 1 1 0 1 1 0 1  
 1 1 0 1 1 1 1 0 1 1 0 1 1 1  
 1 1 1 0 0 1 1 1 1 1 1 0 0 1  
 1 0 1 0 0 1 0 1 1 0 1 0 0 1  
 1 1 1 1 1 0 0 0 1 1 1 1 1 1  
 1 0 1 1 0 0 0 0 1 0 1 1 0 1  
 1 1 0 1 1 0 0 0 1 1 0 1 1 1  
 1 1 1 1 1 1 1 1 0 0 0 0 0 1  
 1 0 1 1 0 1 0 1 0 0 0 0 0 1  
 1 1 0 1 1 1 1 0 0 0 0 0 0 1  
 1 1 1 0 0 1 1 1 0 0 0 0 0 1  
 1 0 1 0 0 1 0 1 0 0 0 0 0 1  
 1 1 1 1 1 1 1 1 1 1 1 1 1 0
 ...                         ...

(A089939) where Mij=1 just when Ai & Aj = 0, where A is A003714 (which I
call the Fibbinary numbers) and & is the usual bit-wise logical-and
operation.

The Fibbinary numbers encode the allowed 01-patterns for a row/column,
and Mij is 1 just when the i-th and j-th patterns can appear in adjacent
columns/rows.

For finite computation, I took the square submatrices Mn of size
Fibonacci(n+2) (so M1 is 2x2 etc).  These Mn describe all the n-bit
patterns that can be adjacent in a size-n matrix.

Then Gn(x) = (I - x Mn)^(-1) is a matrix generating function whose
coefficient of x^k shows the numbers of allowed adjacencies in an nXk /
kXn matrix.

Distribute the x's and sum the first row, and you get the rational
generating functions, Hn(x) for n-bit patterns whose k-th term counts
the nXk / kXn cases.

Theoretically, to get the diagonal values, you could extract them from
the infinite matrix generating function in the same way.  If you could
describe the result you'd presumably have a "formula".

This may be hopeless, but M is suggestively patterned.  For example
along the main diagonal are square Fibonacci-sized blocks of 0s, and
there's an interesting recursive structure.

Maybe this is useful, maybe not.  Anyway, "Enjoy"!


NJAS: I forgot to add links to A089939 to the other entries, sorry.