a new problem related to partitions, dissections and polyominoes

[N. J. A. Sloane]

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.