# Number of rectangles in N*M grid

We are given a N*M grid, print the number of rectangles in it.
Examples:

Input : N = 2, M = 2
Output : 9
There are 4 rectangles of size 1 x 1.
There are 2 rectangles of size 1 x 2
There are 2 rectangles of size 2 x 1
There is one rectangle of size 2 x 2.

Input : N = 5, M = 4
Output : 150

Input : N = 4, M = 3
Output: 60

Let us derive a formula for number of rectangles.
If the grid is 1×1, there is 1 rectangle.
If the grid is 2×1, there will be 2 + 1 = 3 rectangles
If it grid is 3×1, there will be 3 + 2 + 1 = 6 rectangles.
we can say that for N1 there will be N + (N-1) + (n-2) … + 1 = (N)(N+1)/2 rectangles
If we add one more column to N×1, firstly we will have as many rectangles in the 2nd column as the first,
and then we have that same number of 2×M rectangles.
So N×2 = 3 (N)(N+1)/2
After deducing this we can say
For N
M we’ll have (M)(M+1)/2 (N)(N+1)/2 = M(M+1)(N)(N+1)/4
So the formula for total rectangles will be M(M+1)(N)(N+1)/4

.

Combinatorial Logic:

N*M grid can be represented as (N+1) vertical lines and (M+1) horizontal lines.
In a rectangle, we need two distinct horizontal and two distinct verticals.
So going by the logic of Combinatorial Mathematics we can choose 2 vertical lines and 2 horizontal lines to form a rectangle. And total number of these combinations is the number of rectangles possible in the grid.

Total Number of Rectangles in NM grid: N+1C2 * M+1C2 = *(N(N+1)/2!)(M*(M+1)/2!)** = N(N+1)M(M+1)/4*

`// JAVA Code to count number of`

`// rectangles in N*M grid`

`import` `java.util.*;`

`class` `GFG {`

` `

` ` `public` `static` `long` `rectCount(` `int` `n, ` `int` `m)`

` ` `{`

` ` `return` `(m * n * (n + ` `1` `) * (m + ` `1` `)) / ` `4` `;`

` ` `}`

` `

` ` `/* Driver program to test above function */`

` ` `public` `static` `void` `main(String[] args)`

` ` `{`

` ` `int` `n = ` `5` `, m = ` `4` `;`

` ` `System.out.println(rectCount(n, m));`

` ` `}`

`}`

Output:

150