a new problem related to partitions, dissections and polyominoes

[Edwin Clark]

On Thu, 23 Feb 2006, Brendan McKay wrote:

> Is the following true?
> 
> Choose two points, draw a line through them, move it a tiny bit to
> the right if they are vertically above one another or a tiny bit
> upwards otherwise, then that gives all cases.  Upper bound
> binomial(n^2,2) which seems pretty good.  I proved nothing!
> 
> Brendan.

Compare the following:

A018808 Number of lines through at least 2 points of an n X n grid of 
points.  

0, 0, 6, 20, 62, 140, 306, 536, 938, 1492, 2306, 3296, 4722, 6460, 
8830, 11568, 14946, 18900, 23926, 29544, 36510, 44388, 53586, 63648, 
75674, 88948, 104374, 121032, 139966, 160636, 184466, 209944, 239050, 
270588, 305478, 342480, 383370, 427020 

offset 0,3

and

A114043 Take an n X n square grid of points in the plane; 
a(n) = number of ways to divide the points into two sets using a straight 
line.  
	1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 
11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 
101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 
361329, 407303 (list)
	OFFSET 	

1,2








> 
> * Max <maxale at gmail.com> [060223 05:05]:
> > Richard,
> > 
> > Actually it grows proportionally to 3/pi^2 * n^4.
> > 
> > Max
> > 
> > On 2/22/06, Richard Guy <rkg at cpsc.ucalgary.ca> wrote:
> > > Here's a crude argument which gives  O(n^6)
> > > as upper bound. Almost certainly not more
> > > than quartic, and I could believe cubic: ---
> > >
> > > Number of `different' slopes,  O(n^4)
> > > Number of `different' intercepts, O(n^2)    R.
> > >
> > > On Wed, 22 Feb 2006, N. J. A. Sloane wrote:
> > >
> > > > Seqfans,  this arose from a question i received yesterday from a correspondent:
> > > >
> > > > %I A114043
> > > > %S A114043 1,7,29,87,201
> > > > %N A114043 Take an n X n square grid of points in the plane; a(n) = number of ways to divid
> > > > e the points into two sets using a straight line.
> > > > %C A114043 The line may not pass through any point. This is the "labeled" version - rotatio
> > > > ns and reflections are not taken into account.
> > > > %C A114043 8*binomial(2n,n) = 8*A000984(n) is a crude upper bound. Related to A001168.
> > > > %O A114043 1,2
> > > > %K A114043 nonn,nice,more
> > > > %e A114043 Examples: the two sets are indicated by X's and o's.
> > > > %e A114043 a(2) = 7:
> > > > %e A114043 XX oX Xo XX XX oo oX
> > > > %e A114043 XX XX XX Xo oX XX oX
> > > > %e A114043 --------------------
> > > > %e A114043 a(3) = 29:
> > > > %e A114043 XXX oXX ooX ooo ooX ooo
> > > > %e A114043 XXX XXX XXX XXX oXX oXX
> > > > %e A114043 XXX XXX XXX XXX XXX XXX
> > > > %e A114043 -1- -4- -8- -4- -4- -8- Total = 29
> > > > %A A114043 Ugo Merlone (merlone(AT)econ.unito.it) and njas, Feb 22 2006
> > > >
> > > > I think it is quite interesting.  Maybe someone would like to
> > > > compute some more terms!
> > > >
> > > > Although at first glance it seems to be quadratic in n,
> > > > I believe - because of the connection with A001168 and
> > > > other polyomino sequences that it is in fact exponential.
> > >
> > >
> 

---------------------------------------------------------
  W. Edwin Clark, Math Dept, University of South Florida
           http://www.math.usf.edu/~eclark/
---------------------------------------------------------