[seqfan] Re: LRS formulas for n>=...?

[Hagen von Eitzen]

rhhardin at att.net schrieb:
> http://home.att.net/~rhhardin/temp.txt is the current (unfinished, working)
> collection of these sequences that the shell scripts have assembled out of
> results so far.  Nearly done, I guess, though; with the recurrence
> formulas still in.
>
>   
The recursions should be provable. For example with
> %N A000002 Number of nX2 binary arrays with all 1s connected, a path of 1s from upper left corner to lower right corner, and no 1 having more than two 1s adjacent
>   
Consider all nx2 binary arrays with all 1s connected, a path of 1s from 
upper left to LOWER ROW and no 1 having more than two 1s adjacent.
These are of one of the following types according to their lower two rows:

..
01
01

..
01
11

..
10
10

..
10
11

..
11
01

..
11
10

(And one type not possible for n > 2:
..
11
11
)

Let their respective counts be a1(n), ..., a7(n).
Then for n > 3, we have
a2(n+1) = a1(n+1) = a1(n) + a5(n)
a4(n+1) = a3(n+1) = a3(n) + a6(n)
a5(n+1) = a4(n)
a6(n+1) = a2(n)
a7(n+1) = 0

This clearly leads to some recurrence formula for a(n) = a1(n) + a2(n) + 
a4(n) + a5(n) + a7(n).

A similar argument should be possible with n x k arrays for any fixed k, 
as checking the condition "no more than two 1s adjacent" for the new 
penultimate row requires only checking two rows.
Since more subtypes are available, things become more cumbersome, though.

Hagen