Combinatorics - number of disjoint rectangles My question is:  I have a grid $m \cdot n$ and I have to find how many pairs of disjoint rectangles there are. Squares are allowed too. They also can't share edges or vertices.
I know, that number of all rectangles in the grid is ${m+1 \choose 2} \cdot {n+1 \choose 2}$ but I can't find out how many disjoint pairs there are. Thank you.
 A: Two disjoint rectangles must either have $4$ distinct horizontal extended sides or $4$ distinct vertical extended sides. There are $\binom{n+1}4$ sets of $4$ distinct horizontal extended sides, and for each of them we can pick any two vertical extended sides for the top rectangle and any two for the bottom rectangle; this accounts for
$$\binom{n+1}4\binom{m+1}2^2$$
pairs of rectangles that can be separated by a horizontal line. Similarly, there are 
$$\binom{m+1}4\binom{n+1}2^2$$
pairs of rectangles that can be separated by a vertical line. Finally, there are 
$$2\binom{n+1}4\binom{m+1}4\tag{1}$$
pairs of rectangles that can be separated by both a horizontal and a vertical line, so there are 
$$\binom{n+1}4\binom{m+1}2^2+\binom{m+1}4\binom{n+1}2^2-2\binom{n+1}4\binom{m+1}4$$
pairs of disjoint rectangles. (The factor of $2$ in $(1)$ arises from the fact that the upper rectangle can be either to the left or to the right of the lower rectangle.)
A: A little bit like computing the number of rectangles in your grid, you consider 2 disjoint rectangles, and extend their sides: you get $k$ vertical lines and $l$ distinct horizontal lines, with $k,l\in\{2,3,4\}$.
How many pairs of disjoint rectangles are there, that give you the same lines?
Let it be $n_{k,l}$ pairs. Thus the sought after answer is:
$$\sum_{(k,l)\in \{2,3,4\}^2} n_{k,l}{{m+1\choose k}}{{n+1}\choose l}$$
Now we need to compute the values of the $n_{k,l}$.
Observe that $n_{k,l}=n_{l,k}$. Indeed, each configuration of the $(k,l)$ case corresponds to a configuration of the $(l,k)$ case, so let us assume that $k\leq l$.
$n_{2,2}=0$ since otherwise it would imply that we get two rectangles that are identical.
$n_{2,3}=0$ =since otherwise it would imply that we get rectangles that share the middle vertical line.
$n_{3,3}=0$ since otherwise they would share a vertical line and a horizontal line so they share a vertex.
$n_{2,4}=1$: the lines determine our rectangles, if we want them to be disjoint.
$n_{3,4}=6$: consider a horizontal line that is shared by two rectangles. You look at the vertical lines from left to right, and the first two belong to one and the last two, to the other one. In this case, their second horizontal lines are differnet (so that $k=3$), thus for each case, you get $2$ configurations, so considering there are $3$ disjoint cases, for each shared horizontal line you get $6$ configurations.
$n_{4,4}=10$; this one's a little harder. Consider the horizontal lines and lok at them from top to bottom: say your uppermost rectangle is $A$ and your second one, $B$. You write down in order the rectangles to which your lines belong to.
So you only get $AABB$ (case $1$), $ABAB$ (case $2$) or $ABBA$ (case $3$). Now to enumerate each case, we check the vertical lines from left to right:
case $1$: every configuration is possible. The $A$ rectangle is in an upper lane than the $B$ rectangle so they only need to give us $4$ vertical lines: ${4\choose 2}=6$ possibilities.
case $2$ and $3$: only $AABB$ and $BBAA$ can come out, otherwise, they wouldn't be disjoint.
Now this gives you the whole formula. Unfortunenatly, I don't know if you have a more compact expression for this :(
