2-dimensional version of Fibonacci numbers

[Mitchell Harris]

on a query by Yuval Dekel, Marc LeBrun responded

let IS(n,m) = # of independent sets on P_n x P_m (the sequences in 
question)

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

Excellent! 

>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.

Wilf and Calkin's paper seem not to do it so systematically.

>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.

Yes, the construction is:

let A_n be the (square) matrix (of size F_{n+2} x F_{n+2})

  A_{n-1}    B_{n-1}
  B_{n-1}^T  0

and B_n be (of size F_{n+2} x F_{n+1}

  A_{n-1}
  B_{n-1}^T

with base cases

  A_0 = {{1}}
  B_0 = {{1}}

Then 1.(A_n)^m.1 equals IS(n,m) (A_n is just a permuted form of the matrix
in Wilf/Calkin). And of course this is equivalent to the extracted
coefficient from the generating function given Gn(x) above. This may make
it easier to compute values.

Any particular Gn(x) is a nice rational function from which one can read 
off (from the coeffs of the poly in the denominator) a nice recurrence.
The problem is coming up with a recurrence for the set of recurrences.

With such a nice recursive structure, one would think that computing such 
a thing would be straightforward (playing around with elimination), but I 
have not yet found a general recurrence. Any ideas?

-- 
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris