How many different rectangles of maximum horizontal side K can be formed in an N x N grid?

Question

Horizontal side of rectangle formed must be <= K

example: if N = 3 and K = 2 ans = 30

example: if N = 2 and K = 1 ans = 6

How to derive generalized formula?

Answer 1

HINT: A rectangle is determined by its four sides. There is no restriction on the height, so the top and bottom edges can be any two of the $N+1$ horizontal lines of the grid. Thus, there are $\binom{N+1}2$ ways to choose the top and bottom edges of the rectangle. Now we have to count the number of pairs of vertical grid lines that are at most $K$ units apart. If you draw some sketches, you should be able to see that for $1\le w\le K$ there are $N-w+1$ pairs of vertical grid lines $w$ units apart.

More explanation: Number the vertical grid lines $0$ through $N$ from right to left. A pair that are $w$ units apart must be numbered $k$ and $k+w$ for some $k$. The smallest possible value of $k$ is $0$. The largest is when $k+w=N$, so it’s $k=N-w$. There are therefore $N-w+1$ possibilities for $k$, from $0$ through $N-w$.

Thus, there are

$$\sum_{w=1}^K(N-w+1)=\sum_{w=1}^K(N+1)-\sum_{w=1}^Kw=K(N+1)-\sum_{w=1}^Kw$$

ways to choose the vertical edges of the rectangle. To complete the calculation, express $\sum_{w=1}^Kw$ in a closed form as a function of $K$, and then suitably combine the number of possibilities for the horizontal edges of the rectangle with the number of possibilities for the vertical edges.