Number of rectangles in N*M grid

Software Development
#1

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 NM 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