a new problem related to partitions, dissections and polyominoes

[Max]

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