a new problem related to partitions, dissections and polyominoes

[Brendan McKay]

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.

* 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.
> >
> >