# [seqfan] Column Recurrences of Fibonacci Order

Ron Hardin rhhardin at att.net
Sun Aug 18 19:48:10 CEST 2013

```The orders of the column (or row) linear recurrences of this seem to form the Fibonacci series.

/tmp/diu
T(n,k)=Number of nXk binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or nw-se diagonally

Table starts
..1...1.....2......3........5.........8..........13...........21.............34
..1...1.....3......6.......13........28..........60..........129............277
..2...3....13.....35......112.......337........1034.........3154...........9637
..3...6....35....133......587......2448.......10414........44024.........186414
..5..13...112....587.....3631.....21166......126119.......745178........4416695
..8..28...337...2448....21166....172082.....1428523.....11771298.......97268701
.13..60..1034..10414...126119...1428523....16566199....190540884.....2197847780
.21.129..3154..44024...745178..11771298...190540884...3057290265....49208639399
.34.277..9637.186414..4416695..97268701..2197847780..49208639399..1105411581741
.55.595.29431.789100.26150120.802886174.25325358687.791176762937.24801939723742

Column 1 is A000045
Column 2 is A002478(n-1)

Empirical for column k:
k=1: a(n)=a(n-1)+a(n-2)
k=2: a(n)=a(n-1)+2*a(n-2)+a(n-3)
k=3: a(n)=a(n-1)+5*a(n-2)+4*a(n-3)-a(n-5)
k=4: a(n)=a(n-1)+10*a(n-2)+15*a(n-3)+4*a(n-4)-6*a(n-5)-a(n-6)+3*a(n-7)-a(n-8)
k=5: [order 13]
k=6: [order 21]
k=7: [order 34]
k=8: [order 55]
k=9: [order 89]

rhhardin at mindspring.com
rhhardin at att.net (either)
```

More information about the SeqFan mailing list