Partitioning points with a line Let $A_{m, n} = \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$. A straight line would partition the points into two sets. How many ways are there to do it?
Let $p_{m, n}$ be that number. Apparently $p_{1, n} = n$ and $p_{2, n}$ looks like $\binom{2n}{2}+1$ but $p_{3, n}$ is already too hard for me.
I'm sure that $\binom{2m+2n-4}{2} < p_{m, n} < 2(m+n)\binom{mn}{2}$ but that's very rough.
 A: The problem is that your points are arranged on a regular grid, which means they are not in general position. As a consequence, a number of partitions with a line are not possible which otherwise were if you had $p = m\times n$ many points in general position. An upper bound for the number of partitions in your problem with dimension $d=2$ is therefore the number $C(p,d)$ of linear partitions of $p= m\times n$ many points in general position which is given (1) as 
$$
p_{m,n} \leq C(m n,2) = m  n +  \binom {m  n -1} 2
$$
as a special case  of the general formula 
$$
C(p,d) = \sum_{k=0}^{d} \binom {p-1} k
$$
A more detailed treatment on the grid problem can be found in (2). There, amongst other results, asymptotics are given for large $m,n$:
$$
p_{m,n} \simeq \frac{3}{\pi^2} m^2 n^2 
$$
Ref.:
(1) 
Thomas Cover, 1965: 
Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition
(2) Dragan M. Acketa  and   Joviša D. Žunic : On the number of linear partitions of the (m,n)-grid. 
Information Processing Letters archive, 
Volume 38,  Issue 3, May 7, 1991, Pages 163 - 168 
