<s>[INST] Get amount of submatrixes from $a \times b $matrix I was trying to do the following exercise
Given a grid of size $a \times b$, write a formula able t calculate the total number of rectangles contained in this rectangle. All integer sizes and positions are counted.
Examples:
$3 \times 2$ matrix $\Rightarrow 18$
$4 \times 4$ matrix $\Rightarrow 100$
Here is how the $3\times2$ grid works:
$1$ rectangle of size $3\times 2$:
[][][]
[][][]
$2$ rectangles of size $3\times 1$:
[][][]
$4$ rectangles of size $2\times 1$:
[][]
$2$ rectangles of size $2\times 2$
[][]
[][]
$3$ rectangles of size $1\times 2$:
[]
[]
$6$ rectangles of size $1\times 1$:
[]
As you can see $(1 + 2 + 4 + 2 + 3 + 6) = 18$, and is the solution for the $3\times 2$ grid.
...
Alledgedly, the answer is $\frac{((ab)+a)((ab)+b))}{4}$
I can't understand why, can anybody explain this?
 [/INST] Yes, although I find it easier to understand it as $\frac{a(a+1)b(b+1)}{4}$.
Every rectangle can be described by selecting two not necessarily distinct columns (the columns the corners are going to occupy) and two not necessarily distinct rows (the rows the corners are going to occupy).
There are $\binom{a}{2}=\frac{a(a-1)}{2}$ ways to select distinct columns and $a$ ways to select only one column. So $\frac{a(a+1)}{2}$ ways in total.
There are $\binom{b}{2}=\frac{b(b-1)}{2}$ ways to select distinct rows and $b$ ways ways to select only one row, so $\frac{b(b+1)}{2}$ in total.
So there are $\frac{a(a+1)}{2}\frac{b(b+1)}{2}=\frac{a(a+1)b(b+1)}{4}=\frac{(ab+a)(ab+b)}{4}$ ways to select the rows and columns of the corners of the rectangle, this uniquely determines each rectangle.
</s>