[seqfan] Re: Column Recurrences of Fibonacci Order

[Neil Sloane]

Ron, I showed your message to Doron Zeilberger.

He can prove that the Fibonacci number is an upper
bound on the order of the recurrence for all k.
He also worked out - with a rigorous proof - the
generating functions for the first 11 columns,
and in each case the degree of the denominator is equal to the Fibonacci
number.

Can you submit the array (read by anti-diagonals) to the OEIS,
as well as columns 3,4,5,6 (say)? Then I will add his
analysis to the entry for the array. It is much too long to show here, but
I will give the start of his message.

Could you also add the sequence for the main diagonal of the array?
Here is the extension to 11 terms that Doron computed:
[1, 1, 13, 133, 3631, 172082, 16566199, 3057290265, 1105411581741,
776531523355217, 1063228770141145384]
Let me know the A-numbers!

Here is the start of Doron's message

                   Rigorously derived generating functions for
               enumerating k by n Hardin matrices for k from 1 to 11
                              By Shalosh B. Ekhad

               Definition: A Hardin matrix has entries from {0,1}
               with no adjacent 1's horizontally, vertically, or
             in the NE-SW direction, and whose top-left entry is 1

                 Definition: For a fixed k, Let f(k)(x) be the
                              generating function
                whose coefficient of x^n is the number of n by k
                We have the following (rigorously-derived) facts
              followed by the first, 20, terms of the enumerating
                      sequence (for  the sake of Sloane)

f[1](x) = -x/(x^2+x-1)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181,
6765]

f[2](x) = -x/(x^3+2*x^2+x-1)

[1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201,
58425,

    125491, 269542, 578949, 1243524]

f[3](x) = -x*(x^3-x-2)/(x^5-4*x^3-5*x^2-x+1)

[2, 3, 13, 35, 112, 337, 1034, 3154, 9637, 29431, 89895, 274564, 838609,

    2561372, 7823242, 23894643, 72981777, 222909351, 680835436, 2079486057]

f[4](x) =
x*(2*x^4-7*x^3-x^2+3*x+3)/(x^8-3*x^7+x^6+6*x^5-4*x^4-15*x^3-10*x^2-x+
1)

[3, 6, 35, 133, 587, 2448, 10414, 44024, 186414, 789100, 3340345, 14140347,

    59858152, 253389483, 1072638232, 4540650778, 19221306410, 81366888278,

    344439152622, 1458066449898]

I will send you his full message in a separate email. I will be happy to
send it to anyone else who is interested.
Neil


On Sun, Aug 18, 2013 at 1:48 PM, Ron Hardin <rhhardin at att.net> wrote:

> 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)
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>



-- 
Dear Friends, I have now retired from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com