Counting Sub-Rectangles

Правка en2, от Ahmed_Mohamed_Al3adl, 2025-04-16 16:52:38

How to count how many rectangles of size r × s fit inside a larger rectangle of size n × m.

Example:

Now, if I have a 5*8 rectangle, and I want to know how many 3*2 rectangles are inside the 5*8 rectangle?
Here, 5*8 is n * m and 3*2 is r * s. But I use letters to express a general rule.

Let's get the rule

Let's take a step-by-step approach to create the rule:
- Firstly, it's logical when I am at any square in n * m chape, and I want to draw r * s rectangle, it should still have >(r-1) squares in n dimension, and >(s-1) squares in m dimension.
- Secondly: The last valid square in n dimention will be n - (r - 1), and any squere blew it is also valid, so n - (r - 1) is the number of valid squares as a base point in n dimention, if I think on the chape base start from right bottom corner, and it's the (0, 0) position.
- Thirdly: We apply the same for the m dimension, so now we know that the valid quares in the m dimension are equal to m - (s - 1).
- Forthly: multiply the number of valid squares in n and m dimensions, to get all valid squares.
The general rule is: (n - (r -1)) * (m - (s - 1)).

Apply the rule in the example:

  • r * s = 3 * 2 AND n * m = 5 * 8.
  • r = 3, s = 2, n = 5 and m = 8;
  • (n - (r - 1)) * (m - (s - 1)) = (5 - (3 - 1)) * (8 - (2 - 1)) = (5 - 2) * (8 - 1) = 3 * 7 = 21.
  • So there are 21 rectangles with the dimensions 3*2 in the rectangle with 5*8 dimensions.
Теги math, computational geometry, geometry, geometric combinatorics

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Ahmed_Mohamed_Al3adl 2025-04-16 16:52:38 4
en1 Английский Ahmed_Mohamed_Al3adl 2025-04-16 16:50:50 1503 Initial revision (published)