a new problem related to partitions, dissections and polyominoes

[Richard Guy]

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.