[seqfan] Re: Column Recurrences of Fibonacci Order

Tue Aug 20 02:27:18 CEST 2013

I'll take it out of the queue and submit it.

Nice that somebody made sense of it!

Incidentally (so far) hor vert and antidiagonal has the same recurrences except for column 5 an order 9 recurrence suffices.  But the h v diagonal recurrence for column 5 or order 13 also works for it.  Evidently some roots are not excited in that case.

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

>________________________________
> From: Neil Sloane <njasloane at gmail.com>
>To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu> 
>Sent: Monday, August 19, 2013 8:04 PM
>Subject: [seqfan] Re: Column Recurrences of Fibonacci Order
> 
>
>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
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>
>