[seqfan] Re: No isosceles triangles in a square grid, continued

Ron Hardin rhhardin at att.net
Wed Apr 27 14:12:18 CEST 2016


Okay, good.  I should drop the "right triangle" constraint.  For the right n+k-1 case i have so far
T(n,k)=Number of nXk 0..1 arrays with exactly n+k-1 having value 1 and no three 1s forming an isosceles right triangle

Table starts
.1.1...1....1.....1....1....1....1.....1.....1....1....1.1.1
.1.0...1....0.....1....0....1....0.....1.....0....1....0.1..
.1.1...0....1.....9....6...16...66....95...177..493.1153....
.1.0...1....0.....8....8...71..212...731..1840.5953.........
.1.1...9....8....12...58..367.1952.10854.28952..............
.1.0...6....8....58..192..838.4968.37436....................
.1.1..16...71...367..838.4892...............................
.1.0..66..212..1952.4968....................................
.1.1..95..731.10854.........................................
.1.0.177.1840...............................................
.1.1.493....................................................
.1.0........................................................
.1..........................................................

Empirical for column k:
k=1: a(n) = a(n-1)
k=2: a(n) = a(n-2)
k=3: a(n) = 3*a(n-1) -3*a(n-2) +4*a(n-3) -6*a(n-5) +3*a(n-6) -6*a(n-7) -16*a(n-8) +44*a(n-9) -14*a(n-10) -42*a(n-11) +65*a(n-12) -56*a(n-13) +52*a(n-14) -8*a(n-15) -65*a(n-16) +63*a(n-17) -43*a(n-18) +64*a(n-19) -6*a(n-20) -119*a(n-21) +122*a(n-22) +42*a(n-23) -93*a(n-24) +16*a(n-25) +20*a(n-26) -6*a(n-27) -8*a(n-28) -2*a(n-30) -2*a(n-31) +4*a(n-32)
probably the last recurrence within my reach.
 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: Wednesday, April 27, 2016 7:07 AM
 Subject: [seqfan] Re: No isosceles triangles in a square grid, continued
   
Ron, There are two separate problems being discussed:

No right isosceles triangles:
=====================
NORIT(m,n) = max no of 1's in mXn array so that no 3 form a right isosceles
triangle
- this array is not yet in OEIS (Because I don't know the initial values -
but I would like to)

A271906(n) = main diagonal of that array = max no of 1's in nXn array so
that no 3 form a right isosceles triangle. It is known that this grows like
O(n^1.99999) but not as fast as O(n^2)  (!)  (paper in preparation, with
Warren Smith, part of a general attack on problems of this class)

No isosceles triangles:
=================
A271914(m,n) = max no of 1's in mXn array so that no 3 form an isosceles
triangle, and
I conjecture A271907(m,n) <= m+n-1. The main diagonal is conjectured to be
= 2n-2 for n>1.

A271907(n) = main diagonal of that array = max no of 1's in nXn array so
that no 3 form an isosceles triangle,
which I conjecture to equal 2n-2 for n>1.

[The comment you quoted about "For (m,n) with 10 >= m >= n >= 2, the only
exceptions [to m+n-2] are..."
was referring to A271914(m,n). There are in fact infinitely
many exceptions, thanks to Rob's work. But (I conjecture) all values are <=
m+n-1.]

Best regards
Neil

>
>

--
Seqfan Mailing list - http://list.seqfan.eu/


   


More information about the SeqFan mailing list